Array¶
Largest¶
/*
QUESTION:-
Given an array A[] of size n. The task is to find the largest element in it.
Example:
Input:
n = 5
A[] = {1, 8, 7, 56, 90}
Output:
90
Explanation:
The largest element of given array is 90
*/
/*
APPROACH:-
-> Intialize the ans with starting element
-> Traverse the entire array and update the ans if the element is greater then ans
-> Finally, return the ans
*/
// CODE:-
int largest(int arr[], int n)
{
int ans = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > ans)
ans = arr[i];
}
return ans;
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(0)
/*
QUESTION:-
Given an array Arr of size N, print second largest distinct element from an array.
Example:
Input:
N = 6
Arr[] = {12, 35, 1, 10, 34, 1}
Output: 34
Explanation: The largest element of the
array is 35 and the second largest element
is 34.
*/
/*
APPROACH
-> If the current element is larger than ‘large’ then update second_large and large variables
-> Else if the current element is larger than ‘second_large’ then we update the variable second_large.
-> Once we traverse the entire array, we would find the second largest element in the variable second_large.
*/
// CODE:-
int print2largest(int arr[], int n)
{
int prev = -1, curr = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > curr)
{
prev = curr;
curr = arr[i];
}
else if (arr[i] > prev && arr[i] != curr)
prev = arr[i];
}
return prev;
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(0)
/*
QUESTION:-
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
*/
/*
APROACH:-
-> Initialize two variables: candidate and count. Set candidate to the first element of the array, and count to 1.
-> Iterate through the array starting from the second element:
If the current element is equal to the candidate, increment the count by 1.
If the current element is different from the candidate, decrement the count by 1.
If the count becomes 0, update the candidate to the current element and set the count to 1 again.
-> After the iteration, the candidate variable will hold the majority element.
Return the candidate as the result.
*/
// CODE:-
int majorityElement(vector<int> &nums)
{
int candidate = nums[0];
int vote = 1;
for (int i = 1; i < nums.size(); i++)
{
if (vote <= 0)
candidate = nums[i];
if (nums[i] == candidate)
vote++;
else
vote--;
}
return candidate;
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(0)
/*
QUESTION:-
You are given an array prices where prices[i] is the price of a given stock on the ith day.
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.
*/
/*
APPROACH:-
Initialize two variables: min_price and max_profit.
-> min_price = minimum price in the array.
-> max_profit = 0.
Iterate through the array, and for each price:
-> Update min_price to the minimum price seen so far.
-> Update max_profit to the maximum profit seen so far, or the current price minus min_price, whichever is greater.
Return max_profit.
*/
// CODE:-
int maxProfit(vector<int> &prices)
{
int minprice = prices[0];
int ans = 0;
for (int i = 1; i < prices.size(); i++)
{
ans = max(ans, prices[i] - minprice);
minprice = min(minprice, prices[i]);
}
return ans;
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(0)
Sorted and Rotated¶
/*
QUESTION:-
Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false.
There may be duplicates in the original array.
Example 1:
Input: nums = [3,4,5,1,2]
Output: true
Explanation: [1,2,3,4,5] is the original sorted array.
You can rotate the array by x = 3 positions to begin on the the element of value 3: [3,4,5,1,2].
Example 2:
Input: nums = [2,1,3,4]
Output: false
Explanation: There is no sorted array once rotated that can make nums.
*/
/*
APPROACH:-
Compare all neignbour elements (a,b) in A,
the case of a > b can happen at most once.
Note that the first element and the last element are also connected.
If all a <= b, A is already sorted so answer is true.
If all a <= b but only one a > b, and the first element is greater than equal to last element
we can rotate and make b the first element so answer is true.
Other case, return false.
*/
// CODE:-
bool check(vector<int> &nums)
{
int cnt = 0;
int n = nums.size();
for (int i = 0; i < n - 1; i++)
{
if (nums[i] > nums[i + 1])
cnt++;
}
if (cnt == 0)
return true;
else if (cnt == 1 && nums[0] >= nums[n - 1])
return true;
return false;
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(0)
/*
QUESTION:-
Given an array "ARR' containing 'N' elements, rotate this array Left by once means to shift all elements by one place to the left and move the first element to the last position in the array.
Example:
Input: 'N' 5, 'ARR' = [1, 2, 3, 4, 5]
Output: [2, 3, 4, 5, 1]
Explanation:
We moved the 2nd element to the 1st position and 3rd element to the 2nd position and 4th element to the 3rd position and 5th element to the 4th position and move oth element to the 5th position.
*/
/*
APPROACH:-
-> By observing we can the ans is the arr where arr[i] = arr[i+1] and at last place we will have arr[0]
-> Before traversing store the arr[0] in temp and then traverse the array and make arr[i] = arr[i+1]
-> Make arr[n-1] = arr[0], where n is the size of the array
*/
// CODE:-
vector<int> rotateArray(vector<int> &arr, int n)
{
int temp = arr[0];
for (int i = 0; i < n - 1; i++)
{
arr[i] = arr[i + 1];
}
arr[n - 1] = temp;
return arr;
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(0)
/*
QUESTION:-
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
*/
/*
APPROACH:-
To rotate the array k places to right follow below steps
-> Reverse first n-k elements
-> Reverse last k elements
-> Reverse the entire array
To rotate the array k places to left follow below steps
-> Reverse first k elements
-> Reverse last n-k elements
-> Reverse the entire array
*/
// CODE:-
// RIGHT ROATATE:-
void rightRotate(int arr[], int n, int k)
{
k = k % n; // to keep k within the range
reverse(arr, arr + (n - k));
reverse(arr + (n - k), arr + n);
reverse(arr, arr + n);
}
// LEFT ROATATE:-
void leftRotate(int arr[], int n, int k)
{
k = k % n; // to keep k within the range
reverse(arr, arr + k);
reverse(arr + k, arr + n);
reverse(arr, arr + n);
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(0)
/*
QUESTION:-
Union of two arrays can be defined as the common and distinct elements in the two arrays.
Given two sorted arrays of size n and m respectively, find their union.
Example 1:
Input:
n = 5, arr1[] = {1, 2, 3, 4, 5}
m = 3, arr2 [] = {1, 2, 3}
Output: 1 2 3 4 5
Explanation: Distinct elements including
both the arrays are: 1 2 3 4 5.
Example 2:
Input:
n = 5, arr1[] = {2, 2, 3, 4, 5}
m = 5, arr2[] = {1, 1, 2, 3, 4}
Output: 1 2 3 4 5
Explanation: Distinct elements including
both the arrays are: 1 2 3 4 5.
*/
/*
APPROACH:-
-> Take two pointer i and j where i is for arr1 and j is for arr2 and traverse
-> While travsersing 3 cases arises
-> arr1[ i ] == arr2[ j ]
Here we found a common element, so insert only one element in the union.
Let’s insert arr[i] in union and whenever we insert element we increment pointer while pointer is not equal to the inserted element
-> arr1[i]<arr2[j]
Here insert arr[i]
-> arr1[i]>arr2[j]
Here insert arr2[j]
-> Now check if elements of any array is left to traverse then traverse that array
*/
// CODE:-
vector<int> findUnion(int arr1[], int arr2[], int n, int m)
{
int i = 0; // i to keep track in arr1
int j = 0; // j to keep track in arr2
vector<int> ans;
while (i < n && j < m)
{
if (arr1[i] < arr2[j])
{
ans.push_back(arr1[i++]);
while (i < n && arr1[i] == arr1[i - 1])
i++;
}
else if (arr2[j] < arr1[i])
{
ans.push_back(arr2[j++]);
while (j < m && arr2[j] == arr2[j - 1])
j++;
}
// means arr1[i] = arr2[j] in that case we can insert anyone
else
{
ans.push_back(arr1[i++]);
j++;
while (i < n && arr1[i] == arr1[i - 1])
i++;
while (j < m && arr2[j] == arr2[j - 1])
j++;
}
}
while (i < n)
{
ans.push_back(arr1[i++]);
while (i < n && arr1[i] == arr1[i - 1])
i++;
}
while (j < m)
{
ans.push_back(arr2[j++]);
while (j < m && arr2[j] == arr2[j - 1])
j++;
}
return ans;
}
// TIME COMPLEXITY = O(N+M)
// SPACE COMPLEXITY = O(0)
Duplicates¶
/*
QUESTION:-
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.
Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:
Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
Return k.
Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
*/
/*
APPROACH:-
-> The idea, is to use keep a pointer k which signifies that upto here the array is sorted
-> Now travese the entire array and if arr[k]!=arr[j] that is arr[j] is a unique value hence it should be included
so increment the k and swap arr[k] with arr[j]
-> Return k+1, +1 is because of 0 based indexing
*/
// CODE:-
int removeDuplicates(vector<int> &nums)
{
int k = 0; // upto k array contains unique elements
for (int j = 1; j < nums.size(); j++)
{
if (nums[k] != nums[j])
{
k++;
swap(nums[k], nums[j]);
}
}
return k + 1;
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(0)
/*
QUESTION:-
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:
Input: nums = [0]
Output: [0]
*/
/*
APPROACH:-
-> The idea is while traversing the array if we found any zero then we have to swap it with next non-zero
*/
// CODE:-
// function to find the next non-zero element
int next_nonzero(vector<int> &a, int &j)
{
while (j < a.size())
{
if (a[j] != 0)
return j;
j++;
}
return -1;
}
void moveZeroes(vector<int> &nums)
{
int j = -1; // is to find the next non zero element
// i signifies that upto here all elements are non-zero
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] != 0)
continue;
if (j == -1)
j = i + 1;
int nxt_non0 = next_nonzero(nums, j);
if (nxt_non0 == -1)
return;
swap(nums[i], nums[nxt_non0]);
}
}
// TIME COMPLEXITY = O(N) (as we moving j throught the array only once)
// SPACE COMPLEXITY = O(0)
/*
QUESTION:-
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Example 2:
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
*/
/*
APPROACH:-
-> Calculate the optimum sum i.e. sum when all elements were present
-> Calculate the actual array's sum
-> Return the optimum sum - actual sum
*/
// CODE:-
int missingNumber(vector<int> &nums)
{
int n = nums.size();
long long optimum_sum = (n * (n + 1)) / 2; // the sum if no number is absent
long long actual_sum = 0;
for (auto it : nums)
{
actual_sum += it;
}
return optimum_sum - actual_sum;
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(0)
/*
QUESTION:
Given an unsorted array Arr of size N of positive integers. One number 'A' from set {1, 2,....,N} is missing and one number 'B' occurs twice in the array. Find these two numbers.
Example:
Input:
N = 2
Arr[] = {2, 2}
Output: 2 1
Explanation: Repeating number is 2 and the smallest positive missing number is 1.
APPROACH:
To find the missing and repeating numbers in the given unsorted array, we can utilize the properties of summation and sum of squares. Let's denote the missing number as 'x' and the repeating number as 'y'.
1. Calculate the optimal sum 'optSum' using the formula: optSum = N * (N + 1) / 2, where N is the size of the array.
2. Calculate the optimal sum of squares 'opt2Sum' using the formula: opt2Sum = N * (N + 1) * (2 * N + 1) / 6.
3. Calculate the actual sum 'actSum' and actual sum of squares 'act2Sum' of the given array.
4. Find the difference between the optimal sum and the actual sum: xMinusY = optSum - actSum.
5. Find the difference between the optimal sum of squares and the actual sum of squares: x2MinusY2 = opt2Sum - act2Sum.
6. Calculate the sum of 'x' and 'y': xPlusY = x2MinusY2 / xMinusY.
7. Calculate 'x' and 'y' using the equations: x = (xPlusY + xMinusY) / 2 and y = xPlusY - x.
CODE:
*/
vector<int> findTwoElement(vector<int> arr, int N) {
long long n = N;
long long optSum = n * (n + 1) / 2; // Sum if all elements are present once
long long opt2Sum = n * (n + 1) * (2 * n + 1) / 6; // Optimum sum of squares
long long actSum = 0; // Actual sum of the given array
long long act2Sum = 0; // Actual sum of squares
for (auto it : arr) {
actSum += it;
act2Sum += (long long)it * (long long)it;
}
long long xMinusY = optSum - actSum;
long long x2MinusY2 = opt2Sum - act2Sum;
long long xPlusY = x2MinusY2 / xMinusY;
long long x = (xPlusY + xMinusY) / 2;
long long y = xPlusY - x;
return {(int)y, (int)x};
}
/*
TIME COMPLEXITY: O(N), where N is the size of the array.
SPACE COMPLEXITY: O(1).
*/
Counting¶
/*
QUESTION:-
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
*/
/*
APPROACH:-
-> We can use XOR operation as we know xor cancles out the same elements
-> Intial xr=0 then traverse the entire array and xor each element with xr
-> Since only one element is present once and all other are present twice so the remaining element would be the
one which is present only once cause all other gets cancels out
*/
// CODE:-
int singleNumber(vector<int> &nums)
{
int xr = 0;
for (int i = 0; i < nums.size(); i++)
{
xr = nums[i] ^ xr;
}
return xr;
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(0)
/*
QUESTION:-
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Example 2:
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
*/
/*
APPROACH:-
-> Traverse the entire array and within it run a loop while element's are equal to 1 and store the count
-> Update the ans as max(ans,cnt)
*/
// CODE:-
int findMaxConsecutiveOnes(vector<int> &nums)
{
int ans = 0;
for (int i = 0; i < nums.size(); i++)
{
int cnt = 0; // to store the count of consecutive 1's
while (i < nums.size() && nums[i] == 1)
{
cnt++;
i++;
}
ans = max(ans, cnt);
}
return ans;
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(0)
/*
QUESTION:-
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
*/
/*
APPROACH:-
To find the length of the longest consecutive elements sequence, we can follow these steps:
1. Create a set to store all the elements of the array.
2. Iterate through the array and insert each element into the set.
3. For each element, check if its previous consecutive element (num-1) exists in the set. If it does not exist, it means the current element is the starting element of a sequence.
4. For each starting element, keep incrementing the current element (num+1) and checking if it exists in the set. This will help find the consecutive elements in the sequence.
5. Keep track of the maximum length of consecutive elements encountered.
6. Return the maximum length as the result.
*/
// CODE:
int longestConsecutive(vector<int> &nums)
{
unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); i++)
{
mp[nums[i]]++;
}
int ans = 0;
for (int i = 0; i < nums.size(); i++)
{
int start = nums[i];
// check whehter this can be the start of the subsequence
if (mp.find(nums[i] - 1) == mp.end())
{
int temp = 1;
int nxt = nums[i];
while (mp.find(nxt + 1) != mp.end())
{
temp++;
nxt++;
}
ans = max(ans, temp);
}
}
return ans;
}
// TIME COMPLEXITY: O(n), where n is the size of the input array.
// SPACE COMPLEXITY: O(n), as we are using a set to store the elements of the array.
/*
QUESTION:-
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.
*/
/*
APPROACH:-
-> Initialize two variables: maxSum and currentSum. Set both variables to the first element of the array.
-> Iterate through the array starting from the second element:
Update currentSum by adding the current element to it.
If currentSum becomes negative, reset it to 0. This step ensures that we consider only the subarrays with positive sums.
Update maxSum by taking the maximum value between maxSum and currentSum. This keeps track of the maximum subarray sum encountered so far.
-> After the iteration, the maxSum variable will hold the largest sum of any subarray.
-> Return the maxSum as the result.
*/
// CODE:-
int maxSubArray(vector<int> &nums)
{
int curr_sum = 0;
int ans = INT_MIN;
for (int i = 0; i < nums.size(); i++)
{
curr_sum += nums[i];
ans = max(ans, curr_sum);
if (curr_sum < 0)
curr_sum = 0;
}
return ans;
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(0)
/*
QUESTION:
Given an array of integers. Find the Inversion Count in the array.
Inversion Count: For an array, inversion count indicates how far (or close) the array is from being sorted. If the array is already sorted then the inversion count is 0. If an array is sorted in the reverse order then the inversion count is the maximum.
Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.
Example 1:
Input: N = 5, arr[] = {2, 4, 1, 3, 5}
Output: 3
Explanation: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).
Example 2:
Input: N = 5, arr[] = {2, 3, 4, 5, 6}
Output: 0
Explanation: As the sequence is already sorted, there is no inversion count.
APPROACH:
To find the inversion count in the array, we can utilize the merge sort algorithm. The idea is to divide the array into two halves, recursively count the inversions in each half, and then merge the two halves while counting the inversions across them.
CODE:
*/
long long int inv_cnt = 0;
long long int merge(long long start, long long mid, long long end, long long arr[]) {
long long leftsize = mid - start + 1;
long long rightsize = end - mid;
long long left[leftsize], right[rightsize];
for (long long i = 0; i < leftsize; i++) {
left[i] = arr[start + i];
}
for (long long i = 0; i < rightsize; i++) {
right[i] = arr[mid + 1 + i];
}
long long i = 0, j = 0, k = start;
while (i < leftsize && j < rightsize) {
if (left[i] > right[j]) {
inv_cnt += leftsize - i;
arr[k++] = right[j++];
} else {
arr[k++] = left[i++];
}
}
while (i < leftsize) {
arr[k++] = left[i++];
}
while (j < rightsize) {
arr[k++] = right[j++];
}
}
void mergesort(long long start, long long end, long long arr[]) {
if (start >= end)
return;
long long mid = start + (end - start) / 2;
mergesort(start, mid, arr);
mergesort(mid + 1, end, arr);
merge(start, mid, end, arr);
}
long long int inversionCount(long long arr[], long long N) {
mergesort(0, N - 1, arr);
return inv_cnt;
}
/*
TIME COMPLEXITY: O(N log N), where N is the size of the array.
SPACE COMPLEXITY: O(N).
*/
Merge¶
/*
QUESTION:
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals and return an array of non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
APPROACH:
To merge overlapping intervals, we can follow these steps:
1. Sort the intervals based on the start time.
2. Initialize a vector `ans` to store the merged intervals.
3. Add the first interval from the sorted intervals to the `ans` vector.
4. Iterate through the remaining intervals:
- If the start time of the current interval is less than or equal to the end time of the last interval in the `ans` vector, it means they overlap. Update the end time of the last interval in the `ans` vector if necessary.
- If the start time of the current interval is greater than the end time of the last interval in the `ans` vector, it means they don't overlap. Add the current interval to the `ans` vector.
5. Return the `ans` vector as the merged non-overlapping intervals.
CODE:
*/
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> ans;
ans.push_back(intervals[0]);
for(int i = 1; i < intervals.size(); i++){
if(ans.back()[1] >= intervals[i][0]){
ans.back()[1] = max(ans.back()[1], intervals[i][1]);
}
else{
ans.push_back(intervals[i]);
}
}
return ans;
}
/*
TIME COMPLEXITY: O(nlogn), where n is the number of intervals in the input.
The sorting step takes O(nlogn) time, and the merging step takes O(n) time.
Overall, the time complexity is dominated by the sorting step.
SPACE COMPLEXITY: O(n), where n is the number of intervals in the input.
We are using additional space to store the merged intervals in the `ans` vector.
*/
/*
QUESTION:
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
APPROACH:
To merge two sorted arrays, nums1 and nums2, into nums1, we can use a two-pointer approach.
1. Initialize three pointers: i, j, and k, where i points to the last valid element of nums1, j points to the last element of nums2, and k points to the last index of the merged array nums1.
2. Start from the end of the arrays and compare the elements at i and j.
3. If the element at nums1[i] is greater than the element at nums2[j], swap it with the element at nums1[k], decrement i and k.
4. Otherwise, swap the element at nums2[j] with the element at nums1[k], decrement j and k.
5. Repeat steps 3 and 4 until all elements in nums1 and nums2 have been merged.
6. If there are still elements remaining in nums2 after merging, copy them to the remaining positions in nums1.
CODE:
*/
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1; // Pointer for nums1
int j = n - 1; // Pointer for nums2
int k = m + n - 1; // Pointer for merged array nums1
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
swap(nums1[i], nums1[k]);
i--;
k--;
} else {
swap(nums2[j], nums1[k]);
j--;
k--;
}
}
// Copy remaining elements from nums2 to nums1 if any
while (j >= 0) {
swap(nums2[j], nums1[k]);
j--;
k--;
}
}
/*
TIME COMPLEXITY: O(m + n), where m and n are the lengths of nums1 and nums2 respectively.
The merging process requires iterating through both arrays once.
SPACE COMPLEXITY: O(1)
The merge is performed in-place without using any additional space.
*/
Sum¶
/*
QUESTION:-
You are given an array 'A' of size 'N' and an integer 'K'. You need to print the length of the longest subarray of array 'A' whose sum = 'K'.
Example:
Input: 'N' = 7 'K' = 3
'A' = [1, 2, 3, 1, 1, 1, 1]
Output: 3
Explanation: Subarrays whose sum = '3' are:
[1, 2], [3], [1, 1, 1], [1, 1, 1]
Here, the length of the longest subarray is 3, which is our final answer.
*/
/*
APPROACH:-
-> Use sliding window approach using two pointers start and end
-> Run a loop to traverse the entire array add from end and subtract from start when sum>k
-> If sum==k then, update the ans now, window size = end-start+1
*/
// CODE:-
int longestSubarrayWithSumK(vector<int> a, long long k)
{
int start = 0;
int ans = 0;
long long sum = 0;
int n = a.size();
for (int end = 0; end < n; end++)
{
sum += a[end];
while (sum > k)
{
sum -= a[start];
start++;
}
if (sum == k)
{
ans = max(ans, end - start + 1);
}
}
return ans;
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(0)
/*
QUESITON:-
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
*/
/*
Approach:
-> Create an empty map to store the elements and their corresponding indices.
> Iterate through the input array, nums, and for each element:
Calculate the complement by subtracting the current element from the target value.
Check if the complement exists in the map.
If the complement exists, return the indices of the current element and the complement.
If the complement does not exist, add the current element and its index to the map.
-> If no solution is found, return an empty vector or a message indicating no solution exists.
*/
// CODE:-
vector<int> twoSum(vector<int> &nums, int target)
{
unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); i++)
{
int remain = target - nums[i];
if (mp.find(remain) != mp.end() && mp[remain] != i)
return {i, mp[remain]};
mp[nums[i]] = i;
}
return {-1, -1};
// If the question asks to just return whether pair exists or not, not the indexes in that case we can sort and easily find the pair sum without extra space
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(N)
/*
QUESTION:
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Example:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + 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.
*/
/*
APPROACH:
To find all triplets that sum up to zero, we can follow these steps:
1. Sort the input array in non-decreasing order.
2. Iterate through the array and fix the first element as nums[k] (where k = 0 to n-1).
3. Use two pointers (i and j) to find the other two elements such that nums[i] + nums[j] = -nums[k].
4. Move the pointers accordingly to find all possible triplets.
5. Skip duplicate elements to avoid duplicate triplets.
6. Return the resulting triplets.
*/
vector<vector<int>> threeSum(vector<int> &nums)
{
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); k++)
{
int i = k + 1;
int j = nums.size() - 1;
int target = -nums[k];
while (i < j)
{
int sum = nums[i] + nums[j];
if (sum == target)
{
ans.push_back({nums[k], nums[i], nums[j]});
i++;
j--;
// Skip duplicate elements
while (i < j && nums[i] == nums[i - 1])
i++;
while (i < j && nums[j] == nums[j + 1])
j--;
}
else if (sum < target)
{
i++;
}
else
{
j--;
}
}
// Skip duplicate elements
while (k + 1 < nums.size() && nums[k + 1] == nums[k])
k++;
}
return ans;
}
/*
TIME COMPLEXITY: O(n^2), where n is the size of the input array.
The sorting step takes O(n log n), and the two-pointer traversal takes O(n^2) in the worst case.
Hence, the overall time complexity is O(n^2).
SPACE COMPLEXITY: O(1), as we are using a constant amount of extra space for storing the output and variables.
*/
/*
QUESTION:
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
- 0 <= a, b, c, d < n
- a, b, c, and d are distinct.
- nums[a] + nums[b] + nums[c] + nums[d] == target
Example:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
APPROACH:
To find the unique quadruplets that sum up to the target, we can use a similar approach as the threeSum problem. We will fix two elements (nums[a] and nums[b]) and use two pointers to find the remaining two elements (nums[c] and nums[d]) that sum up to the target.
1. Sort the input array nums in ascending order.
2. Iterate through the array with two pointers: a and b.
3. For each pair of elements nums[a] and nums[b], use two pointers c and d to find the remaining two elements that sum up to the target.
- Initialize c as b + 1 and d as the last index of the array.
- Calculate the target sum as trgt = target - (nums[a] + nums[b]).
- While c < d, compare the sum of nums[c] and nums[d] with the target sum.
- If the sum is equal to the target sum, we found a quadruplet. Add it to the answer and move the pointers c and d.
- Important: Skip any duplicate elements while moving c and d.
- If the sum is greater than the target sum, decrement d.
- If the sum is less than the target sum, increment c.
4. Skip any duplicate elements for pointers a and b to avoid duplicate quadruplets.
5. Return the answer array containing unique quadruplets.
CODE:
*/
vector<vector<int>> fourSum(vector<int> &nums, int target)
{
vector<vector<int>> ans;
long long trgt = (long long)(target); // to handle overflow
sort(nums.begin(), nums.end());
for (int a = 0; a < nums.size(); a++)
{
for (int b = a + 1; b < nums.size(); b++)
{
if (a == b)
continue;
int c = b + 1;
int d = nums.size() - 1;
long long tar = trgt - (nums[a] + nums[b]);
while (c < d)
{
long long sum = nums[c] + nums[d];
if (sum == tar)
{
ans.push_back({nums[a], nums[b], nums[c], nums[d]});
c++;
d--;
// Skip duplicate elements
while (c < d && nums[c] == nums[c - 1])
c++;
while (c < d && nums[d] == nums[d + 1])
d--;
}
else if (sum > tar)
{
d--;
}
else
{
c++;
}
}
// Skip duplicate elements
while (b + 1 < nums.size() && nums[b + 1] == nums[b])
b++;
}
// Skip duplicate elements
while (a + 1 < nums.size() && nums[a + 1] == nums[a])
a++;
}
return ans;
}
/*
TIME COMPLEXITY: O(n^3), where n is the size of the input array nums.
SPACE COMPLEXITY: O(1), as we are using a constant amount of extra space.
*/
/*
QUESTION:
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
Example:
Input: nums = [1,1,1], k = 2
Output: 2
APPROACH:
To find the total number of subarrays with sum equal to k, we can use the technique of prefix sum along with a hashmap.
1. Initialize a variable `count` to keep track of the count of subarrays with sum equal to k.
2. Initialize a variable `prefixSum` to keep track of the prefix sum while iterating through the array.
3. Initialize a hashmap `sumCount` to store the frequency of prefix sums encountered so far.
4. Set the initial prefix sum to 0 and set its count to 1 in the `sumCount` hashmap.
5. Iterate through the array and update the prefix sum by adding each element.
6. Check if the current prefix sum minus k exists in the `sumCount` hashmap. If it does, add the count of that prefix sum to the `count` variable.
7. Increment the count of the current prefix sum in the `sumCount` hashmap.
8. Finally, return the `count` variable as the total number of subarrays with sum equal to k.
CODE:
*/
int subarraySum(vector<int> &nums, int k)
{
int pref_sum = 0;
unordered_map<int, int> mp;
int ans = 0;
for (int i = 0; i < nums.size(); i++)
{
pref_sum += nums[i];
if (pref_sum == k)
ans++;
if (mp.find(pref_sum - k) != mp.end())
{
ans += mp[pref_sum - k];
}
mp[pref_sum]++;
}
return ans;
}
/*
TIME COMPLEXITY: O(n), where n is the size of the input array nums.
SPACE COMPLEXITY: O(n), as we are using a hashmap to store the prefix sums and their corresponding counts.
*/
/*
QUESTION:
Given an array with both positive and negative integers, we need to compute the length of the largest subarray with a sum of 0.
Example:
Input:
N = 8
A[] = {15, -2, 2, -8, 1, 7, 10, 23}
Output: 5
Explanation: The largest subarray with a sum of 0 will be -2, 2, -8, 1, 7.
APPROACH:
To find the length of the largest subarray with a sum of 0, we can use a technique called prefix sum.
1. Create a prefix sum array of the same size as the input array.
2. Initialize a map to store the prefix sum and its corresponding index. Initialize it with an entry for prefix sum 0 and index -1.
3. Iterate through the input array and calculate the prefix sum by adding each element.
4. For each prefix sum encountered, check if it exists in the map. If it does, update the answer by taking the maximum of the current answer and the difference between the current index and the index stored in the map for that prefix sum.
5. If the prefix sum is not found in the map, add it to the map with its corresponding index.
6. Finally, return the answer as the length of the largest subarray with a sum of 0.
CODE:
*/
int maxLen(vector<int> &A, int n)
{
unordered_map<int, int> mp;
mp[0] = -1;
int pref_sum = 0;
int ans = 0;
for (int i = 0; i < n; i++)
{
pref_sum += A[i];
if (mp.find(pref_sum) != mp.end())
{
ans = max(ans, i - mp[pref_sum]);
}
else
{
mp[pref_sum] = i;
}
}
return ans;
}
/*
TIME COMPLEXITY: O(n), where n is the size of the input array A.
SPACE COMPLEXITY: O(n), as we are using a map to store the prefix sums and their corresponding indices.
*/
/*Question:
Given an array containing N integers and an integer K, find the length of the longest subarray with the sum of the elements equal to K.
Example:
Input:
A[] = {10, 5, 2, 7, 1, 9}
K = 15
Output:
4
Explanation:
The sub-array is {5, 2, 7, 1}.
Approach:
To solve this problem, we can use a prefix sum approach along with a hashmap to keep track of the prefix sums encountered so far. We iterate through the array and maintain a prefix sum variable. At each index, we check if the prefix sum equals K, in which case we update the maximum length of the subarray found so far. Additionally, we check if the current prefix sum minus K exists in the hashmap. If it does, it means there is a subarray between the previous occurrence of the prefix sum minus K and the current index that sums up to K. We update the maximum length accordingly. We store the prefix sums and their corresponding indices in the hashmap.
Code:
*/
int lenOfLongSubarr(int A[], int N, int K) {
int pref_sum = 0;
int ans = 0;
unordered_map<int, int> mp;
for (int i = 0; i < N; i++) {
pref_sum += A[i];
if (pref_sum == K)
ans = max(ans, i + 1);
if (mp.find(pref_sum - K) != mp.end())
ans = max(ans, i - mp[pref_sum - K]);
if (mp.find(pref_sum) == mp.end())
mp[pref_sum] = i;
}
return ans;
}
/*
Time Complexity: The code iterates through the array once, resulting in a time complexity of O(N), where N is the size of the array.
Space Complexity: The code uses an unordered map to store the prefix sums and their corresponding indices. In the worst case, all elements of the array could be distinct, leading to a space complexity of O(N) to store the prefix sums in the map.
*/
Product¶
/*QUESTION:
Given an integer array nums, find a subarray that has the largest product, and return the product.
Example:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
APPROACH:
To find the subarray with the largest product, we iterate through the array while keeping track of the current product. We maintain two variables: `ans` to store the maximum product found so far and `prdct` to store the current product. Since negative numbers can change the sign and potentially result in a larger product, we run the loop twice, once from left to right and once from right to left.
CODE:*/
int maxProduct(vector<int>& nums) {
int ans = INT_MIN;
int prdct = 1;
// Iterate from left to right
for (int i = 0; i < nums.size(); i++) {
prdct = prdct * nums[i];
ans = max(ans, prdct);
if (prdct == 0)
prdct = 1;
}
prdct = 1;
// Iterate from right to left
for (int i = nums.size() - 1; i >= 0; i--) {
prdct = prdct * nums[i];
ans = max(ans, prdct);
if (prdct == 0)
prdct = 1;
}
return ans;
}
/*
TIME COMPLEXITY: O(N), where N is the size of the input array.
SPACE COMPLEXITY: O(1).
*/
/*
QUESTION:-
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 0, 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]
*/
/*
APPROACH:-
-> Initialize three pointers: low at the beginning of the array, mid at the beginning of the array, and high at the end of the array.
-> Iterate through the array while the mid pointer is less than or equal to the high pointer:
1. If the current element at the mid pointer is 0 (red), we swap it with the element at the low pointer and increment both low and mid pointers. This ensures that red elements are moved to the left side of the array.
2. If the current element at the mid pointer is 1 (white), we simply increment the mid pointer. This keeps white elements in the middle of the array.
3. If the current element at the mid pointer is 2 (blue), we swap it with the element at the high pointer and decrement the high pointer. This ensures that blue elements are moved to the right side of the array.
Repeat step 2 until the mid pointer crosses the high pointer.
At the end of the algorithm, the array will be sorted in the desired order.
*/
// CODE:-
void sortColors(vector<int> &nums)
{
int low = 0, mid = 0, high = nums.size() - 1;
while (mid <= high)
{
if (nums[mid] == 0)
swap(nums[mid++], nums[low++]);
else if (nums[mid] == 1)
mid++;
else
swap(nums[mid], nums[high--]);
}
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(0)
Arrangement¶
/*
QUESTION:-
You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.
You should rearrange the elements of nums such that the modified array follows the given conditions:
Every consecutive pair of integers have opposite signs.
For all integers with the same sign, the order in which they were present in nums is preserved.
The rearranged array begins with a positive integer.
Return the modified array after rearranging the elements to satisfy the aforementioned conditions.
Example 1:
Input: nums = [3,1,-2,-5,2,-4]
Output: [3,-2,1,-5,2,-4]
Explanation:
The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4].
The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].
Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.
*/
/*
APPROACH:-
Initialize two pointers, pos_ptr and neg_ptr. pos_ptr will point to the first positive integer in the array, and neg_ptr will point to the first negative integer in the array.
Iterate over the array.
If the current integer is positive, swap it with the element at neg_ptr.
Increment pos_ptr by 1.
Increment neg_ptr by 1.
Repeat steps 3-5 until the end of the array is reached.
The array will now be rearranged such that every consecutive pair of integers have opposite signs.
*/
// CODE:-
vector<int> rearrangeArray(vector<int> &nums)
{
int i = 0; // for +ve integers
int j = 1; // for -ve integers
vector<int> ans(nums.size());
for (int k = 0; k < nums.size(); k++)
{
if (nums[k] >= 0)
{
ans[i] = nums[k];
i += 2;
}
else
{
ans[j] = nums[k];
j += 2;
}
}
return ans;
}
// TIME COMPLEXITY = O(N)
// SPACE COMPLEXITY = O(0)
/*
QUESTION:-
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].
The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory.
Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]
*/
/*
APPROACH:-
To find the next permutation of an array, we can follow these steps:
1. Find the first index `i` from the right such that `nums[i] < nums[i+1]`. This is the first element that needs to be swapped.
2. Find the first index `j` from the right such that `nums[j] > nums[i]`. This is the element that will replace `nums[i]`.
3. Swap `nums[i]` and `nums[j]`.
4. Reverse the subarray starting from `i+1` till the end of the array.
5. If step 1 does not find any index `i`, it means the array is in descending order. In that case, reverse the entire array to get the lowest possible order.
*/
// CODE:
void nextPermutation(vector<int> &nums)
{
int bp = -1;
// finding the break point
for (int i = nums.size() - 2; i >= 0; i--)
{
if (nums[i] < nums[i + 1])
{
bp = i;
break;
}
}
// first greater element from back
if (bp != -1)
{
for (int i = nums.size() - 1; i >= 0; i--)
{
if (nums[i] > nums[bp])
{
swap(nums[i], nums[bp]);
break;
}
}
}
// reverse the array from bp+1 to end
reverse(nums.begin() + bp + 1, nums.end());
}
// TIME COMPLEXITY: O(n), where n is the size of the input array.
// SPACE COMPLEXITY: O(1)
/*
QUESTION:
Given an integer array nums, return the number of reverse pairs in the array.
A reverse pair is a pair (i, j) where:
0 <= i < j < nums.length and
nums[i] > 2 * nums[j].
Example:
Input: nums = [1,3,2,3,1]
Output: 2
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1
APPROACH:
To solve this problem, we can use the merge sort algorithm. While merging the two sorted subarrays, we can count the number of reverse pairs.
1. Define a variable 'rev_pair' to store the count of reverse pairs.
2. Implement the 'merge' function to merge two subarrays and count the reverse pairs.
3. Implement the 'mergesort' function to recursively divide the array into subarrays and perform merge sort.
4. Initialize 'rev_pair' to 0 and call the 'mergesort' function on the given array.
5. Return the 'rev_pair' as the result.
CODE:
*/
int rev_pair = 0;
void merge(int start, int mid, int end, vector<int>& nums){
int left_size = mid - start + 1;
int right_size = end - mid;
vector<int> left(left_size);
vector<int> right(right_size);
for(int i = 0; i < left_size; i++){
left[i] = nums[start + i];
}
for(int i = 0; i < right_size; i++){
right[i] = nums[mid + 1 + i];
}
// main logic resides here
int m = 0;
for(int i = 0; i < left_size; i++){
while(m < right_size && left[i] > (long long)2 * right[m]){
m++;
}
rev_pair += m;
}
int i = 0, j = 0, k = start;
while(i < left_size && j < right_size){
if(left[i] > right[j]){
nums[k++] = right[j++];
}
else{
nums[k++] = left[i++];
}
}
while(i < left_size){
nums[k++] = left[i++];
}
while(j < right_size){
nums[k++] = right[j++];
}
}
void mergesort(int start, int end, vector<int>& nums){
if(start >= end)
return;
int mid = start + (end - start) / 2;
mergesort(start, mid, nums);
mergesort(mid + 1, end, nums);
merge(start, mid, end, nums);
}
int reversePairs(vector<int>& nums) {
rev_pair = 0;
mergesort(0, nums.size() - 1, nums);
return rev_pair;
}
/*
TIME COMPLEXITY: O(n log n), where n is the size of the array.
SPACE COMPLEXITY: O(n), where n is the size of the array.
*/
/*
QUESTION:-
Given an array A of positive integers. Your task is to find the leaders in the array. An element of the array is a leader if it is greater than or equal to all the elements to its right side. The rightmost element is always a leader.
Example 1:
Input:
n = 6
A[] = {16,17,4,3,5,2}
Output: 17 5 2
Explanation: The first leader is 17 as it is greater than all the elements to its right. Similarly, the next leader is 5. The rightmost element is always a leader, so it is also included.
*/
/*
APPROACH:-
To find the leaders in the array, we can follow these steps:
1. Initialize a variable `maxRight` with the rightmost element of the array.
2. Iterate the array from right to left:
- If the current element is greater than or equal to `maxRight`, it is a leader. Print the current element and update `maxRight` to the current element.
3. Finally, print `maxRight` as it is always a leader.
*/
// CODE:
vector<int> leaders(int a[], int n)
{
vector<int> ans;
ans.push_back(a[n - 1]);
int maxi = a[n - 1]; // represent maximum encountered till now
for (int i = n - 2; i >= 0; i--)
{
if (a[i] >= maxi)
{
ans.push_back(a[i]);
maxi = a[i];
}
}
reverse(ans.begin(), ans.end());
return ans;
}
// TIME COMPLEXITY: O(n), where n is the size of the array.
// SPACE COMPLEXITY: O(1)
Matrix¶
/*
QUESTION:
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.
Example 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Example 2:
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]]
APPROACH:
To solve this problem in-place, we can follow these steps:
1. Use two boolean variables, firstRowZero and firstColZero, to check if the first row and first column contain zeros initially.
2. Iterate through the matrix and if an element is zero, set the corresponding element in the first row and first column to zero.
3. Iterate through the matrix again, excluding the first row and first column. If an element in the first row or first column is zero, set the current element to zero.
4. Finally, based on the values in firstRowZero and firstColZero, set the first row and first column to zero if needed.
TIME COMPLEXITY: O(m * n), where m and n are the dimensions of the matrix.
SPACE COMPLEXITY: O(1), as we are using constant extra space.
*/
// CODE:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
bool firstRowZero = false;
bool firstColZero = false;
// Check if the first row contains zero
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowZero = true;
break;
}
}
// Check if the first column contains zero
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}
// Mark zeros in the first row and column
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// Set rows to zero
for (int i = 1; i < m; i++) {
if (matrix[i][0] == 0) {
for (int j = 1; j < n; j++) {
matrix[i][j] = 0;
}
}
}
// Set columns to zero
for (int j = 1; j < n; j++) {
if (matrix[0][j] == 0) {
for (int i = 1; i < m; i++) {
matrix[i][j] = 0;
}
}
}
// Set first row to zero
if (firstRowZero) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
// Set first column to zero
if (firstColZero) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
// TIME COMPLEXITY: O(m * n), where m and n are the dimensions of the matrix.
// SPACE COMPLEXITY: O(1), as we are using constant extra space.
/*
QUESTION:-
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2:
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
*/
/*
APPROACH:-
To rotate the image by 90 degrees clockwise in-place, we can follow these steps:
1. Transpose the matrix: Iterate over the matrix and swap each element (i, j) with its corresponding element (j, i). This step transforms rows into columns.
2. Reverse each row: Iterate over each row in the transposed matrix and reverse the elements. This step ensures the rotation in a clockwise direction.
*/
// CODE:
void rotate(vector<vector<int>>& matrix) {
// Transpose the matrix
int n = matrix.size();
int m = matrix[0].size();
for(int i=0; i<n; i++){
// note here we move
for(int j=0; j<i; j++){
swap(matrix[i][j],matrix[j][i]);
}
}
// Reverse each row
for(int i=0; i<n; i++){
reverse(matrix[i].begin(),matrix[i].end());
}
}
// TIME COMPLEXITY = O(N^2), where N is the size of the matrix.
// SPACE COMPLEXITY = O(1)
/*
QUESTION:-
Given an m x n matrix, return all elements of the matrix in spiral order.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
*/
/*
APPROACH:-
To traverse the matrix in a spiral order, we can use the following steps:
1. Initialize four variables: top, bottom, left, and right to keep track of the boundaries of the current spiral.
2. Create an empty vector called 'ans' to store the elements in spiral order.
3. While the top boundary is less than or equal to the bottom boundary and the left boundary is less than or equal to the right boundary:
- Traverse the top row from left to right and add each element to 'ans'.
- Increment the top boundary.
- Traverse the right column from top to bottom and add each element to 'ans'.
- Decrement the right boundary.
- Check if the top boundary is still less than or equal to the bottom boundary:
- Traverse the bottom row from right to left and add each element to 'ans'.
- Decrement the bottom boundary.
- Check if the left boundary is still less than or equal to the right boundary:
- Traverse the left column from bottom to top and add each element to 'ans'.
- Increment the left boundary.
4. Return the 'ans' vector containing all the elements in spiral order.
*/
// CODE:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
int top = 0, bottom = n - 1;
int left = 0, right = m - 1;
vector<int> ans;
while (top <= bottom && left <= right) {
// Traverse top row
for (int i = left; i <= right; i++) {
ans.push_back(matrix[top][i]);
}
top++;
// Traverse right column
for (int i = top; i <= bottom; i++) {
ans.push_back(matrix[i][right]);
}
right--;
// Traverse bottom row
if (top <= bottom) {
for (int i = right; i >= left; i--) {
ans.push_back(matrix[bottom][i]);
}
bottom--;
}
// Traverse left column
if (left <= right) {
for (int i = bottom; i >= top; i--) {
ans.push_back(matrix[i][left]);
}
left++;
}
}
return ans;
}
// TIME COMPLEXITY: O(N), where N is the total number of elements in the matrix.
// SPACE COMPLEXITY: O(1)
Hard¶
/*
**Question:**
Given an integer `rowIndex`, return the `rowIndex`th (0-indexed) row of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it.
Example:
Input: `rowIndex = 3`
Output: `[1, 3, 3, 1]`
*/
/*
**APPROACH:**
To generate the `rowIndex`th row of Pascal's triangle, we can use the property that each number is the sum of the two numbers directly above it. We start with the base case of the first row, which is `[1]`. Then, for each subsequent row, we calculate the elements using the formula `C(n, k) = C(n-1, k-1) * (n-k+1) / k`, where `C(n, k)` represents the binomial coefficient.
**CODE:**
*/
vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex + 1, 1); // Initialize the row with 1s
long long coefficient = 1;
for (int col = 1; col <= rowIndex; col++) {
coefficient = coefficient * (rowIndex - col + 1) / col;
row[col] = coefficient;
}
return row;
}
/*
**COMPLEXITY ANALYSIS:**
- Time Complexity: O(rowIndex)
- We iterate over each element in the row and calculate its value using the binomial coefficient formula.
- Space Complexity: O(rowIndex)
- We use additional space to store the row of Pascal's triangle.
Overall, the algorithm has a linear time complexity and linear space complexity.
*/
/*
QUESTION:
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Example 1:
Input: nums = [3,2,3]
Output: [3]
Example 2:
Input: nums = [1]
Output: [1]
APPROACH:
To find all elements that appear more than ⌊ n/3 ⌋ times, we can use the Boyer-Moore Majority Vote algorithm. This algorithm helps us find potential candidates that could appear more than ⌊ n/3 ⌋ times in a single pass. After finding the candidates, we count their occurrences and return the elements that meet the criteria.
1. Initialize two candidate variables, c1 and c2, and their corresponding vote counters, vote1 and vote2.
2. Iterate through the array:
- If the current element matches c1, increment vote1.
- Else if the current element matches c2, increment vote2.
- Else if vote1 is 0, assign the current element to c1 and set vote1 to 1.
- Else if vote2 is 0, assign the current element to c2 and set vote2 to 1.
- Else, decrement both vote1 and vote2.
3. After finding the potential candidates, count the occurrences of each candidate using cnt1 and cnt2.
4. If cnt1 is greater than ⌊ n/3 ⌋, add c1 to the result vector.
5. If cnt2 is greater than ⌊ n/3 ⌋ and c2 is different from c1, add c2 to the result vector.
6. Return the result vector containing the elements that appear more than ⌊ n/3 ⌋ times.
*/
vector<int> majorityElement(vector<int> &nums)
{
int c1 = 0, c2 = 0, vote1 = 0, vote2 = 0;
// Finding potential candidates
for (int i = 0; i < nums.size(); i++)
{
if (c1 == nums[i])
{
vote1++;
}
else if (c2 == nums[i])
{
vote2++;
}
else if (vote1 == 0)
{
c1 = nums[i];
vote1 = 1;
}
else if (vote2 == 0)
{
c2 = nums[i];
vote2 = 1;
}
else
{
vote1--;
vote2--;
}
}
vector<int> ans;
int cnt1 = 0, cnt2 = 0;
// Counting occurrences of potential candidates
for (auto it : nums)
{
if (it == c1)
{
cnt1++;
}
if (it == c2)
{
cnt2++;
}
}
// Checking if candidates appear more than ⌊ n/3 ⌋ times
if (cnt1 > nums.size() / 3)
{
ans.push_back(c1);
}
if (cnt2 > nums.size() / 3 && c2 != c1)
{
ans.push_back(c2);
}
return ans;
}
// TIME COMPLEXITY: O(n), where n is the size of the input array.
// SPACE COMPLEXITY: O(1), as we are using a constant amount of extra space.
/*QUESTION:
Given an array 'A' consisting of 'N' integers and an integer 'B', find the number of subarrays of array 'A' whose bitwise XOR of all elements is equal to 'B'.
Example:
Input: 'N' = 4, 'B' = 2
'A' = [1, 2, 3, 2]
Output: 3
Explanation: Subarrays have bitwise xor equal to '2' are: [1, 2, 3, 2], [2], [2].
APPROACH:
To find the number of subarrays with bitwise XOR equal to B, we can use the technique of prefix XOR along with a hashmap.
1. Initialize a variable `prefixXOR` to keep track of the prefix XOR while iterating through the array.
2. Initialize a variable `count` to keep track of the count of subarrays with XOR equal to B.
3. Initialize a hashmap `xorCount` to store the frequency of prefix XOR values encountered so far.
4. Set the initial prefix XOR to 0 and set its count to 1 in the `xorCount` hashmap.
5. Iterate through the array and update the prefix XOR by XOR-ing each element.
6. Check if the current prefix XOR is equal to B. If it is, increment the `count` variable.
7. Check if the XOR of the current prefix XOR with B exists in the `xorCount` hashmap. If it does, add the count of that XOR value to the `count` variable.
8. Increment the count of the current prefix XOR in the `xorCount` hashmap.
9. Finally, return the `count` variable as the number of subarrays with XOR equal to B.
CODE:
*/
int subarraysWithSumK(vector<int> a, int b) {
int pref_xr = 0;
int ans = 0;
unordered_map<int, int> mp;
for(int i = 0; i < a.size(); i++){
pref_xr = pref_xr ^ a[i];
if(pref_xr == b)
ans++;
if(mp.find(pref_xr ^ b) != mp.end()){
ans += mp[pref_xr ^ b];
}
mp[pref_xr]++;
}
return ans;
}
/*
TIME COMPLEXITY: O(n), where n is the size of the input array a.
SPACE COMPLEXITY: O(n), as we are using a hashmap to store the prefix XOR values and their corresponding counts.
*/