Q: Binary Search.
public class Main {
public static void main(String[] args) {
int[] arr = {-8, -6, -2, 0, 2, 4, 6, 8, 11, 18, 21, 27}; // Sorted array
int target = -6;
System.out.println(bSearch(arr, target));
// System.out.println(bSearch2(arr, target));
}
// Return -1 if it does not exist else return index
static int bSearch(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
// Find the middle element
// int mid = (start + end) / 2; // Might be possible that exceeds the range of int in java
int mid = start + (end - start) / 2;
if (target < arr[mid]) {
end = mid - 1;
}
else if (target > arr[mid]) {
start = mid + 1;
}
else {
return mid;
}
}
return -1;
}
static int bSearch2(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (target == arr[mid]) {
return mid;
}
else if (target > arr[mid]) {
start = mid;
}
else {
end = mid;
}
}
return -1;
}
}
Q: Order Agnostic in Binary Search.
public class OrderAgnosticBSearch {
public static void main(String[] args) {
int[] arr = {-8, -6, -2, 0, 2, 34, 4, 6, 8, 11, 18, 21, 27}; // Sorted array
int target = -6;
System.out.println(orderAgnosticBSearch(arr, target));
}
static int orderAgnosticBSearch(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
// Find whether the array is sorted in ascending or descending order
boolean isAsc = arr[start] < arr[end];
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == target) {
return mid;
}
if (isAsc) {
if (target < arr[mid]) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
else {
if (target > arr[mid]) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
}
return -1;
}
}
Q: Ceiling number.
public class CeilingNum {
public static void main(String[] args) {
// Ceiling number = Smallest number >= target
int[] arr = {2, 3, 5, 9, 14, 16, 18, 35, 47, 59};
int target = 15;
System.out.println(ceiling(arr, target));
}
// Return the index of smallest no. >= target
static int ceiling(int[] arr, int target) {
// But what if the target is > the greatest no. in the array
if (target == arr[arr.length - 1]) {
return arr.length - 1;
}
else if (target > arr[arr.length - 1]) {
return -1;
}
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (target < arr[mid]) {
end = mid - 1;
} else if (target > arr[mid]) {
start = mid + 1;
} else {
return mid;
}
}
return start;
}
}
Q: Floor number.
public class FloorNum {
public static void main(String[] args) {
// Floor number = Greatest number <= target
int[] arr = {2, 3, 5, 9, 14, 16, 18, 35, 47, 59};
int target = 15;
System.out.println(floor(arr, target));
}
// Return the index of greatest no. <= target
static int floor(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (target < arr[mid]) {
end = mid - 1;
} else if (target > arr[mid]) {
start = mid + 1;
} else {
return mid;
}
}
return end;
}
}
Q: Find Ceiling letter (LeetCode Question).
public class CeilingLetter {
public static void main(String[] args) {
// Ceiling number = Smallest number >= target
char[] letters = {'c', 'f', 'j'};
char target = 'd';
System.out.println(nextGreatestLetter(letters, target));
}
// Return the index of smallest no. >= target
static char nextGreatestLetter(char[] letters, char target) {
int start = 0;
int end = letters.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (target < letters[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
// return letters[start]; // Does not reach out the LeetCode's Question conditions
// Condition: to Wrap the letters means like a loop
// Eg: target = 'z' Ans = 'c'
return letters[start % letters.length];
}
}
Q: Find first and last position (LeetCode Question).
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] nums = {5, 7, 7, 7, 7, 8, 8};
int target = 7;
System.out.println(Arrays.toString(searchRange2(nums, target)));
}
// Return the index of smallest no. >= target
static int[] searchRange(int[] nums, int target) {
int[] ans = {-1, -1};
// Check for first occurrence if target first
int start = search(nums, target, true);
int end = search(nums, target, false);
ans[0] = start;
ans[1] = end;
return ans;
}
// More optimize
static int[] searchRange2(int[] nums, int target) {
int[] ans = {-1, -1};
// Check for first occurrence if target first
ans[0] = search(nums, target, true);
if (ans[0] != -1) {
ans[1] = search(nums, target, false);
}
return ans;
}
// This function just returns the index value of target
static int search(int[] nums, int target, boolean firstStartInd) {
int ans = -1;
int start = 0;
int end = nums.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (target < nums[mid]) {
end = mid - 1;
}
else if (target > nums[mid]) {
start = mid + 1;
}
else {
// Potential ans found
ans = mid;
if (firstStartInd) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
}
return ans;
}
}
Q: Find the position in sorted array of infinity length (Amazon Question)?
public class Main {
public static void main(String[] args) {
// Find the position in sorted array of infinity length (Amazon Question)
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30};
int target = 27;
System.out.println(findPositionInInfiniteArray2(arr, target));
}
static int findPositionInInfiniteArray(int[] arr, int target){
int start = 0;
int end = 5;
int ans = -1;
while (true) {
ans = bSearch(arr, target, start, end);
if (ans != -1) {
break;
} else {
start = end + 1;
end += 5;
bSearch(arr, target, start, end);
}
}
return ans;
}
// More Optimize
static int findPositionInInfiniteArray2(int[] arr, int target){
// First find the range
// First start with a box of size 2
int start = 0;
int end = 1;
// Condition for the target ot lie in the range
while (target > arr[end]) {
int temp = end + 1; // It's a new start
// Double the box value
end = end + (end - start + 1) * 2; // end = previous end + sizeofbox * 2
start = temp;
}
return bSearch(arr, target, start, end);
}
static int bSearch(int[] arr, int target, int start, int end) {
while (start <= end) {
int mid = start + (end - start) / 2;
if (target < arr[mid]) {
end = mid - 1;
} else if (target > arr[mid]) {
start = mid + 1;
} else {
return mid;
}
}
return -1;
}
}
Q: Find the peak in the mountain (highest/peak element) (LeetCode Question).
public class Main {
public static void main(String[] args) {
// int[] arr = {2, 4, 6, 8, 5, 6, 4, 2};
int[] arr = {1, 2, 3, 5, 6, 4, 3, 2};
System.out.println(peakInMounatain(arr));
}
static int peakInMounatain(int[] arr) {
int start = 0;
int end = arr.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (arr[mid] < arr[mid+1]) {
// You are in increasing part of an array
// This might be the answer, but look at right
start = mid + 1; // Because we know that mid+1 element > mid element
} else if (arr[mid] > arr[mid+1]) {
// You are in decreasing part of an array
// This might be the answer, but look at left
// This is why end != mid - 1
end = mid;
}
}
// In the end, start == end and pointing to the largest number because of the 2 checks above
// start and end are always trying to find max element in the above 2 checks
// Hence, when they are pointing to just one element, that is the ma one because that is what the check says
// More elaboration: at every point of time for start and end, they have the best possible answer till that time
// And if we are saying that only one item is reminaing, hence because of above line that is the best possible answer
return start; // or return end as both are equal
}
}
Q: Find mountain element (LeetCode Question).
public class Main {
public static void main(String[] args) {
// LeetCode Question
int[] arr = {1, 2, 3, 4, 5, 3, 1};
int target = 3;
System.out.println(mountainElement(arr, target));
}
static int mountainElement(int[] arr, int target) {
int peakElement = mountainPeakIndex(arr); // Return sepration index of the array (increasing and decreasing)
// int firstHalf = searchTarget(arr, target, 0, peakElement);
// We can also use this by any chance array is not sorted
int firstHalf = orderAgnosticBSearch(arr, target, 0, peakElement);
if (firstHalf != -1) {
return firstHalf;
}
// Search in second half array
// return searchTarget(arr, target, peakElement+1, arr.length-1);
return orderAgnosticBSearch(arr, target, peakElement+1, arr.length-1);
}
static int mountainPeakIndex(int[] arr) {
int start = 0;
int end = arr.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (arr[mid] < arr[mid+1]) {
// You are in increasing part of an array
// This might be the answer, but look at right
start = mid + 1; // Because we know that mid+1 element > mid element
} else if (arr[mid] > arr[mid+1]) {
// You are in decreasing part of an array
// This might be the answer, but look at left
// This is why end != mid - 1
end = mid;
}
}
// In the end, start == end and pointing to the largest number because of the 2 checks above
// start and end are always trying to find max element in the above 2 checks
// Hence, when they are pointing to just one element, that is the ma one because that is what the check says
// More elaboration: at every point of time for start and end, they have the best possible answer till that time
// And if we are saying that only one item is reminaing, hence because of above line that is the best possible answer
return start; // or return end as both are equal
}
static int searchTarget(int[] arr, int target, int start, int end) {
while (start < end) {
int mid = start + (end - start) / 2;
if (target < arr[mid]) {
end = mid - 1;
} else if (target > arr[mid]) {
start = mid + 1;
}
else {
return mid;
}
}
return -1;
}
static int orderAgnosticBSearch(int[] arr, int target, int start, int end) {
// Find whether the array is sorted in ascending or descending order
boolean isAsc = arr[start] < arr[end];
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == target) {
return mid;
}
if (isAsc) {
if (target < arr[mid]) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
else {
if (target > arr[mid]) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
}
return -1;
}
}
Q: Rotated sorted array (LeetCode Question).
public class Main {
public static void main(String[] args) {
}
}
Q: Count how many times an array is rotated (LeetCode Question).
public class Main {
public static void main(String[] args) {
}
}
Q: Split array largest sum (LeetCode Question).
public class Main {
public static void main(String[] args) {
// Split array largest sum (LeetCode Question)
int[] arr = {1, 2, 3, 4, 5};
// int[] arr = {7, 2, 5, 10, 8};
int m = 2;
System.out.println(splitArray(arr, m));
}
static int splitArray(int[] arr, int m) {
int start = 0;
int end = 0;
for (int i=0; i<arr.length; i++) {
start = Math.max(start, arr[i]); // In the end of the loop this will contain the max item from the array
end += arr[i];
}
// Binary Search
while (start < end) {
// Try for the middle as potential answer
int mid = start + (end - start) / 2;
// Calculate how many pieces you can divide this in with this max sum
int sum = 0;
int pieces = 1;
for (int element : arr) {
if (sum + element > mid) {
// You can't add this inthis subarray, nake new one
// Say you add this element in new subarray, then sum = num
sum = element;
pieces++;
}
else {
sum += element;
}
}
if (pieces > m) {
start = mid + 1;
}
else {
end = mid;
}
}
return start;
}
}
Q: (LeetCode Question).
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
// int[][] matrix = {
// {1, 2, 3, 4},
// {5, 6, 7, 8},
// {9, 10, 11, 12},
// {13, 14, 15, 16}
// };
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
{10, 11, 12}
};
int target = 8;
// System.out.println(Arrays.toString(bSearchIn2DArray(matrix, target)));
System.out.println(Arrays.toString(search(matrix, target)));
}
// Solution - I
static int[] bSearchIn2DArray(int[][] matrix, int target) {
int row = 0;
int col = matrix.length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] == target) {
return new int[] {row, col};
}
if (matrix[row][col] < target) {
row++;
}
else {
col--;
}
}
return new int[] {-1, -1};
}
// Solution - II
// search in the row provided between the cols provided
static int[] binarySearch(int[][] matrix, int row, int cStart, int cEnd, int target) {
while (cStart <= cEnd) {
int mid = cStart + (cEnd - cStart) / 2;
if (matrix[row][mid] == target) {
return new int[]{row, mid};
}
if (matrix[row][mid] < target) {
cStart = mid + 1;
} else {
cEnd = mid - 1;
}
}
return new int[]{-1, -1};
}
static int[] search(int[][] matrix, int target) {
int rows = matrix.length;
int cols = matrix[0].length; // be cautious, matrix may be empty
if (cols == 0){
return new int[] {-1,-1};
}
if (rows == 1) {
return binarySearch(matrix,0, 0, cols-1, target);
}
int rStart = 0;
int rEnd = rows - 1;
int cMid = cols / 2;
// run the loop till 2 rows are remaining
while (rStart < (rEnd - 1)) { // while this is true it will have more than 2 rows
int mid = rStart + (rEnd - rStart) / 2;
if (matrix[mid][cMid] == target) {
return new int[]{mid, cMid};
}
if (matrix[mid][cMid] < target) {
rStart = mid;
} else {
rEnd = mid;
}
}
// now we have two rows
// check whether the target is in the col of 2 rows
if (matrix[rStart][cMid] == target) {
return new int[]{rStart, cMid};
}
if (matrix[rStart + 1][cMid] == target) {
return new int[]{rStart + 1, cMid};
}
// search in 1st half
if (target <= matrix[rStart][cMid - 1]) {
return binarySearch(matrix, rStart, 0, cMid-1, target);
}
// search in 2nd half
if (target >= matrix[rStart][cMid + 1] && target <= matrix[rStart][cols - 1]) {
return binarySearch(matrix, rStart, cMid + 1, cols - 1, target);
}
// search in 3rd half
if (target <= matrix[rStart + 1][cMid - 1]) {
return binarySearch(matrix, rStart + 1, 0, cMid-1, target);
} else {
return binarySearch(matrix, rStart + 1, cMid + 1, cols - 1, target);
}
}
}
0 Comments