Note basic

• leetcode 136 - single number

Given a non-empty array of integers nums, every element appears twice except for one. Find that
single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]

Output: 1

Example 2:

Input: nums = [4,1,2,1,2]

Output: 4

Example 3:

Input: nums = [1]

Output: 1

Constraints:

o 1 <= nums.length <= 3 * 104

o 3 * 104 <= nums[i] <= 3 * 104

o Each element in the array appears twice except for one element which appears only
once.

• static and dynamic allocation

• Kadanes algorithm -leetccode 53, subarray sum

Given an integer array nums, find the

subarray

with the largest sum, and return

its sum
.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]

Output: 1

Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]

Output: 23

Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

o 1 <= nums.length <= 105

o 104 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and
conquer approach, which is more subtle.

class Solution {

public:

int maxSubArray(vector<int>& nums) {

//kadane's algorithm

int currentSum = 0;

int maxSum = INT_MIN;

/* for (int start = 0; start < nums.size();start++){ */

for (int start:nums){

maxSum = max(currentSum,maxSum);

if(currentSum < 0){

currentSum = 0;

return maxSum;

};

• leetcode 169- Majority element

• class Solution {

• public:

• int majorityElement(vector<int>& nums) {

• //brute force approch : o(n2)

• /* int n = nums.size();

• for(int val : nums){

• int frequency = 0;

• for(int ele: nums){

• if(val == ele){

• frequency++;

• }

• }

• if( frequency > n/2){

• return val;

• }

• }
•

• return -1; */

• //sorting approch better than brute force : o(nlogn)

• /* int n = nums.size();

• sort(nums.begin(),nums.end());

• int fre = 1;

• int ans = nums[0];

• for(int i = 1; i<n; i++){

• if( nums[i] == nums[i-1]){

• fre++;

• }else{

• fre = 1;

• ans = nums[i];

• }

• if(fre > n/2){

• return ans;

• }

• }

• return ans; */

• //mores voting algorithm : o(n)

• int fre = 0;

• int ans = 0;

• for (int i =0; i<nums.size(); i++){

• if(fre ==0){

• ans = nums[i];

• } if(ans == nums[i]){

• fre++;

• }else{
 • fre--;

• }

• }

• return ans;

• }

• };

• Leetcode 50 || Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

Example 1:

Input: x = 2.00000, n = 10

Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3

Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2

Output: 0.25000

Explanation: 2-2 = 1/22 = 1/4 = 0.25

Constraints:

o 100.0 < x < 100.0

o 231 <= n <= 2311

o n is an integer.

o Either x is not zero or n > 0.

o 104 <= xn <= 104

public:

double myPow(double x, int n) {

//corners (if unique input)

if(n==0) return 1.00;

if(x==0) return 0.00;

if(x == 1) return 1.00;

if(x == -1 && n%2 == 0) return 1.00;

if(x == -1 && n%2 != 0) return -1.00;

long binForm = n; //store power n into binForm

double ans = 1;

if(n < 0){ //if power is negative

binForm = -binForm; // make n into positive

x = 1/x; // if power is negative number become 1/x

while(binForm>0){

if(binForm % 2 == 1 ){ // reminder is reponsible for binary last digit is 1 or 0

ans *= x; // ans = ans * x where x is the number

x *= x; // x = x * x where x is multiply by the number

binForm /=2; // number is multiply so the power is devided by 2

return ans;

};

• 121. Best Time to Buy and Sell Stock

You want to maximize your profit by choosing a single day to buy one stock and choosing a different
day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit,
return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]

Output: 5

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.

Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]

Output: 0

Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

o 1 <= prices.length <= 105

o 0 <= prices[i] <= 104

class Solution {

public:

int maxProfit(vector<int>& prices) {

int bestBuy = prices[0]; // store first day as the best buy day

int maxProfit = 0;

for (int i = 1; i < prices.size(); i++){

if(prices[i] > bestBuy){ // compare bestBuy number with the i th day element

maxProfit = max(maxProfit,prices[i]-bestBuy);// find maximum between i'th day profit and

}
 bestBuy = min(bestBuy,prices[i]); //find minimum between previous price and i'th day price

return maxProfit;

};

• Leetcode 11 | Container with Most Water || 2 pointer approch

• class Solution {

• public:

• int maxArea(vector<int>& height) {

• /* Brute force approch : O(n2) (Time Limit Exceeded 56 / 63 testcases passed

• because Constraints:

• n == height.length

• 2 <= n <= 105

• 0 <= height[i] <= 104 ) */

• /* int maxWater = 0;

• for(int i = 0; i < height.size(); i++){

• for(int j = i + 1; j < height.size(); j++){

• int heightWater = min(height[i], height[j]); // find minimum water height level from
seleted two line

• int width = j - i; // width is right line - first line

• int area = heightWater * width;

• maxWater = max(area, maxWater);

• }

• }

• return maxWater; */

•
 • // 2 Pointer Approch : O(n)

• int maxWater = 0;

• int leftBar = 0;

• int rightBar = height.size() - 1;

• while(leftBar < rightBar){

• int heightofWater = min(height[leftBar],height[rightBar]);

• int width = rightBar - leftBar;

• int area = heightofWater * width;

• maxWater = max(maxWater,area);

• height[leftBar] < height[rightBar] ? leftBar++ : rightBar-- ; // tinary operator for if ccase

• }

• return maxWater;

• }

• };

11. Container With Most Water

Solved

Medium

Topics

Companies

Hint

You are given an integer array height of length n. There are n vertical lines drawn such that the two
endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the
most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

!https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/17/question_11.jpg

Input: height = [1,8,6,2,5,4,8,3,7]

Output: 49

Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max
area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]

Output: 1

Constraints:

o n == height.length

o 2 <= n <= 105

o 0 <= height[i] <= 104

• https://brainstation.io/career-guides/software-engineer-interview-
questions?utm_source=chatgpt.com