Contents

Binary Search

Find the Duplicate Number

Search Insert Position

Sort Colors
Find First and Last Position of Element in Sorted Array

Length of Last Word

Set Matrix Zeroes.

Pascals Triangle

Single Element in a Sorted Array

Search 2D Matrix
Find Peak Element....
Jump Game

Product of Array Except Self.

Find Minimum in Rotate Sorted Array

Search in Rotated Sorted Array

Binary Search

704. Binary Search

Easy © Topics & Companies

Given an array of integers nums which is sorted in ascending order, and an integer
target, write a function to search target in nums.If target exists, then return its
index. Otherwise, return -1.

You must write an algorithm with 0(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9

Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2

Output: -1
Explanation: 2 does not exist in nums so return -1

1 // C++ solution
2 class Solution {
3 public:
int search(vectorcint>& nums, int target) {
// Initialize pointers low and high representing the search range.
int low = @, high = nums.size() - 1;
// Use a uhile loop to perform binary search.
while (low <= high) {
// Caleulate the middle index mid.
int mid = (low + high) / 2;
// I the element at mid is equal to the target, return mid.
if (nums[mid] == target) {
return mid;
¥
J/ If the element at mid is greater than the target, update high to mid - 1.
else if (nums[mid] > target) {
high = mid - 1;
¥

J/ Tf the element at mid is less than the target, update low to mid + 1.
else {
Tou = mid + 1;
b
b
// Tf the while loop exits, return -1, indicating that the target is not present in the array.
return -1;

¥
Find the Duplicate Number

287. Find the Duplicate Number

Medium © Topics @ Companies

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number
You must solve the problem without modifying the array nuns and uses only constant extra space.

Example 1:
Input: nums = [1,3,4,2,2]
Output: 2

Example 2:
Input: nums = [3,1,3,4,2]
Output: 3

1 class Solution {
2 public:
3 int finduplicate(vector<int>& nums) {
4 For(int i=0;i<nums.size();it+)
5 1
3 For(int j=itl;j<nums.size();3++)
7 {
8 if(nums[d]==nuns[31)
9 {
10 return nums[i];
11 3}
12 3
13 b
14 return -1;
15
16 }
7 b

Search Insert Position

 35. Search Insert Position Solved @&
Easy O Topics @ Companies

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were
inserted in order.
You must write an algorithm with 0(log n) runtime complexity.

Example1:
Input: nums = [1,3,5,6], target = 5
output: 2
Example2:
Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7

Output: 4

1 class Solution {
2 public:
3 int searchInsert(vector<int>& nums, int target) {
4 int 1=
5 int r=nums.size()-1;
6 int m;
7 while(lesr){
8 m=(14+r)/2;
9 if(nums[m]==target){
10 return m;
11 Yelse if(nums[m]>target){
12 r=m-1;
13 }
14 else{
15 1=m+1;
16 }
17 3}
18 return 1;
19 3}
2 )

Sort Colors
Use bubble sort algorithm
75. Sort Colors
Medium © Topics @ Companies © Hint

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color
are adjacent, with the colors in the order red, white, and blue.

We will use the integers 9, 1, and 2 to represent the color red, white, and blue, respectively.
You must solve this problem without using the library's sort function

Example 1:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]

Output: [0,1,2]

1 class solution {
2 public:
3 void sortColors(vector<int>& nums) {
a int n=nums.size();
H int temp;
6
7 for(int i=8;icn-1;i++)
g {
9
10 for(int j=0;j<n-i-1;j++)
11
12 if (nums[§]>nums[§+1])
13 <
14 temp=nums[j];
15 nume [§41];
16
17 ¥
18 3}
19 }
2
Find First and Last Position of Element in Sorted Array

34. Find First and Last Position of Element in Sorted

Array
Medium © Topics & Companies

Given an array of integers nums sorted in non-decreasing order, find the starting and ending
position of a given target value.

If target is not found in the array, return [-1, -1]

You must write an algorithm with 0(log n) runtime complexity.

Example1:

Input: nums = [5,7,7,8,8,10], target = 8

Output: [3,4]

Example2:

Input: nums = [5,7,7,8,8,10], target = 6

Output: [-1,-1]

Example 3:

Input: nums = [], target = 0

OQutput: [-1,-1]
Cor v & Auto

class solution {
public:
vectorcint> searchRange(vectorcint>& nums, int target) {
if(nums. size()==8){
return {-1,-1};
}
int 11=0;
int rl= nums.size()-1;
while(11cr1){
int mi= 11+ (r1-11)/2;
if(nums[m1]>=target){
ri=mi;
}
else{
11=mi+l;
}
}

oy - Auw

int 12=0;
int r2= nums.size();
while(l2<r2){
int m2= 12+ (r2-12)/2;
if(nums[m2]>target){
r2=m2;
i
else{
12=m2+1;
¥
}

return {-1,-1};
}
if(11==12){
return{11,12};
}
return {11, 12-1};
Length of Last Word

58. Length of Last Word Solved@

tasy © Topics @ Companies

Given a string s consisting of words and spaces, return the length of the last word in the
string.

A word is a maximal substring consisting of non-space characters only.

Example 1:

Input: s = "Hello World"

Output: 5
Explanation: The last word is "World" with length 5.

Example 2:

Input: s = fly me to the moon

Output: 4
Explanation: The last word is "moon" with length 4.

Example 3:

Input: s = "luffy is still joyboy"

Output: 6
Explanation: The last word is "joyboy" with length 6.
 1 class Solution {
2 public:
3 int lengthOflLastWord(string s) {
4 int len = @, tail = s.length() - 1;
5 while (tail >= © && s[tail] == ' ') tail--;
6 while (tail >= @ && s[tail] != ' ') {
7 len++;
8 tail--;
9 }
10 return len;
11
12 }
13 )

Set Matrix Zeroes

73. Set Matrix Zeroes

Medium © Topics @ Companies @ Hint

Givenan m x n integer matrix matrix, if an elementis 0, set its entire row and columnto @'s.

You must do it in place.

Example 1:
 Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],(1,0,1]

Example2:

o/1/2]0 ololo]o
3452|0450
11315 o|3|1]o0
Input: matrix = [[0,1,2,0],(3,4,5,2],[1,3,1,5]
Output: [[0,0,0,0],(0,4,5,0],[0,3,1,0]]
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {

int n = matrix.size();
int m = matrix[e].size();

vector<int>rows(n,1);
vector<int>cols(m,1);

for(int i =0; d<n; i+H){

Forl(int 3 =0; j<m; 3p){
if(matrix[1][3] == ©){
rows[i] = ©;
cols[3] = @5

for(int i =8; i<n; i++){

for(int j =0; j<m; j++){
if(rows[i] == @ || cols[j] == ©){
matrix[i][3] =0;
Pascals Triangle

118. Pascal's Triangle

Easy © Topics @ Companies

Given an integer numRows , return the first numRows of Pascal’s triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],(1,2,1],[1,3,3,1],(1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]
 3 class Solution {
4 public:
5 std::vector<std::vector<int>> generate(int numRows) {
6 std::vector<std::vector<int>> result;
7
8 for (int i = ©; i < numRows; ++i) {
9 std::vector<int> row(i + 1, 1);
1e
11 for (int j = 1; j < i; ++j) {
12 row[j] = result[i - 1][j - 1] + result[i - 1][j];
13 ¥
14
15
16
17
18
19
20
21

Single Element in a Sorted Array

540. Single Element in a Sorted Array

Medium © Topics & Companies

You are given a sorted array consisting of only integers where every element
appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in 0(log n) time and 0(1) space.

Example 1:

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

Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11]

Output: 10
Co+ v & Auto

class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = (left + right) / 2;
if (mid % 2 == 1) {
mid--;
}
if (nums[mid] != nums[mid + 1]) {
right = mid;
} else {
left = mid + 2;
}
}
return nums[left];
74. Search a 2D Matrix
Medium © Topics & Companies

You are given an m x n integer matrix matrix with the following two
properties:

e Each row is sorted in non-decreasing order.

o The first integer of each row is greater than the last integer of the previous
row.

Given an integer target, return true if target isin matrix or false

otherwise.

You must write a solution in 0(log(m * n)) time complexity.

Example 1:

113|585 |7

10 |11 | 16 | 20

23 |30 | 34 | 60
Input: matrix = [[1,3,5,7],[10,11,16,20], [23,30,34,60]],
target = 3
Outout: true
Example 2:

113|585 |7

10 | 11 | 16 | 20

23 | 30 | 34 | 60
Input: matrix = [[1,3,5,7],[10,11,16,20], [23,30,34,60]],
target = 13
Output: false

1 class Solution {
2 public:
3 bool searchMatrix(vector<vector<int>>& matrix, int target) {
4
5 int m = matrix.size();
6 int n = matrix[@].size();
7
8 int low = ©;
9 int high = m*n - 1;
10
11 while(low <= high){
12 int mid = (low + high)/2;
13 int ele = matrix[mid/n][mid%n];
14 if(target == ele) return true;
15
16 if(target > ele) low = mid + 1;
17 else high = mid - 1;
18 }
19
20 return false;
21 }
50. Pow(x, n)
Medium © Topics @ Companies

Implement pow(x, n), which calculates x raised to the power n (ie., x").

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 272 = 1/22 = 1/4 = 0.25

C++ Vv @ Auto

1 class Solution {
2 public:
3 double myPow(double x, int n) {
4 ‘ return pow(x, n);
5 }
6 1
Find Peak Element

162. Find Peak Element

Medium © Topics & Companies

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the
array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = —=.In other words, an element is always
considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in 0(log n) time.

Example 1:

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

Output: 2
Explanation: 3 is a peak element and your function should return
the index number 2.

Example 2:

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

Output: 5
Explanation: Your function can return either index number 1
where the peak element is 2, or index number 5 where the peak
element is 6.
 1 class Solution {
2 public:
3 int findPeakElement(vector<int>& nums) {
4 int left=0;
5 int right=nums.size()-1;
6 while(left<right){
7 int mid=left+(right-left)/2;
8 if(nums[mid]>nums[mid+1]){
9 right=mid;
10 }
11 else{
12 left=mid+1;
13 }
14 }
15 return left;
16 }
17 %

Jump Game
55. Jump Game
Medium © Topics @ Companies

You are given an integer array nums. You are initially positioned at the array's first index,
and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

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

Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the
last index.

Example 2:

Example 2:

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

Output: false
Explanation: You will always arrive at index 3 no matter what.
Its maximum jump length is 0, which makes it impossible to
reach the last index.
C++ Vv @ Auto

1 class Solution {
2 public:
3 bool canJump(vector<int>& nums) {
4 int n = nums.size();
5 int maxReach = 9;
6 for (int 1 = ©; 1 < n; i++) {
7 if (i > maxReach) return false;
8 maxReach = max(maxReach, i + nums[i]);
9 }
10 return true;
1}
12}

Product of Array Except Self

238. Product of Array Except Self

Medium © Topics & Companies

Given an integer array nums, return an array answer such that answer[i] s equal to the
product of all the elements of nums except nums[i] .

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in 0(n) time and without using the division
operation.

Example 1:

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

Output: [24,12,8,6]
Example 2:

Input: nums = [-1,1,0,-3,3]

Output: [0,0,9,0,0]

public int[] productExceptself(int(] nums) { BRY-RUNOF CoDE

7/ Array to store all left multiplication
int[] left = new intlnums.lengthl; [(2,1.3,4])
// Array to store all right multiplication left = é- 61
nt[] right = new int[nuns.length];
tlo] =1 3 _ ey
o r(int i = 1; i < nums.length; i++) { right = [ ]
teftli] = leftli - 1] * nums[i - 11;

et 1
}

right [nums . Length - 1] =

for (int i = nuns.length - 2; i > ~1; i--) {
right[i] = right[i + 1] * nums[i + 1];
y
int(] ans = new int(nuns.length]
for (int i = 0; i < nums.length; i++) { s i
ans[i] = leftli] * right[il; 4-¥
y ey
return ans;
}

1 #include <vectors
2
3 class solution {
4 public:
5 std::vector<int> productExceptSelf(std: :vectorcint>& nums) {
6 int n = nums.size();
7
8 // Initialize the result array with all elements set to 1
] std: ivectorcint> result(n, 1);
10
1 // Calculate the product of all elements to the left of each element
12 int leftProduct = 1;
13 for (int i=0; i <n; +H) {
1 result[i] *= leftProduct;
15 leftProduct *= nums[i];
 // Calculate the product of all elements to the right of each element and multiply with the result
int rightProduct = 1;
for (int i =n - 1; i>=@; --i) {
result[i] *= rightProduct;
rightproduct *= nuns[il;
}
return result;

152. Maximum Product Subarray

Medium © Topics @ Companies

Given an integer array nums, find a subarray that has the largest product, and return the
product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

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

Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]

Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a
subarray.
 1 #include <vector>
2 #include <algorithm>
3
4 class Solution {
5 public:
6 int maxProduct(std: :vector<ints& nums) {
7 int n = nums.size();
8 if (n == @) return e;
°
10 int result = nums[e];
11 int maxEndingHere = nums[e];
12 int minEndingHere = nums[e];
13
14 for (int i = 1; 1 < ny ++i) {
15 // Swap max and min if the current number is negative
16 if (nums[i] < @) {
17 std: :swap(maxEndingHere, minEndingHere);
18 }

19
20 // Update max and min ending here considering the current number
21 maxEndingHere = std::max(nums[i], maxEndingHere * nums[i]);
22 minEndingHere = min(nums[i], minEndingHere * nums[i]);
23
22 // Update the overall result
25 result = std::max(result, maxEndingHere);
26 3}
27
28 return result;
29 }
30 )
31
15. 3Sum
Medium © Topics @ Companies @ Hint

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i
'=j,1i!=k,and j != k,and nums[i] + nums[j] + nums[k] ==

Notice that the solution set must not contain duplicate triplets.

Example1:

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

Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1l] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] =0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets
does not matter.

Example 2:

Input: nums = [0,1,1]

Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]

Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
 1 // optinized Approach - O(n"2 logn + nlogn) - O(n"2 logn) time and O(n) space
2 class Solution {
3 public:
4 vectorcvectorcint>> threeSum(vector<int>e nums) {
5 int target = o;
6 sort(nums.begin(), nums.end()); // Sort the input array in ascending order.
7 setcvector<int>> s; // Use a set to store unique triplets.
8 vector<vector<int>> output; // Output vector to store the final result.
i
10 1/ Loop through the array with three pointers.
u for (int i=8; i < nums.size(); i++){
12 int j = i +1; // Start the second pointer at the next element after the current one.
13 int k = nums.size() - 1; // Start the third pointer at the end of the array.

14
15 // Use a two-pointer approach to find triplets that sum to the target.
16 while (3 < k) {
17 int sum = nums[i] + nums[§] + nums[k];
18
19 // If the sum is equal to the target, add the triplet to the set.
2 if (sum == target) {
21 s.insert({nums[i], nums[j], nums[k]});
2 s
23 k-=;
22 } else if (sum < target) {
25 // If the sum is less than the target, move the second pointer to the right.
26 3+
27 } else {
28 // If the sum is greater than the target, move the third pointer to the left.
29 k==;
30 ¥
31 b
32 b

33
34 // Convert the set of unique triplets to a vector for the final result.
35 for(auto triplets : s)
36 output.push_back(triplets);
37 return output;
38 1
E N H
40

11. Container With Most Water

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 i™ lineare (i, @) 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.

Example 1:

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

1 class Solution {
2 public:
3 int maxArea(vector<int>& height) {
4
5 int n = height.size();
6
7 //as n will always be 2 but height can be @ so maxarea init to @
8 int maxarea = 8;
]
10 int start = €;
1 int end = n-1;
12
13 while(start < end)
14 {
15 int currarea = min(height[start], height[end]) * (end - start);
16 maxarea = max(maxarea, currarea);
17
18 //move the one which is smaller, as this can only lead to higher area further ahead
19 if(height[start] <= height[end])
20 {
 22 }
23 else
22 {
25 end
2 3
27
28 }
29
30 return maxarea;
31 }
52 )

Find Minimum in Rotate Sorted Array

153. Find Minimum in Rotated Sorted Array

Medium © Topics @ Companies @ Hint

Suppose an array of length n sorted in ascending order is rotated between 1

and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

* [4,5,6,7,0,1,2] ifit was rotated 4 times.

e [0,1,2,4,5,6,7] ifit was rotated 7 times.

Notice
that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1time results
inthearray [a[n-1], a[@], a[l], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum
element of this array.

You must write an algorithm that runs in 0(log n) time.

Example 1:

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

Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3
times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]

Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and
it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]

Output: 11
Explanation: The original array was [11,13,15,17] and it
was rotated 4 times.

1 # C++ Code
2 class solution {
3 public:
4 int findiin(vectorcint>a nums) {
5 // Initialize ans to the first element of the array, assuming the array is not rotated.
6 int ans = numsfe];
7 /7 set low to @ and high to the last index of the array.
8 int low = @ , high = nums.size()-1;
9
10 // Check for Rotation:
1 // If the element at index low is less than the element at index high,
12 // the array is not rotated, and we return the element at index low as the minimum.
if(nums[low] < nums[high]){
return nums[low];
}

11 Binary search:
while(low <= high){
/7 1¢ nums[lou] < nuns[high], update ans and break the loop
if(nums[low] < nums[high]){
ans = min(ans , nums[low]);
break;
1

// Calculate the middle index

int mid = (low + high)/2;
// Update ans with the minimum of the current ans and the element at the middle index
ans = min(ans , nums[mid]);
/1 check for rotation
if(nuns[mid] >= nums[low]){
// 1 the element at the middle index is greater than or equal to the element at the low index,
/1 adjust low to mid + 1 (nove right).
low = mid + 1;
 35 }
36 elsef
37 /1 If the element at the middle index is less than the element at the low index,
38 /1 adjust high to mid -1 (move left).
39 high = mid -1 ;
4 3
a ¥
42
a3 7/ Return the final answer
as return ans;
45 }
4 )

Search in Rotated Sorted Array

33. Search in Rotated Sorted Array

Medium © Topics @ Companies

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot
index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1],
.., nums[n-1], nums[@], nums[1], ..., nums[k-1]] (0-indexed). For example,
[0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index
of target ifitisin nums, or -1 if it is notin nums.

You must write an algorithm with 0(log n) runtime complexity.

 Example 1:

Input: nums = [4,5,6,7,0,1,2], target = @

Output: 4

Example2:

Input: nums = [4,5,6,7,0,1,2], target = 3

Output: -1

Example 3:

Input: nums = [1], target = 0

Output: -1

T I~
61 We can solve this probles using binary search, but how?
62
6 The interesting property of a sorted and rotated array is that when we divide
64 the array into two halves. Atleast, one of the two halves is always sorted.
65
66 1f mid happens to the polnl of rotation then both the (right and left)
&7 halves will be sorted
Il
69+ nu; static int search(int(] nums, int target) {
%
n if(nums.length == @) {
n return -1;
7 »
u r
7 int start = 8;
7% int end = nums. length-1;
7
78 while(start <= end) {
7
80 int mid = (start + end)/2;
81
82 if(nums(mid) == target) {
83 return mid; o A
58 ) else ifif (nussstart]
(nuss(start] <= numsa[=10]) { F\o \
887 mmgn >= nums [start] & target <= nuas(mid])) {
(T \L \
88 = mid-1;
8 } e
% y st = mieens

https://www.youtube.com/watch?