Binary Search¶
1D Arrays¶
Basic Search¶
/*
QUESTION:-
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.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: The target value 9 exists in the nums array, and its index is 4.
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: The target value 2 does not exist in the nums array, so return -1.
*/
/*
APPROACH:-
1. Initialize low as 0 and high as the last index of the array.
2. Iterate using a while loop until low is less than or equal to high.
3. Calculate the middle index using the formula mid = low + (high - low) / 2.
4. Compare the target value with the element at the middle index:
- If they are equal, return the middle index.
- If the target is less than the element, update high to mid - 1 and continue the search in the left half.
- If the target is greater than the element, update low to mid + 1 and continue the search in the right half.
5. If the target is not found, return -1.
*/
//CODE:-
int search(vector<int>& nums, int target) {
int low = 0, high = nums.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] > target)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
// TIME COMPLEXITY: O(log n)
// - The algorithm divides the search space in half at each step, resulting in a logarithmic time complexity.
// SPACE COMPLEXITY: O(1)
// - The algorithm uses a constant amount of extra space for the variables.
/*
QUESTION:
Given a sorted array arr[] of size N without duplicates, and given a value x. Floor of x is defined as the largest element K in arr[] such that K is smaller than or equal to x. Find the index of K (0-based indexing).
Example 1:
Input:
N = 7, x = 0
arr[] = {1,2,8,10,11,12,19}
Output: -1
Explanation: No element less than 0 is found. So the output is "-1".
Example 2:
Input:
N = 7, x = 5
arr[] = {1,2,8,10,11,12,19}
Output: 1
Explanation: Largest number less than 5 is 2 (i.e K = 2), whose index is 1 (0-based indexing).
APPROACH:
- Initialize low as 0 and high as N-1.
- Iterate using a while loop until low is less than or equal to high.
- Calculate the mid index using mid = low + (high - low) / 2.
- Check if the element at mid index is less than or equal to x.
- If true, update the answer as mid and move the low pointer to mid+1 to search for a larger element.
- If false, update the high pointer to mid-1 to search in the lower half of the array.
- Finally, return the answer.
CODE:
*/
int findFloor(vector<long long> v, long long n, long long x) {
long long low = 0, high = n - 1;
int ans = -1;
while (low <= high) {
long long mid = low + (high - low) / 2;
if (v[mid] <= x) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
}
// TIME COMPLEXITY: O(log N)
// SPACE COMPLEXITY: O(1)
/*
QUESTION:
Given an unsorted array Arr[] of N integers and an integer X, find floor and ceiling of X in Arr[0..N-1].
Floor of X is the largest element which is smaller than or equal to X. Floor of X doesn’t exist if X is smaller than the smallest element of Arr[].
Ceil of X is the smallest element which is greater than or equal to X. Ceil of X doesn’t exist if X is greater than the greatest element of Arr[].
Example:
Input:
N = 8, X = 7
Arr[] = {5, 6, 8, 9, 6, 5, 5, 6}
Output: 6 8
Explanation:
Floor of 7 is 6 and ceil of 7 is 8.
APPROACH:
1. Sort the array in ascending order.
2. Use binary search to find the floor and ceil values.
3. The floor value is the largest element smaller than or equal to X, and the ceil value is the smallest element greater than or equal to X.
4. If the floor or ceil values are not found, set them to -1.
CODE:
*/
int lowerbound(int arr[], int n, int x){
int low = 0, high = n-1;
int ans = -1;
while(low<=high){
int mid = low+(high-low)/2;
if(arr[mid]<=x){
ans = mid;
low = mid+1;
}
else{
high = mid-1;
}
}
if(ans!=-1) ans = arr[ans];
return ans;
}
int upperbound(int arr[], int n, int x){
int low = 0, high = n-1;
int ans = -1;
while(low<=high){
int mid = low+(high-low)/2;
if(arr[mid]>=x){
ans = mid;
high = mid-1;
}
else{
low = mid+1;
}
}
if(ans!=-1) ans = arr[ans];
return ans;
}
pair<int, int> getFloorAndCeil(int arr[], int n, int x) {
sort(arr,arr+n);
int Floor = lowerbound(arr,n,x);
int Ceil = upperbound(arr,n,x);
return {Floor,Ceil};
}
// TIME COMPLEXITY: O(NlogN)
// SPACE COMPLEXITY: O(1)
/*
QUESTION:
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 O(log n) runtime complexity.
Example:
Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1
*/
/*
APPROACH:
We can use the lower_bound function from the C++ standard library to find the index where the target should be inserted. The lower_bound function returns an iterator pointing to the first element that is not less than the target. By subtracting the beginning iterator from the lower_bound iterator, we get the index where the target should be inserted.
CODE:
*/
int searchInsert(vector<int>& nums, int target) {
auto ans = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
return ans;
}
// TIME COMPLEXITY: O(log n) due to the use of lower_bound function
// SPACE COMPLEXITY: O(1)
/*
QUESTION:
Given an array arr[] of size N, check if it is sorted in non-decreasing order or not.
APPROACH:
- We can use a recursive approach to check if the array is sorted in non-decreasing order or not.
- The base case for recursion is when the subarray has only one element or when the subarray is empty, in which case we consider it to be sorted.
- For a non-empty subarray, we compare the middle element with its next element. If they are in non-decreasing order and both the left and right subarrays are also sorted, then we consider the entire array to be sorted.
- We recursively check the left and right subarrays using the same approach.
- If any of the recursive calls returns false, we return false. Otherwise, we return true.
Example:
Input:
N = 5
arr[] = {10, 20, 30, 40, 50}
Output: 1
Explanation: The given array is sorted.
CODE:
*/
bool solve(int arr[], int low, int high) {
if (low >= high)
return true;
int mid = low + (high - low) / 2;
if (arr[mid] <= arr[mid + 1] && solve(arr, low, mid) && solve(arr, mid + 1, high))
return true;
return false;
}
bool arraySortedOrNot(int arr[], int n) {
return solve(arr, 0, n - 1);
}
// TIME COMPLEXITY: O(log N)
// SPACE COMPLEXITY: O(log N) (for recursion stack)
Rotated Arrays¶
/*
QUESTION:
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 O(log n) runtime complexity.
Example:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
APPROACH:
1. Use lower_bound to find the index of the first occurrence of the target in the array.
2. If the target is not found, return [-1, -1].
3. Use upper_bound to find the index of the last occurrence of the target in the array.
4. Return the range [first, last-1] as the starting and ending positions.
CODE:
*/
vector<int> searchRange(vector<int>& nums, int target) {
int first = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
// if the target is not found, return [-1, -1]
if (first == nums.size() || nums[first] != target)
return {-1, -1};
int last = upper_bound(nums.begin(), nums.end(), target) - nums.begin();
return {first, last-1};
}
// TIME COMPLEXITY: O(log n)
// SPACE COMPLEXITY: O(1)
/*
QUESTION:
Given a sorted array Arr of size N and a number X, you need to find the number of occurrences of X in Arr.
Example:
Input:
N = 7, X = 2
Arr[] = {1, 1, 2, 2, 2, 2, 3}
Output: 4
Explanation: 2 occurs 4 times in the given array.
Example 2:
Input:
N = 7, X = 4
Arr[] = {1, 1, 2, 2, 2, 2, 3}
Output: 0
Explanation: 4 is not present in the given array.
*/
/*
APPROACH:
1. Use binary search to find the first occurrence of the target element.
2. Use binary search to find the last occurrence of the target element.
3. Return the difference between the indices of the first and last occurrence + 1.
CODE:
*/
int countOccurrences(int arr[], int n, int x) {
int first = lower_bound(arr, arr + n, x) - arr;
if (first == n || arr[first] != x)
return 0;
int last = upper_bound(arr, arr + n, x) - arr;
return last - first;
}
// TIME COMPLEXITY: O(log N), where N is the size of the array.
// SPACE COMPLEXITY: O(1).
/*
QUESTION:-
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 O(log n) time.
Example 1:
Input: nums = [1,2,3,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.
*/
/*
APPROACH:-
We can use the binary search approach to find the peak element.
1. Initialize low = 0 and high = n-1, where n is the size of the array.
2. While low < high, calculate mid = low + (high - low) / 2.
3. If nums[mid] < nums[mid+1], it means a peak element exists on the right side of mid, so update low = mid+1.
4. Otherwise, a peak element exists on the left side of mid or mid itself is a peak, so update high = mid.
5. After the loop ends, low will be pointing to the peak element index.
6. Return low as the result.
CODE:-
*/
int findPeakElement(vector<int>& nums) {
int low = 0, high = nums.size()-1;
while(low < high){
int mid = low + (high - low) / 2;
if(nums[mid] < nums[mid+1])
low = mid+1;
else
high = mid;
}
return low;
}
// TIME COMPLEXITY: O(log n)
// SPACE COMPLEXITY: O(1)
/*
QUESTION:
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[0], 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 if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
*/
/*
APPROACH:
We can use the binary search approach to find the target element in the rotated sorted array.
1. Initialize low = 0 and high = nums.size() - 1, where nums is the input array.
2. Perform binary search using the while loop until low <= high.
3. Calculate mid = low + (high - low) / 2.
4. If nums[mid] is equal to the target, return mid.
5. Check if the left part of the array (nums[low] to nums[mid]) is sorted or the right part (nums[mid] to nums[high]) is sorted.
- If the left part is sorted:
- If the target is within the range of nums[low] and nums[mid], update high = mid - 1.
- Otherwise, update low = mid + 1.
- If the right part is sorted:
- If the target is within the range of nums[mid] and nums[high], update low = mid + 1.
- Otherwise, update high = mid - 1.
6. If the target is not found after the while loop, return -1.
CODE:
*/
int search(vector<int>& nums, int target) {
int low = 0, high = nums.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target)
return mid;
if (nums[low] <= nums[mid]) {
if (nums[low] <= target && target <= nums[mid])
high = mid - 1;
else
low = mid + 1;
} else {
if (nums[mid] <= target && target <= nums[high])
low = mid + 1;
else
high = mid - 1;
}
}
return -1;
}
// TIME COMPLEXITY: O(log n)
// SPACE COMPLEXITY: O(1)
/*
QUESTION:
There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).
Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].
Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.
You must decrease the overall operation steps as much as possible.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
*/
/*
APPROACH:
We can modify the standard binary search algorithm to search for the target element.
1. Initialize low = 0 and high = nums.size() - 1.
2. While low <= high, calculate mid = low + (high - low) / 2.
3. If nums[mid] equals the target, return true.
4. If nums[mid] is equal to nums[low], we are in a situation where we can't determine which part of the array is sorted.
In this case, we increment low and decrement high to skip the duplicate elements.
5. If the left part of the array from low to mid is sorted, check if the target lies within this range.
If so, update high = mid - 1. Otherwise, update low = mid + 1.
6. If the right part of the array from mid to high is sorted, check if the target lies within this range.
If so, update low = mid + 1. Otherwise, update high = mid - 1.
7. If the target is not found, return false.
CODE:
*/
bool search(vector<int>& nums, int target) {
int low = 0, high = nums.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target)
return true;
if (nums[mid] == nums[low] && nums[mid] == nums[high]) {
low++;
high--;
continue;
}
if (nums[low] <= nums[mid]) {
if (nums[low] <= target && target <= nums[mid])
high = mid - 1;
else
low = mid + 1;
} else {
if (nums[mid] <= target && target <= nums[high])
low = mid + 1;
else
high = mid - 1;
}
}
return false;
}
// TIME COMPLEXITY: O(log n)
// SPACE COMPLEXITY: O(1)
/*
QUESTION:
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] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
APPROACH:
We can use the binary search approach to find the minimum element.
1. Initialize low = 0 and high = n-1, where n is the size of the array.
2. While low < high, calculate mid = low + (high - low) / 2.
3. If nums[mid] > nums[high], it means the minimum element is on the right side of mid, so update low = mid+1.
4. Otherwise, the minimum element is on the left side of mid or mid itself, so update high = mid.
5. After the loop ends, low will be pointing to the minimum element index.
6. Return nums[low] as the result.
CODE:
*/
int findMin(vector<int>& nums) {
int low = 0, high = nums.size()-1;
while(low < high){
int mid = low + (high - low) / 2;
if(nums[mid] > nums[high])
low = mid+1;
else
high = mid;
}
return nums[low];
}
// TIME COMPLEXITY: O(log n)
// SPACE COMPLEXITY: O(1)
/*
QUESTION:
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.
APPROACH:
Since the array is sorted and every element appears exactly twice except for one element, we can use binary search to find the single element.
1. Initialize low = 0 and high = nums.size()-1, where nums is the input array.
2. While low < high, calculate mid = low + (high - low) / 2.
3. Check if mid is an even index (mid % 2 == 0).
- If nums[mid] is equal to nums[mid + 1], it means the single element is on the right side, so update low = mid + 1.
- Otherwise, the single element is on the left side, so update high = mid.
4. If mid is an odd index (mid % 2 == 1).
- If nums[mid] is not equal to nums[mid + 1], it means the single element is on the right side, so update low = mid + 1.
- Otherwise, the single element is on the left side, so update high = mid.
5. After the loop ends, low will be pointing to the single element.
6. Return nums[low] as the result.
CODE:
*/
int singleNonDuplicate(vector<int>& nums) {
int low = 0, high = nums.size() - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (mid % 2 == 0) {
if (nums[mid] == nums[mid + 1])
low = mid + 1;
else
high = mid;
} else {
if (nums[mid] != nums[mid + 1])
low = mid + 1;
else
high = mid;
}
}
return nums[low];
}
// TIME COMPLEXITY: O(log n)
// SPACE COMPLEXITY: O(1)
/*
QUESTION:
Given an ascending sorted rotated array Arr of distinct integers of size N. The array is right rotated K times. Find the value of K.
Example 1:
Input:
N = 5
Arr[] = {5, 1, 2, 3, 4}
Output: 1
Explanation: The given array is 5 1 2 3 4.
The original sorted array is 1 2 3 4 5.
We can see that the array was rotated
1 times to the right.
APPROACH:
To find the value of K, we can use binary search.
1. Initialize low = 0 and high = N-1, where N is the size of the array.
2. While low < high, calculate mid = low + (high - low) / 2.
3. Check if arr[mid] > arr[n-1].
- If true, it means the rotation point lies on the right side of mid, so update low = mid + 1.
- If false, it means the rotation point lies on the left side of mid or mid is the rotation point, so update high = mid.
4. After the loop ends, low will be pointing to the rotation point.
5. Return low as the value of K.
CODE:
*/
int findKRotation(int arr[], int n) {
int low = 0, high = n - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[n - 1])
low = mid + 1;
else
high = mid;
}
return low;
}
// TIME COMPLEXITY: O(log n)
// SPACE COMPLEXITY: O(1)
2D Arrays¶
/*
QUESTION:-
Given a boolean 2D array of n x m dimensions where each row is sorted. Find the 0-based index of the first row that has the maximum number of 1's.
Example 1:
Input:
N = 4 , M = 4
Arr[][] = {{0, 1, 1, 1},
{0, 0, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0}}
Output: 2
Explanation: Row 2 contains 4 1's (0-based indexing).
*/
/*
APPROACH:-
-> We can use two pointer i and j which indicates current row and col
-> As we know the matrix is row-wise sorted we can intilaize j=m-1 i.e. last col and i=0 i.e. first row
-> Now, the idea is we will keep moving left j while we occur 1 and if 0 is found we will check in next row
-> The last row where we encountered 1 will be our ans
{*0, *1, *1, *1}
{*0, 0, 1, 1}
out of matrix *{*1, 1, 1, 1} ---> ans
{0, 0, 0, 0}
*/
// CODE:-
int rowWithMax1s(vector<vector<int>> arr, int n, int m)
{
int j = m - 1;
int i = 0;
int ans = -1;
while (j >= 0 && i < n)
{
while (arr[i][j] == 1)
{
ans = i;
j--;
}
if (i < n)
i++;
}
return ans;
}
// TIME COMPLEXITY = O(N+M)
// SPACE COMPLEXITY = O(0)
/*
QUESTION:-
You are given an m x n integer matrix matrix with the following two properties:
Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.
You must write a solution in O(log(m * n)) time complexity.
Example 1:
Input: matrix = [[1,3,5,7]
[10,11,16,20]
[23,30,34,60]]
target = 3
Output: true
*/
/*
APPROACH:-
-> Since the array is sorted we can use binary search low = 0 and high = n*m-1 i.e. total number of elements
-> Value at mid position could be accessed by matrix[mid/m][mid%m]
-> Then, follow the traditional binary search
*/
// CODE:-
bool searchMatrix(vector<vector<int>> &matrix, int target)
{
int n = matrix.size();
int m = matrix[0].size();
int low = 0;
int high = n * m - 1;
while (low <= high)
{
int mid = low + (high - low) / 2;
int val = matrix[mid / m][mid % m];
if (val == target)
return true;
else if (val > target)
high = mid - 1;
else
low = mid + 1;
}
return false;
}
// TIME COMPLEXITY = O(log(M * N))
// SPACE COMPLEXITY = O(0)
/*
QUESTION:
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending order from left to right.
- Integers in each column are sorted in ascending order from top to bottom.
Example 1:
Input: matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
], target = 5
Output: true
Explanation: The element 5 is present in the matrix.
Example 2:
Input: matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
], target = 20
Output: false
Explanation: The element 20 is not present in the matrix.
APPROACH:
We can start the search from the top-right element or the bottom-left element and move towards the target element based on the properties of the matrix.
1. Initialize the current position to the top-right element (row = 0, col = n-1), where n is the number of columns in the matrix.
2. While the current position is within the matrix boundaries:
- If the current element is equal to the target, return true.
- If the current element is greater than the target, move left to the previous column.
- If the current element is less than the target, move down to the next row.
3. If the loop exits without finding the target, return false.
CODE:
*/
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row = 0, col = matrix[0].size() - 1;
while (row < matrix.size() && col >= 0) {
if (matrix[row][col] == target)
return true;
else if (matrix[row][col] > target)
col--;
else
row++;
}
return false;
}
/*
Time Complexity: The time complexity of this algorithm is O(m + n), where m is the number of rows and n is the number of columns in the matrix.
In the worst case, we may need to traverse through the entire row or column of the matrix.
Space Complexity: The space complexity is O(1) since we are using constant extra space.
*/
/*
QUESTION:
A peak element in a 2D grid is an element that is strictly greater than all of its adjacent neighbors to the left, right, top, and bottom.
Given a 0-indexed m x n matrix mat where no two adjacent cells are equal, find any peak element mat[i][j] and return the length 2 array [i,j].
You may assume that the entire matrix is surrounded by an outer perimeter with the value -1 in each cell.
You must write an algorithm that runs in O(m log(n)) or O(n log(m)) time.
Example 1:
Input: mat = [[1,4],[3,2]]
Output: [0,1]
Explanation: Both 3 and 4 are peak elements so [1,0] and [0,1] are both acceptable answers.
Example 2:
Input: mat = [[10,20,15],[21,30,14],[7,16,32]]
Output: [1,1]
Explanation: Both 30 and 32 are peak elements so [1,1] and [2,2] are both acceptable answers.
APPROACH:
- Perform a binary search on the columns of the matrix.
- Find the maximum element in each column and check if it is a peak element by comparing it with its adjacent elements.
- If it is a peak element, return its position [i, j].
TIME COMPLEXITY: O(m log(n)) or O(n log(m)) - Binary search is performed on the columns of the matrix.
SPACE COMPLEXITY: O(1) - Constant space is used.
CODE:
*/
int max_finder(vector<int>& row) {
int maxi = INT_MIN;
int ans = -1;
for (int i = 0; i < row.size(); i++) {
if (row[i] > maxi) {
maxi = row[i];
ans = i;
}
}
return ans;
}
vector<int> findPeakGrid(vector<vector<int>>& mat) {
int n = mat.size();
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int col = max_finder(mat[mid]);
if ((mid == 0 || mat[mid][col] > mat[mid - 1][col]) &&
(mid == n - 1 || mat[mid][col] > mat[mid + 1][col]))
return {mid, col};
else {
if (mid != 0 && mat[mid][col] < mat[mid - 1][col])
high = mid - 1;
else
low = mid + 1;
}
}
return {-1, -1};
}
/*
TIME COMPLEXITY: O(m log(n)) or O(n log(m)) - Binary search is performed on the columns of the matrix.
SPACE COMPLEXITY: O(1) - Constant space is used.
*/
/*QUESTION:
Given a row-wise sorted matrix of size R*C where R and C are always odd, find the median of the matrix.
Example:
Input:
R = 3, C = 3
M = [[1, 3, 5],
[2, 6, 9],
[3, 6, 9]]
Output: 5
Explanation: Sorting matrix elements gives us {1, 2, 3, 3, 5, 6, 6, 9, 9}. Hence, 5 is the median.
APPROACH:
To find the median of a row-wise sorted matrix, we can follow these steps:
1. Initialize two variables, `low` and `high`, to keep track of the minimum and maximum elements in the matrix.
2. Iterate through each row and update `low` with the minimum value of the first element in each row and `high` with the maximum value of the last element in each row.
3. Perform binary search between `low` and `high`.
4. For each iteration of binary search, count the number of elements in the matrix that are less than or equal to the mid value.
- If the count is less than the desired median position, update `low` to mid + 1.
- If the count is greater than or equal to the desired median position, update the answer with the mid value and update `high` to mid - 1.
5. Repeat steps 3-4 until `low` becomes greater than `high`.
6. Return the final answer as the median of the matrix.
CODE:*/
int median(vector<vector<int>>& matrix, int R, int C) {
int low = INT_MAX;
int high = INT_MIN;
int opt_cnt = (R * C + 1) / 2;
int ans = -1;
for (int i = 0; i < R; i++) {
low = min(low, matrix[i][0]);
high = max(high, matrix[i][C - 1]);
}
while (low <= high) {
int mid = low + (high - low) / 2;
int cnt = 0;
for (int i = 0; i < R; i++) {
cnt += upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
}
if (cnt < opt_cnt)
low = mid + 1;
else {
ans = mid;
high = mid - 1;
}
}
return ans;
}
/*
TIME COMPLEXITY: O(R * log(C) * log(range)), where R is the number of rows, C is the number of columns, and range is the difference between the minimum and maximum elements in the matrix.
The algorithm performs binary search on each row, which takes O(log(C)) time, and the outer binary search iterates log(range) times.
SPACE COMPLEXITY: O(1) as the algorithm only uses a constant amount of additional space to store variables.
*/
In Search Space¶
/*
QUESTION:
Given an integer x, find the square root of x. If x is not a perfect square, then return floor(√x).
Example:
Input:
x = 5
Output: 2
Explanation: Since 5 is not a perfect square, the floor of the square root of 5 is 2.
Input:
x = 4
Output: 2
Explanation: Since 4 is a perfect square, the square root of 4 is 2.
APPROACH:
We can use binary search to find the square root of x.
1. Initialize the search space with low = 1 and high = x.
2. While low is less than or equal to high:
- Calculate the mid of the search space.
- If the square of mid is equal to x, return mid as the square root.
- If the square of mid is less than x, update the answer to mid and set low = mid + 1 to search for a larger value.
- If the square of mid is greater than x, set high = mid - 1 to search for a smaller value.
3. Return the answer, which represents the floor of the square root of x.
CODE:
*/
long long int floorSqrt(long long int x)
{
long long int low = 1, high = x;
long long int ans = -1;
while(low <= high){
long long int mid = low + (high - low) / 2;
if(x == mid * mid)
return mid;
else if(mid * mid < x){
ans = mid;
low = mid + 1;
}
else
high = mid - 1;
}
return ans;
}
/*
Time Complexity: O(log(x))
Space Complexity: O(1)
*/
/*
QUESTION:
You are given 2 numbers (n, m); the task is to find n√m (nth root of m).
Example:
Input: n = 2, m = 9
Output: 3
Explanation: 3^2 = 9
Input: n = 3, m = 9
Output: -1
Explanation: 3rd root of 9 is not an integer.
APPROACH:
We can use a binary search algorithm to find the nth root of m.
1. Initialize the search range with low = 1 and high = m.
2. While low is less than or equal to high:
- Calculate the mid value as the average of low and high.
- If mid raised to the power of n is equal to m, return mid.
- If mid raised to the power of n is less than m, update low to mid + 1.
- If mid raised to the power of n is greater than m, update high to mid - 1.
3. If the loop exits without finding the nth root, return -1.
CODE:
*/
int NthRoot(int n, int m) {
int low = 1, high = m;
while (low <= high) {
long long mid = low + (high - low) / 2;
if (pow(mid, n) == m)
return mid;
else if (pow(mid, n) < m)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
/*
TIME COMPLEXITY: O(log m)
The binary search algorithm runs in logarithmic time complexity as it reduces the search range by half at each step.
SPACE COMPLEXITY: O(1)
The algorithm uses a constant amount of space to store the variables and perform calculations.
*/
/*
QUESTION:
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
EXAMPLES:
Input: piles = [3,6,7,11], h = 8
Output: 4
Input: piles = [30,11,23,4,20], h = 5
Output: 30
APPROACH:
- We can apply binary search to find the minimum eating speed.
- The eating speed can range from 1 to the maximum number of bananas in a pile.
- For each eating speed, we check if it is possible to finish eating all the bananas within h hours.
- We calculate the required time based on the eating speed, considering the number of bananas in each pile.
- If the required time is less than or equal to h, it means it is possible to finish eating all the bananas within h hours.
- We update the answer accordingly and continue the binary search.
CODE:
*/
bool isPossible(int mid, vector<int>& piles, int h){
long req = 0;
for(auto it:piles){
int time = it/mid;
req += time;
if(it%mid!=0) req++;
}
if(req<=h)
return true;
return false;
}
int minEatingSpeed(vector<int>& piles, int h) {
int ans = -1;
int low = 1, high = INT_MIN;
for(auto it:piles){
high = max(high,it);
}
while(low<=high){
int mid = low+(high-low)/2;
if(isPossible(mid,piles,h)){
ans = mid;
high = mid-1;
}
else{
low = mid+1;
}
}
return ans;
}
// TIME COMPLEXITY: O(N log M), where N is the number of piles and M is the maximum number of bananas in a pile.
// SPACE COMPLEXITY: O(1)
/*
Question:
You are given an integer array bloomDay, an integer m, and an integer k. You want to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.
The garden consists of n flowers, where the i-th flower will bloom on the bloomDay[i] day and can be used in exactly one bouquet.
Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets, return -1.
Example:
Input:
bloomDay = [1,10,3,10,2]
m = 3
k = 1
Output:
3
Explanation:
Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _] // we can only make one bouquet.
After day 2: [x, _, _, _, x] // we can only make two bouquets.
After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.
*/
/*
Approach:
- Use binary search to find the minimum number of days required to make m bouquets.
- The search space will be between the minimum and maximum bloom day.
- For each mid value, simulate the process of making bouquets.
- Count the number of bouquets that can be made using k adjacent flowers on or after the current day.
- If the count is equal to or greater than m, update the answer and search in the lower half of the search space.
- If the count is less than m, search in the upper half of the search space.
*/
bool isPossible(int mid, vector<int>& bloomDay, int m, int k) {
int bqts = 0, temp = 0;
for(auto it:bloomDay){
if(it<=mid)
temp++;
else
temp = 0;
if(temp==k){
bqts++;
temp = 0;
}
}
if(bqts>=m)
return true;
return false;
}
int minDays(vector<int>& bloomDay, int m, int k) {
if((long)m*k > bloomDay.size())
return -1;
int ans = -1;
int low = INT_MAX, high = INT_MIN;
for(auto it:bloomDay){
low = min(low,it);
high = max(high,it);
}
while(low<=high){
int mid = low+(high-low)/2;
if(isPossible(mid,bloomDay,m,k)){
ans = mid;
high = mid-1;
}
else{
low = mid+1;
}
}
return ans;
}
// Time Complexity: The binary search approach takes O(log n), where n is the number of elements in the `bloomDay` array.
// Space Complexity: The space complexity is O(1) since we are using a constant amount of extra space.
/*
Question:
You are given an array of integers nums and an integer threshold. We need to find the smallest divisor
such that the result of dividing each element of the array by the divisor and summing up the results
is less than or equal to the threshold.
Example:
Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum of 17 (1+2+5+9) if the divisor is 1.
If the divisor is 4, we can get a sum of 7 (1+1+2+3).
If the divisor is 5, the sum will be 5 (1+1+1+2).
The smallest divisor that gives a sum less than or equal to the threshold is 5.
Approach:
- Start with a range of possible divisors from 1 to the maximum value in the array.
- Use binary search to find the smallest divisor that satisfies the given condition.
- Check the midpoint of the range and calculate the sum of divisions using the current divisor.
- If the sum is less than or equal to the threshold, update the answer and continue searching in the lower half of the range.
- If the sum is greater than the threshold, search in the upper half of the range.
- Repeat this process until the range is narrowed down to a single value, which will be the smallest divisor.
Code:
*/
int smallestDivisor(vector<int>& nums, int threshold) {
int ans = -1;
int low = 1, high = INT_MIN;
// Finding the maximum value in the array
for (auto it : nums)
high = max(high, it);
// Binary search for the smallest divisor
while (low <= high) {
int mid = low + (high - low) / 2;
int sum = 0;
for (auto num : nums) {
sum += (num + mid - 1) / mid;
}
if (sum <= threshold) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans;
}
// Time Complexity: O(n log(max(nums)))
// Space Complexity: O(1)
/*
Question:
A conveyor belt has packages that must be shipped from one port to another within days days.
The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.
Example:
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10
Approach:
To find the least weight capacity of the ship, we can use binary search. We set the low and high as the minimum and maximum weight from the weights array, respectively. Then, we iterate through the weights and check if it can be accommodated within the current capacity. If it can, we subtract the weight from the capacity. If it cannot, we increment the required number of days and update the capacity with the current weight. We continue this process until we find the minimum capacity that satisfies the given number of days.
Code:
*/
bool isPossible(int mid, vector<int>& weights, int days){
int req_day = 1, temp = mid;
for(auto it:weights){
if(it <= temp){
temp -= it;
}
else{
req_day++;
if(it > mid)
return false;
temp = mid - it;
}
}
if(req_day <= days)
return true;
return false;
}
int shipWithinDays(vector<int>& weights, int days) {
int ans = -1;
int low = INT_MAX, high = 0;
for(auto it:weights){
low = min(low, it);
high += it;
}
while(low <= high){
int mid = low + (high - low) / 2;
if(isPossible(mid, weights, days)){
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
/*
- Time Complexity: O(N log M), where N is the size of the weights array and M is the sum of all the weights.
- Space Complexity: O(1) as we are using a constant amount of extra space.
*/
/*
Question:
In the universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.
Rick stated that magnetic force between two different balls at positions x and y is |x - y|.
Given the integer array position and the integer m. Return the required force.
Example:
Input: position = [1,2,3,4,7], m = 3
Output: 3
Explanation: Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.
Approach:
- Sort the position array in ascending order to simplify the possibility check.
- Use binary search to find the maximum minimum magnetic force.
- Set the low and high values for the binary search.
- While the low value is less than or equal to the high value, calculate the mid value.
- Check if it is possible to distribute the balls with a minimum magnetic force of mid using the isPossible() function.
- If it is possible, update the answer and set the low value to mid + 1.
- If it is not possible, set the high value to mid - 1.
- Return the answer.
Code:
*/
bool isPossible(int mid, vector<int>& position, int m){
int placeM = 1;
int start = 0;
for(int i=1; i<position.size(); i++){
if(position[i]-position[start]>=mid){
placeM++;
start = i;
}
}
if(placeM>=m)
return true;
return false;
}
int maxDistance(vector<int>& position, int m) {
sort(position.begin(),position.end());
int low = 1, high = position[position.size()-1]-position[0];
int ans = -1;
while(low<=high){
int mid = low+(high-low)/2;
if(isPossible(mid,position,m)){
ans = mid;
low = mid+1;
}
else{
high = mid-1;
}
}
return ans;
}
/*
Time Complexity: O(n log n), where n is the size of the position array. Sorting the array takes O(n log n) time and the binary search takes O(log n) time.
Space Complexity: O(1), constant space is used.
*/
/*
Question:
You have N books, each with Ai number of pages. M students need to be allocated contiguous books, with each student getting at least one book. Out of all the permutations, the goal is to find the permutation where the student with the most pages allocated to him gets the minimum number of pages, out of all possible permutations.
Note: Return -1 if a valid assignment is not possible, and allotment should be in contiguous order.
Example:
Input:
N = 4
A[] = {12,34,67,90}
M = 2
Output: 113
Explanation:
Allocation can be done in following ways:
{12} and {34, 67, 90} Maximum Pages = 191
{12, 34} and {67, 90} Maximum Pages = 157
{12, 34, 67} and {90} Maximum Pages = 113.
Therefore, the minimum of these cases is 113, which is selected as the output.
Approach:
- We can use binary search to find the minimum number of pages that can be allocated to the student with the most pages.
- The range for binary search will be from the minimum number of pages in the array to the sum of all the pages in the array.
- For each mid value, we will check if it is possible to allocate the books in a way that the maximum number of pages for a student is less than or equal to mid.
- To check this, we iterate through the array of pages and keep track of the number of students and the sum of pages allocated to the current student.
- If at any point, the sum exceeds the mid value, we increment the number of students and reset the sum to the current page value.
- If the number of students exceeds the given M, it means we need more students to allocate the pages, so we return false.
- If at the end, the number of students is less than or equal to M, it means it is possible to allocate the pages within the given constraints, so we return true.
- Finally, we perform binary search and find the minimum mid value that returns true in the isPossible function.
Code:
*/
bool isPossible(int mid, int A[], int N, int M) {
int pos_m = 1;
int temp = 0;
for (int i = 0; i < N; i++) {
if (temp + A[i] <= mid) {
temp += A[i];
} else {
pos_m++;
if (A[i] > mid)
return false;
temp = A[i];
}
}
if (pos_m <= M)
return true;
return false;
}
int findPages(int A[], int N, int M) {
if (M > N)
return -1;
int low = INT_MAX, high = 0;
int ans = -1;
for (int i = 0; i < N; i++) {
low = min(low, A[i]);
high += A[i];
}
while (low <= high) {
int mid = low + (high - low) / 2;
if (isPossible(mid, A, N, M)) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans;
}
/*
Time Complexity: O(N log S), where N is the number of books and S is the sum of all the pages in the array. The binary search takes log S iterations, and for each iteration, we check the validity of allocation in O(N) time.
Space Complexity: O(1), as we are using a constant amount of extra space.
*/
/*
Question: Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized. Return the minimized largest sum of the split.
Example:
Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.
Approach:
- The problem can be solved using the binary search algorithm.
- We need to find the range of possible values for the minimized largest sum.
- The lower bound of the range is the maximum element in the array (as each subarray must contain at least one element).
- The upper bound of the range is the sum of all elements in the array (as the largest sum cannot exceed the total sum of the array).
- We perform binary search within this range to find the minimum largest sum that satisfies the given condition.
- In each iteration, we calculate the mid value of the range and check if it is a valid solution using a helper function.
- The helper function checks if it is possible to split the array into k subarrays with a maximum sum of mid.
- If it is possible, we update the answer and search the lower half of the range.
- If it is not possible, we search the upper half of the range.
- We continue this process until we find the optimal solution.
Time Complexity: O(n * log(sum of array))
Space Complexity: O(1)
*/
bool isPossible(int mid, vector<int>& nums, int k) {
int pos_parts = 1, temp = 0;
for (auto it : nums) {
if (temp + it <= mid) {
temp += it;
} else {
pos_parts++;
if (it > mid)
return false;
temp = it;
}
}
if (pos_parts <= k)
return true;
return false;
}
int splitArray(vector<int>& nums, int k) {
int low = INT_MAX, high = 0;
int ans = -1;
for (auto it : nums) {
low = min(low, it);
high += it;
}
while (low <= high) {
int mid = low + (high - low) / 2;
if (isPossible(mid, nums, k)) {
ans = mid;
high = mid - 1;
} else
low = mid + 1;
}
return ans;
}
/*
Question: Given a sorted array arr of positive integers and an integer k, find the kth positive integer that is missing from the array.
Example:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.
Approach:
- We can solve this problem by finding the position in the array where the count of missing positive integers becomes greater than or equal to k.
- Initialize a variable `low` to 0 to represent the start of the array.
- Initialize a variable `high` to the size of the array minus 1 to represent the end of the array.
- Initialize a variable `pos` to -1 to store the position of the missing integer.
- Perform a binary search on the array:
- Calculate the middle index `mid` using the formula `low + (high - low) / 2`.
- If the count of missing positive integers in the subarray from the start to `mid` is less than k, update `low` to `mid + 1`.
- Otherwise, update `pos` to `mid` and update `high` to `mid - 1`.
- After the binary search, check if a missing integer was found:
- If `pos` is still -1, it means that the missing integer should be after the last element in the array. Return the sum of the size of the array and k.
- Otherwise, return `pos + k` as the kth missing positive integer.
Time Complexity: O(log n), where n is the size of the array.
Space Complexity: O(1)
*/
int findKthPositive(vector<int>& arr, int k) {
int low = 0, high = arr.size() - 1;
int pos = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if ((arr[mid] - (mid + 1)) < k)
low = mid + 1;
else {
pos = mid;
high = mid - 1;
}
}
if (pos == -1)
return arr.size() + k;
return pos + k;
}
/*
Questions:-
We have an horizontal number line. On that number line, we have gas stations at positions stations[0], stations[1], ..., stations[N-1], where N = size of the stations array. Now, we add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized. We have to find the smallest possible value of D. Find the answer exactly to 2 decimal places.
Example 1:
Input:
N = 10
stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
K = 9
Output: 0.50
Explanation: Each of the 9 stations can be added mid way between all the existing adjacent stations.
Example 2:
Input:
N = 10
stations = [3,6,12,19,33,44,67,72,89,95]
K = 2
Output: 14.00
Explanation: Construction of gas stations at 86 locations
Approach:
- To minimize the maximum distance between adjacent gas stations, we can perform binary search on the possible range of distances.
- Initialize `low` to 0 and `high` to the maximum distance between adjacent existing gas stations.
- While `high - low` is greater than a small threshold (e.g., 1e-6), calculate the mid-point `mid` between `low` and `high`.
- Check if it is possible to add `K` additional gas stations such that the maximum distance between adjacent gas stations is less than or equal to `mid`.
- Iterate over the existing gas stations and check the distance between adjacent stations.
- If the total number of additional stations required is less than or equal to `K`, it is possible to achieve the maximum distance `mid`.
- If it is possible, update `high` to `mid`, as we are looking for smaller distances.
- Otherwise, update `low` to `mid`.
- Finally, return the value of `low` plus a small value (e.g., 0.000001) to represent the answer to 2 decimal places.
Time Complexity: O(N log M), where N is the number of existing gas stations and M is the range of distances between adjacent gas stations.
Space Complexity: O(1), as we are using constant extra space.
*/
bool isPossible(double mid, vector<int>& stations, int K) {
int req_stations = 0;
for (int i = 1; i < stations.size(); i++) {
req_stations += floor((stations[i] - stations[i - 1]) / mid);
}
return req_stations <= K;
}
double findSmallestMaxDist(vector<int>& stations, int K) {
double low = 0, high = stations[stations.size() - 1] - stations[0];
while (high - low > 1e-6) {
double mid = low + (high - low) / 2;
if (isPossible(mid, stations, K)) {
high = mid;
} else {
low = mid;
}
}
return low + 0.000001;
}
/*QUESTION:
Given two sorted arrays nums1 and nums2 of sizes m and n respectively, you need to find the median of the two sorted arrays.
APPROACH:
To find the median of two sorted arrays, we can apply the concept of binary search. The overall time complexity of the solution should be O(log (m+n)).
1. First, we ensure that nums1 is the smaller sized array. If not, we swap nums1 and nums2.
2. Calculate the optimal count opt_cnt, which is (nums1.size() + nums2.size() + 1) / 2. This represents the median index in the merged array.
3. Initialize low to 0 and high to nums1.size() - 1.
4. Perform binary search until low is less than or equal to high:
- Calculate the cut1 as low + (high - low) / 2, which represents the potential index to partition nums1.
- Calculate cut2 as opt_cnt - cut1, which represents the corresponding index in nums2.
- Calculate l1, l2, r1, and r2 as the left and right elements around the potential partition points.
- If l1 is less than or equal to r2 and l2 is less than or equal to r1, it means we have found the correct partition points.
- If the total number of elements is even, return the average of the maximum of l1 and l2 and the minimum of r1 and r2.
- If the total number of elements is odd, return the maximum of l1 and l2.
- If l1 is greater than r2, move the high pointer to cut1 - 1.
- Otherwise, move the low pointer to cut1 + 1.
5. If no median is found, return 0.0.
CODE:*/
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size())
return findMedianSortedArrays(nums2, nums1);
int opt_cnt = (nums1.size() + nums2.size() + 1) / 2;
int low = 0, high = nums1.size();
while (low <= high) {
int cut1 = low + (high - low) / 2;
int cut2 = opt_cnt - cut1;
int l1, l2, r1, r2;
(cut1 - 1 < 0) ? l1 = INT_MIN : l1 = nums1[cut1 - 1];
(cut2 - 1 < 0) ? l2 = INT_MIN : l2 = nums2[cut2 - 1];
(cut1 >= nums1.size()) ? r1 = INT_MAX : r1 = nums1[cut1];
(cut2 >= nums2.size()) ? r2 = INT_MAX : r2 = nums2[cut2];
if (l1 <= r2 && l2 <= r1) {
if ((nums1.size() + nums2.size()) % 2 == 0)
return (max(l1, l2) + min(r1, r2)) / 2.0;
return max(l1, l2);
} else if (l1 > r2) {
high = cut1 - 1;
} else {
low = cut1 + 1;
}
}
return 0.0;
}
/*
COMPLEXITY ANALYSIS:
- Time complexity: O(log(min(m, n))), where m and n are the sizes of the input arrays nums1 and nums2, respectively. We perform binary search on the smaller array.
- Space complexity: O(1), as we use constant extra space throughout the algorithm.
*/
/*
Question:-
Given two sorted arrays arr1 and arr2 of size N and M respectively and an element K.
Find the element that would be at the kth position of the final sorted array.
Example:-
Input:
arr1[] = {2, 3, 6, 7, 9}
arr2[] = {1, 4, 8, 10}
k = 5
Output:
6
Explanation:
The final sorted array would be -
1, 2, 3, 4, 6, 7, 8, 9, 10
The 5th element of this array is 6.
Approach:
1. Compare the sizes of the two arrays, arr1 and arr2. If the size of arr1 is greater than arr2, swap the arrays to ensure arr1 is the smaller sized array.
2. Set the low and high variables for binary search.
- If m < k, set low = k - m, otherwise set low = 0.
- If k < n, set high = k, otherwise set high = n.
3. Perform binary search within the range [low, high] to find the kth element.
4. In each iteration of binary search:
- Calculate the cut positions, cut1 and cut2, based on the mid position.
- Determine the left and right elements of arr1 and arr2 based on the cut positions.
- Compare the left and right elements and adjust the low and high pointers accordingly.
5. Return the maximum element among the left elements, as it would be the kth element in the final sorted array.
CODE
*/
int kthElement(int arr1[], int arr2[], int n, int m, int k)
{
// assuming arr1 is the smaller sized array
if (n > m)
kthElement(arr2, arr1, m, n, k);
int low, high;
(m < k) ? low = k - m : low = 0;
(k < n) ? high = k : high = n;
while (low <= high) {
int cut1 = low + (high - low) / 2;
int cut2 = k - cut1;
int l1, l2, r1, r2;
(cut1 - 1 < 0) ? l1 = INT_MIN : l1 = arr1[cut1 - 1];
(cut2 - 1 < 0) ? l2 = INT_MIN : l2 = arr2[cut2 - 1];
(cut1 >= n) ? r1 = INT_MAX : r1 = arr1[cut1];
(cut2 >= m) ? r2 = INT_MAX : r2 = arr2[cut2];
if (l1 <= r2 && l2 <= r1) {
return max(l1, l2);
}
else if (l1 > r2) {
high = cut1 - 1;
}
else {
low = cut1 + 1;
}
}
}
/*
Time Complexity: O(log(min(N, M)))
Space Complexity: O(1)
*/