Lets reduce your search - Binary Search
The first step in optimization always begins with reducing time complexity — and what better way to start than with an algorithm that runs in O(log n)? So lets start with Binary search !!!
What is Binary Search?
Binary Search is a super handy algorithm for finding an element in a sorted array or list. Instead of checking each item one by one like linear search, binary search smartly cuts the search space in half each time, which means way fewer comparisons.
Linear Search → O(n) time (look at each item).
Binary Search → O(log n) time (cut the array in half each step).
This makes binary search incredibly powerful when dealing with large datasets.
So how does it magically reduces the search space by half ??
A Real-Life Analogy for Binary Search: Finding a Word in a Dictionary
Problem Statement: You have a physical dictionary and need to find a specific word.
Method 1: Linear Search (The Inefficient Way)
In this approach, you start on the first page and look at every single word in sequence, page by page, until you either find your target word or reach the end of the dictionary.
How it works: You begin at page 1, check all words, move to page 2, and repeat. This process continues until you find your target.
Technical Term: This brute-force method is known as a Linear Search.
Drawback: While simple, it is highly inefficient. If the word is near the end, you will have to examine almost every page. For a dictionary of 1,000 pages, this could take 1,000 checks in the worst case.
Method 2: Binary Search (The Optimized Way)
This method leverages the most important property of a dictionary: it is sorted in alphabetical order. This sorted nature allows us to intelligently eliminate large sections of the search space with each step.
How it works:
Open to the Middle: Instead of starting at the beginning, you open the dictionary to the exact middle page (e.g., page 500 of 1000).
Check and Compare: You look at the words on this middle page. You then compare your target word with the words on that page.
If your word comes alphabetically before the words on this page, you know your target must be in the left half.
If your word comes alphabetically after, you know it must be in the right half.
Eliminate Half: You can now completely ignore all pages in the half that does not contain your word. Your search space is instantly cut in half.
Repeat: You now take the remaining half and repeat the process—find its new middle page, compare the words, and eliminate another half.
Narrow Down: You continue this process until you pinpoint the exact page containing your word.
Technical Term: This highly efficient algorithm is called Binary Search.
Advantage: Its efficiency is remarkable. With each check, it halves the number of pages left to search. For a dictionary of 1,000 pages, it will find any word in a maximum of 10 steps (because 2¹⁰ = 1024 > 1000), compared to the 1,000 steps required by a linear search.
Conclusion: Binary search is a fundamental algorithm that transforms a large, tedious problem into a small, manageable one by systematically exploiting the sorted order of data. This principle is directly applied in computer science for quickly searching through sorted arrays, databases, and file systems.
Remark: Binary search only works with a sorted search space. It doesn't have to be a sorted array specifically. The search area just needs to be organized, but it can be anything.
Lets start with an classic example -
Binary Search in a Sorted Array
You are given a sorted array and a target element, your task is to find the index of the target in the array.
If the element does not exist, return -1.
Example:
Input: nums = [3, 4, 6, 7, 9, 12, 16, 17], target = 6
Output: 2
Method 1: Iterative Method
Start with two pointers:
left = 0andright = n - 1.While
left <= right:Find the middle index:
mid = left + (right - left) / 2.If
nums[mid] == target, returnmid.If
nums[mid] < target, search in the right half (left = mid + 1).Else, search in the left half (
right = mid - 1).
If the loop ends, return -1.
Method 2: Recursive Method
Base condition: If
left > right, return -1.Find the middle index:
mid = left + (right - left) / 2.If
nums[mid] == target, returnmid.If
nums[mid] > target, recursively search the left half.Else, recursively search the right half.
| Method | Time Complexity | Space Complexity |
| Iterative | O(log n) | O(1) |
| Recursive | O(log n) | O(log n) (stack) |
import java.util.Arrays;
/**
* Demonstrates Binary Search (Iterative and Recursive) on a sorted array.
* Binary Search is an efficient algorithm for finding a target value within a sorted array.
* It works by repeatedly dividing the search interval in half.
*/
class Main {
public static void main(String[] args) {
// A sorted array is a prerequisite for binary search to work correctly.
int[] nums = {3, 4, 6, 7, 9, 12, 16, 17};
int target = 6;
System.out.println("Array: " + Arrays.toString(nums));
System.out.println("Target: " + target);
// Iterative method call
int iterativeIndex = binarySearchIterative(nums, target);
System.out.println("Iterative Method: Target found at index " + iterativeIndex);
// Recursive method call. We pass the initial search space: the entire array (index 0 to n-1).
int recursiveIndex = binarySearchRecursive(nums, target, 0, nums.length - 1);
System.out.println("Recursive Method: Target found at index " + recursiveIndex);
/* Expected Output:
Array: [3, 4, 6, 7, 9, 12, 16, 17]
Target: 6
Iterative Method: Target found at index 2
Recursive Method: Target found at index 2
*/
}
// --- Iterative Method ---
/**
* Performs a binary search iteratively.
*
* @param nums The sorted array to search in.
* @param target The value to search for.
* @return The index of the target value if found; otherwise, -1.
*
* Time Complexity: O(log n) - With each iteration, the search space is halved.
* Space Complexity: O(1) - Uses a constant amount of extra space (variables: left, right, mid).
*/
public static int binarySearchIterative(int[] nums, int target) {
// Initialize pointers to represent the current search space (the entire array at first).
int left = 0;
int right = nums.length - 1;
// Continue searching as long as the search space is valid (left pointer hasn't passed the right pointer).
while (left <= right) {
// Calculate the middle index of the current search space.
// Using `left + (right - left) / 2` instead of `(left + right) / 2` prevents potential integer overflow.
int mid = left + (right - left) / 2;
// Check if the element at the mid index is the target.
if (nums[mid] == target) {
return mid; // Target found! Return its index.
}
// If the target is greater than the mid element, it must be in the right half.
else if (nums[mid] < target) {
left = mid + 1; // Discard the left half (including mid) by moving the left pointer.
}
// If the target is smaller than the mid element, it must be in the left half.
else {
right = mid - 1; // Discard the right half (including mid) by moving the right pointer.
}
}
// If the loop exits, it means the search space is empty and the target was not found.
return -1;
}
// --- Recursive Method ---
/**
* Performs a binary search recursively.
*
* @param nums The sorted array to search in.
* @param target The value to search for.
* @param left The left boundary of the current search space.
* @param right The right boundary of the current search space.
* @return The index of the target value if found; otherwise, -1.
*
* Time Complexity: O(log n) - The problem size is halved with each recursive call.
* Space Complexity: O(log n) - Space is used on the call stack for each recursive call (log n calls deep).
*/
public static int binarySearchRecursive(int[] nums, int target, int left, int right) {
// Base Case: If the left pointer exceeds the right, the search space is invalid/empty.
if (left > right) {
return -1; // Target not found in this sub-array.
}
// Calculate the middle index of the current search space.
int mid = left + (right - left) / 2;
// Check if the element at the mid index is the target.
if (nums[mid] == target) {
return mid; // Base Case: Target found! Return its index.
}
// Decide which half to search next based on the comparison.
// If the target is smaller than the mid element, search the left half.
else if (nums[mid] > target) {
// Recursively search the left sub-array (from 'left' to 'mid-1').
return binarySearchRecursive(nums, target, left, mid - 1);
}
// If the target is greater than the mid element, search the right half.
else {
// Recursively search the right sub-array (from 'mid+1' to 'right').
return binarySearchRecursive(nums, target, mid + 1, right);
}
}
}
Now you have a basic idea of how binary search cuts the search space in half. Plus, you get a sense of its complexity.
We will implement and analyze three distinct binary search paradigms:
Classical Binary Search: Finding a target in a sorted 1D array.
Binary Search on Answer: Applying binary search to find the optimal solution in a search space defined by a problem's constraints.
2D Binary Search: Adapting the algorithm to search within a sorted 2D matrix.
Lets practice now !!
Implement Lower Bound
The lower bound of a target in a sorted array is the first index where the element is greater than or equal to the target.
If no such element exists, return n (array length).
Example:
Input: nums = [3, 4, 6, 7, 9, 12, 16, 17], target = 6
Output: 2
Explanation: Element `6` is found at index 2.
Input: nums = [3, 4, 6, 7, 9, 12, 16, 17], target = 8
Output: 4
Explanation: First element ≥ 8 is 9 at index 4.
Brute Force Approach
Traverse the array linearly from start.
Return the first index
iwherenums[i] >= target.If no such index exists, return
n.
Time Complexity: O(n)
Space Complexity: O(1)
Optimal Approach (Binary Search)
Initialize
left = 0,right = n - 1, andans = n.While
left <= right:Find
mid = left + (right - left) / 2.If
nums[mid] >= target, updateans = midand search left (right = mid - 1).Else, search right (
left = mid + 1).
Return
ans.
Time Complexity: O(log n)
Space Complexity: O(1)
| Method | Time Complexity | Space Complexity |
| Brute Force | O(n) | O(1) |
| Optimal | O(log n) | O(1) |
import java.util.Arrays;
/**
* Demonstrates the concept of Lower Bound in a sorted array.
*
* Lower Bound Definition:
* The lower bound of a target value in a sorted array is the index of the first element
* that is greater than or equal to (>=) the target.
*
* Key Characteristics:
* - If the target exists, lower bound returns its first occurrence.
* - If the target does not exist, it returns the index of the next smallest element greater than the target.
* - If all elements are smaller than the target, it returns the array's length (a hypothetical position after the last element).
*
* This makes it extremely useful for problems involving insertion points, ranges, and non-exact matches.
*/
class Main {
public static void main(String[] args) {
// Sorted array is a prerequisite for both brute-force and optimal approaches.
int[] nums = {3, 4, 6, 7, 9, 12, 16, 17};
int target1 = 6; // Exists in the array
int target2 = 8; // Does not exist in the array
System.out.println("Array: " + Arrays.toString(nums));
System.out.println("Target 1: " + target1 + " | Target 2: " + target2 + "\n");
// Brute Force Approach
// Simple to understand but inefficient for large datasets.
System.out.println("Brute Force (target=6): " + lowerBoundBruteForce(nums, target1));
System.out.println("Brute Force (target=8): " + lowerBoundBruteForce(nums, target2));
// Optimal Approach (Binary Search)
// Efficient and the standard way to solve this problem.
System.out.println("Optimal (target=6): " + lowerBoundOptimal(nums, target1));
System.out.println("Optimal (target=8): " + lowerBoundOptimal(nums, target2));
/* Expected Output:
Array: [3, 4, 6, 7, 9, 12, 16, 17]
Target 1: 6 | Target 2: 8
Brute Force (target=6): 2 -> Explanation: First element >=6 is at index 2 (value 6).
Brute Force (target=8): 4 -> Explanation: First element >=8 is at index 4 (value 9).
Optimal (target=6): 2
Optimal (target=8): 4
*/
}
// --- Brute Force Approach ---
/**
* Finds the lower bound by performing a linear scan of the array.
*
* @param nums The sorted array to search in.
* @param target The value to find the lower bound for.
* @return The index of the first element >= target, or nums.length if no such element exists.
*
* How it works:
* Iterates through each element from the start until it finds one that is >= the target.
* This index is immediately returned as the answer.
*
* Time Complexity: O(n) - In the worst case, it may need to check every element.
* Space Complexity: O(1) - Uses only a constant amount of extra space.
*
* Use Case: Only suitable for very small arrays due to its linear time complexity.
*/
public static int lowerBoundBruteForce(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
// The moment we find an element >= target, we have found our lower bound.
if (nums[i] >= target) {
return i;
}
}
// If the loop completes, it means all elements are smaller than the target.
// The lower bound is then the next available position, which is the end of the array.
return nums.length;
}
// --- Optimal Approach (Binary Search) ---
/**
* Finds the lower bound using an optimized binary search algorithm.
*
* @param nums The sorted array to search in.
* @param target The value to find the lower bound for.
* @return The index of the first element >= target, or nums.length if no such element exists.
*
* How it works:
* 1. It uses the divide-and-conquer strategy of binary search.
* 2. The key idea is to maintain a potential 'ans' (answer) variable.
* 3. Whenever we find an element (nums[mid]) that is >= target, it is a *candidate* for the lower bound.
* We store this candidate index in 'ans' and then aggressively search to the *LEFT* to see if an
* earlier (smaller index) element also satisfies the condition (is >= target). This ensures we find the *first* such element.
* 4. If the element is smaller, we know the lower bound must be to the right.
*
* Time Complexity: O(log n) - The search space is halved with each iteration.
* Space Complexity: O(1) - Uses only a few variables for pointers and the answer.
*
* Use Case: The standard and efficient solution for finding the lower bound in any sorted array.
*/
public static int lowerBoundOptimal(int[] nums, int target) {
// Initialize the search space to the entire array.
int left = 0;
int right = nums.length - 1;
// Initialize 'ans' to the array length. This is the default answer if no element >= target is found.
// It also handles the case where the search completes without finding a candidate within the loop.
int ans = nums.length;
// Continue the search as long as the search space is valid.
while (left <= right) {
// Calculate the middle index. Prevents overflow compared to (left+right)/2.
int mid = left + (right - left) / 2;
// Check if the middle element is a valid candidate.
if (nums[mid] >= target) {
// We found a candidate for the lower bound at index 'mid'.
ans = mid; // Update our best answer so far.
// Now, we need to check if there's a *better* candidate (earlier occurrence)
// to the LEFT of mid. So, we discard the right half including mid.
right = mid - 1;
} else {
// If nums[mid] < target, the lower bound cannot be at mid or to the left of mid.
// All elements in the left half are too small. We must search the RIGHT half.
left = mid + 1;
}
}
// After the loop, 'ans' holds the index of the first element >= target.
return ans;
}
}
Upper Bound in a Sorted Array
The upper bound of a target in a sorted array is the first index where the element is strictly greater than the target.
If no such element exists, return n (array length).
Example:
Input: nums = [3, 4, 6, 7, 9, 12, 16, 17], target = 6
Output: 3
Explanation: First element > 6 is 7 at index 3.
Input: nums = [3, 4, 6, 7, 9, 12, 16, 17], target = 17
Output: 8
Explanation: No element greater than 17, so return array length (8).
Brute Force Approach
Traverse the array linearly from start.
Return the first index
iwherenums[i] > target.If no such index exists, return
n.
Time Complexity: O(n)
Space Complexity: O(1)
Optimal Approach (Binary Search)
Initialize
left = 0,right = n - 1, andans = n.While
left <= right:Find
mid = left + (right - left) / 2.If
nums[mid] > target, updateans = midand search left (right = mid - 1).Else, search right (
left = mid + 1).
Return
ans.
Time Complexity: O(log n)
Space Complexity: O(1)
| Method | Time Complexity | Space Complexity |
| Brute Force | O(n) | O(1) |
| Optimal | O(log n) | O(1) |
import java.util.Arrays;
/**
* Demonstrates the concept of Upper Bound in a sorted array.
*
* Upper Bound Definition:
* The upper bound of a target value in a sorted array is the index of the first element
* that is strictly greater than (>) the target.
*
* Key Characteristics:
* - It finds the position where the target value would be inserted to maintain sorted order,
* but only after all existing instances of the target.
* - If the target exists, the upper bound points to the first element after the last occurrence of the target.
* - If the target does not exist, it behaves the same as the lower bound, returning the index of the first element greater than the target.
* - If all elements are smaller than or equal to the target, it returns the array's length.
*
* This is crucial for operations like finding the range of a value or inserting elements in sorted collections.
*/
class Main {
public static void main(String[] args) {
// A sorted array is essential for the upper bound algorithm
int[] nums = {3, 4, 6, 7, 9, 12, 16, 17};
int target1 = 6; // Exists in array - upper bound should be first element > 6
int target2 = 17; // Largest element - upper bound should be end of array (index 8)
System.out.println("Array: " + Arrays.toString(nums));
System.out.println("Target 1: " + target1 + " | Target 2: " + target2 + "\n");
// Brute Force Approach
// Simple implementation but inefficient for large datasets
System.out.println("Brute Force (target=6): " + upperBoundBruteForce(nums, target1));
System.out.println("Brute Force (target=17): " + upperBoundBruteForce(nums, target2));
// Optimal Approach (Binary Search)
// Efficient algorithm using binary search principle
System.out.println("Optimal (target=6): " + upperBoundOptimal(nums, target1));
System.out.println("Optimal (target=17): " + upperBoundOptimal(nums, target2));
/* Expected Output:
Array: [3, 4, 6, 7, 9, 12, 16, 17]
Target 1: 6 | Target 2: 17
Brute Force (target=6): 3 -> Explanation: First element >6 is at index 3 (value 7)
Brute Force (target=17): 8 -> Explanation: No element >17, so returns array length
Optimal (target=6): 3
Optimal (target=17): 8
*/
}
// --- Brute Force Approach ---
/**
* Finds the upper bound by performing a linear scan through the array.
*
* @param nums The sorted array to search in
* @param target The value to find the upper bound for
* @return The index of the first element > target, or nums.length if no such element exists
*
* How it works:
* Iterates through each element sequentially until it finds the first element
* that is strictly greater than the target value.
*
* Time Complexity: O(n) - In worst case, may need to check all elements
* Space Complexity: O(1) - Uses constant extra space
*
* Limitations:
* - Inefficient for large arrays
* - Doesn't leverage the sorted property optimally
*/
public static int upperBoundBruteForce(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
// The moment we find an element strictly greater than target,
// we've found the upper bound position
if (nums[i] > target) {
return i;
}
}
// If no element greater than target is found,
// the upper bound is the position after the last element
return nums.length;
}
// --- Optimal Approach (Binary Search) ---
/**
* Finds the upper bound using binary search for optimal performance.
*
* @param nums The sorted array to search in
* @param target The value to find the upper bound for
* @return The index of the first element > target, or nums.length if no such element exists
*
* How it works:
* 1. Uses binary search to efficiently narrow down the search space
* 2. Maintains an 'ans' variable that stores the best candidate found so far
* 3. When nums[mid] > target, it's a potential upper bound candidate
* 4. The algorithm continues searching left to find an earlier (smaller index) candidate
* 5. When nums[mid] <= target, the search continues in the right half
*
* Time Complexity: O(log n) - Search space halved each iteration
* Space Complexity: O(1) - Constant space usage
*
* Advantages:
* - Extremely efficient even for very large arrays
* - Fully leverages the sorted property of the array
*/
public static int upperBoundOptimal(int[] nums, int target) {
// Initialize search space to entire array
int left = 0;
int right = nums.length - 1;
// Initialize answer to array length (default when no element > target)
int ans = nums.length;
// Continue while search space is valid
while (left <= right) {
// Calculate middle index - prevents integer overflow
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
// Found a candidate for upper bound at index 'mid'
ans = mid; // Update best candidate found so far
// Search left half to see if there's an earlier candidate
// that also satisfies nums[i] > target
right = mid - 1;
} else {
// nums[mid] <= target, so upper bound must be to the right
// All elements including mid are not greater than target
left = mid + 1;
}
}
// Return the index of first element greater than target
return ans;
}
}
Search Insert Position
The problem is to return the index of a target in a sorted array if it exists.
If it does not exist, return the index where it should be inserted to maintain sorted order.
This is basically the Lower Bound problem.
Example:
Input: nums = [1, 3, 5, 6], target = 5
Output: 2
Explanation: 5 is found at index 2.
Input: nums = [1, 3, 5, 6], target = 2
Output: 1
Explanation: 2 should be inserted at index 1.
Input: nums = [1, 3, 5, 6], target = 7
Output: 4
Explanation: 7 should be inserted at the end.
Brute Force Approach
Traverse the array linearly from start.
If
nums[i] >= target, return indexi.If the target is greater than all elements, return
n.
Time Complexity: O(n)
Space Complexity: O(1)
Optimal Approach (Binary Search)
Initialize
left = 0,right = n - 1,ans = n.While
left <= right:Find
mid = left + (right - left) / 2.If
nums[mid] >= target, updateans = midand moveright = mid - 1.Else, move
left = mid + 1.
Return
ans.
Time Complexity: O(log n)
Space Complexity: O(1)
| Method | Time Complexity | Space Complexity |
| Brute Force | O(n) | O(1) |
| Optimal | O(log n) | O(1) |
import java.util.Arrays;
/**
* Demonstrates the Search Insert Position problem in a sorted array.
*
* Problem Definition:
* Given a sorted array of distinct integers and a target value, return the index
* where the target would be inserted to maintain the sorted order.
*
* Key Characteristics:
* - If the target exists in the array, return its index.
* - If the target does not exist, return the index where it should be inserted
* to keep the array sorted.
* - This is essentially the same as finding the LOWER BOUND of the target value.
*
* The search insert position is the first position where the element is >= target.
* This makes it identical to the lower bound concept.
*/
class Main {
public static void main(String[] args) {
// Sorted array with distinct integers (no duplicates)
int[] nums = {1, 3, 5, 6};
System.out.println("Array: " + Arrays.toString(nums));
System.out.println();
// Test cases demonstrating different scenarios:
// 1. Target exists in array (5)
// 2. Target doesn't exist, should be inserted in middle (2)
// 3. Target larger than all elements, should be inserted at end (7)
// Brute Force Approach
System.out.println("Brute Force (target=5): " + searchInsertBruteForce(nums, 5));
System.out.println("Brute Force (target=2): " + searchInsertBruteForce(nums, 2));
System.out.println("Brute Force (target=7): " + searchInsertBruteForce(nums, 7));
// Optimal Approach (Binary Search)
System.out.println("Optimal (target=5): " + searchInsertOptimal(nums, 5));
System.out.println("Optimal (target=2): " + searchInsertOptimal(nums, 2));
System.out.println("Optimal (target=7): " + searchInsertOptimal(nums, 7));
/* Expected Output:
Array: [1, 3, 5, 6]
Brute Force (target=5): 2 -> Target exists at index 2
Brute Force (target=2): 1 -> Should be inserted between 1 and 3 (index 1)
Brute Force (target=7): 4 -> Should be inserted at end (index 4)
Optimal (target=5): 2
Optimal (target=2): 1
Optimal (target=7): 4
*/
}
// --- Brute Force Approach ---
/**
* Finds the insert position by performing a linear scan through the array.
*
* @param nums The sorted array to search in
* @param target The value to find insert position for
* @return The index where target should be inserted to maintain sorted order
*
* How it works:
* Iterates through each element until it finds the first element that is
* greater than or equal to the target. This position is where the target
* should be inserted (or where it already exists).
*
* Time Complexity: O(n) - May need to check all elements in worst case
* Space Complexity: O(1) - Uses constant extra space
*
* Limitations:
* - Inefficient for large arrays
* - Doesn't leverage the sorted property optimally
*/
public static int searchInsertBruteForce(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
// The moment we find an element >= target, we've found the insert position
// This handles both cases:
// 1. If element == target: return that index (target exists)
// 2. If element > target: return this index (insert before this element)
if (nums[i] >= target) {
return i;
}
}
// If all elements are smaller than target,
// the insert position is at the end of the array
return nums.length;
}
// --- Optimal Approach (Binary Search) ---
/**
* Finds the insert position using binary search for optimal performance.
* This is identical to finding the lower bound of the target.
*
* @param nums The sorted array to search in
* @param target The value to find insert position for
* @return The index where target should be inserted to maintain sorted order
*
* How it works:
* 1. Uses binary search to efficiently narrow down the search space
* 2. Maintains an 'ans' variable that stores the best candidate found so far
* 3. When nums[mid] >= target, it's a potential insert position candidate
* 4. The algorithm continues searching left to find the first such position
* 5. When nums[mid] < target, the search continues in the right half
*
* Time Complexity: O(log n) - Search space halved each iteration
* Space Complexity: O(1) - Constant space usage
*
* Advantages:
* - Extremely efficient even for very large arrays
* - Fully leverages the sorted property of the array
* - Handles all edge cases elegantly
*/
public static int searchInsertOptimal(int[] nums, int target) {
// Initialize search space to entire array
int left = 0;
int right = nums.length - 1;
// Initialize answer to array length (default when target > all elements)
int ans = nums.length;
// Continue while search space is valid
while (left <= right) {
// Calculate middle index - prevents integer overflow
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
// Found a candidate for insert position at index 'mid'
// This could be either:
// 1. The exact target position (if nums[mid] == target)
// 2. The insert position before a larger element (if nums[mid] > target)
ans = mid; // Update best candidate found so far
// Search left half to see if there's an earlier candidate
// that also satisfies nums[i] >= target (we want the FIRST such position)
right = mid - 1;
} else {
// nums[mid] < target, so insert position must be to the right
// All elements including mid are smaller than target
left = mid + 1;
}
}
// Return the optimal insert position
return ans;
}
}
Floor and Ceil in a Sorted Array
Floor of a target = the greatest element in the array ≤ target.
Ceil of a target = the smallest element in the array ≥ target.
If floor/ceil does not exist, return -1.
Example
Array: [3, 4, 6, 7, 9, 12, 16, 17]
Target = 8
Floor = 7 (largest element ≤ 8)
Ceil = 9 (smallest element ≥ 8)
Target = 2
Floor = -1 (no element ≤ 2)
Ceil = 3 (smallest element ≥ 2)
Target = 20
Floor = 17 (largest element ≤ 20)
Ceil = -1 (no element ≥ 20)
Brute Force Approach
Initialize
floor = -1,ceil = -1.Traverse the array linearly:
For floor: keep track of the largest element ≤ target.
For ceil: keep track of the smallest element ≥ target.
Return the results.
Time Complexity: O(n)
Space Complexity: O(1)
Optimal Approach (Binary Search)
Floor (≤ target)
Initialize
ans = -1,left = 0,right = n-1.While
left <= right:Compute
mid.If
nums[mid] ≤ target, updateans = nums[mid]and search right.Else search left.
Return
ans.
Ceil (≥ target)
Initialize
ans = -1,left = 0,right = n-1.While
left <= right:Compute
mid.If
nums[mid] ≥ target, updateans = nums[mid]and search left.Else search right.
Return
ans.
Time Complexity: O(log n)
Space Complexity: O(1)
| Method | Time Complexity | Space Complexity |
| Brute Force | O(n) | O(1) |
| Optimal | O(log n) | O(1) |
import java.util.Arrays;
/**
* Demonstrates the concepts of Floor and Ceil in a sorted array.
*
* Definitions:
* - Floor of a target: The largest element in the array that is less than or equal to the target.
* - Ceil of a target: The smallest element in the array that is greater than or equal to the target.
*
* Key Characteristics:
* - Floor and Ceil may be the same value if the target exists in the array.
* - If the target doesn't exist, floor is the next smallest value and ceil is the next largest value.
* - If target is smaller than all elements, floor doesn't exist (-1) but ceil is the smallest element.
* - If target is larger than all elements, floor is the largest element but ceil doesn't exist (-1).
*
* These concepts are fundamental in mathematical computations, range queries, and database operations.
*/
class Main {
public static void main(String[] args) {
// Sorted array is essential for both brute-force and optimal approaches
int[] nums = {3, 4, 6, 7, 9, 12, 16, 17};
int target = 8; // Target doesn't exist in array
System.out.println("Array: " + Arrays.toString(nums));
System.out.println("Target: " + target + "\n");
// Brute Force Approach
// Simple implementations but inefficient for large datasets
System.out.println("Brute Force Floor(8): " + floorBruteForce(nums, 8));
System.out.println("Brute Force Ceil(8): " + ceilBruteForce(nums, 8));
// Optimal Approach (Binary Search)
// Efficient algorithms using binary search principle
System.out.println("Optimal Floor(8): " + floorOptimal(nums, 8));
System.out.println("Optimal Ceil(8): " + ceilOptimal(nums, 8));
/* Expected Output:
Array: [3, 4, 6, 7, 9, 12, 16, 17]
Target: 8
Brute Force Floor(8): 7 -> Largest element <= 8
Brute Force Ceil(8): 9 -> Smallest element >= 8
Optimal Floor(8): 7
Optimal Ceil(8): 9
*/
}
// --- Brute Force Floor ---
/**
* Finds the floor value by performing a linear scan through the array.
*
* @param nums The sorted array to search in
* @param target The value to find floor for
* @return The largest element <= target, or -1 if no such element exists
*
* How it works:
* Iterates through each element and keeps track of the largest value
* encountered that is less than or equal to the target.
* Since the array is sorted, the last valid element found will be the floor.
*
* Time Complexity: O(n) - Must check every element in worst case
* Space Complexity: O(1) - Uses constant extra space
*
* Limitations:
* - Inefficient for large arrays
* - Doesn't leverage the sorted property optimally
*/
public static int floorBruteForce(int[] nums, int target) {
int floor = -1; // Initialize to -1 (not found)
for (int num : nums) {
if (num <= target) {
// Update floor to current valid value
// Since array is sorted, the last valid value will be the largest valid value
floor = num;
}
}
return floor;
}
// --- Brute Force Ceil ---
/**
* Finds the ceil value by performing a linear scan through the array.
*
* @param nums The sorted array to search in
* @param target The value to find ceil for
* @return The smallest element >= target, or -1 if no such element exists
*
* How it works:
* Iterates through each element until it finds the first element that is
* greater than or equal to the target. Due to the sorted nature of the array,
* this will be the smallest such element.
*
* Time Complexity: O(n) - May find ceil quickly, but worst case is O(n)
* Space Complexity: O(1) - Uses constant extra space
*/
public static int ceilBruteForce(int[] nums, int target) {
int ceil = -1; // Initialize to -1 (not found)
for (int num : nums) {
if (num >= target) {
// Found the first element >= target
// Due to sorted order, this is the smallest such element
ceil = num;
break; // No need to check further
}
}
return ceil;
}
// --- Optimal Floor using Binary Search ---
/**
* Finds the floor value using binary search for optimal performance.
*
* @param nums The sorted array to search in
* @param target The value to find floor for
* @return The largest element <= target, or -1 if no such element exists
*
* How it works:
* 1. Uses binary search to efficiently narrow down the search space
* 2. When nums[mid] <= target, it's a valid floor candidate
* 3. The algorithm stores this candidate and searches RIGHT to find a larger valid candidate
* 4. When nums[mid] > target, the search continues in the LEFT half
*
* Time Complexity: O(log n) - Search space halved each iteration
* Space Complexity: O(1) - Constant space usage
*
* Advantages:
* - Extremely efficient for large arrays
* - Fully leverages the sorted property
*/
public static int floorOptimal(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int ans = -1; // Initialize to not found
while (left <= right) {
int mid = left + (right - left) / 2; // Prevent overflow
if (nums[mid] <= target) {
// Found a valid floor candidate
ans = nums[mid]; // Update best candidate
// Search RIGHT half to find a larger valid candidate
// We want the LARGEST element <= target
left = mid + 1;
} else {
// nums[mid] > target, so valid floor must be in LEFT half
right = mid - 1;
}
}
return ans;
}
// --- Optimal Ceil using Binary Search ---
/**
* Finds the ceil value using binary search for optimal performance.
*
* @param nums The sorted array to search in
* @param target The value to find ceil for
* @return The smallest element >= target, or -1 if no such element exists
*
* How it works:
* 1. Uses binary search to efficiently narrow down the search space
* 2. When nums[mid] >= target, it's a valid ceil candidate
* 3. The algorithm stores this candidate and searches LEFT to find a smaller valid candidate
* 4. When nums[mid] < target, the search continues in the RIGHT half
*
* Time Complexity: O(log n) - Search space halved each iteration
* Space Complexity: O(1) - Constant space usage
*
* Note: This is identical to the lower bound algorithm but returns the value instead of index
*/
public static int ceilOptimal(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int ans = -1; // Initialize to not found
while (left <= right) {
int mid = left + (right - left) / 2; // Prevent overflow
if (nums[mid] >= target) {
// Found a valid ceil candidate
ans = nums[mid]; // Update best candidate
// Search LEFT half to find a smaller valid candidate
// We want the SMALLEST element >= target
right = mid - 1;
} else {
// nums[mid] < target, so valid ceil must be in RIGHT half
left = mid + 1;
}
}
return ans;
}
}
Last Occurrence in a Sorted Array
Definition: Given a sorted array (possibly with duplicates) and a target, find the index of the last occurrence of the target.
If the target does not exist, return
-1.
Example
Array: [2, 4, 4, 4, 7, 8, 10]
Target = 4
Last Occurrence = index 3
Target = 6
Last Occurrence = -1
Target = 10
Last Occurrence = index 6
Brute Force Approach
Traverse the array from left to right.
Keep updating the index whenever the target is found.
Return the last updated index.
Time Complexity: O(n)
Space Complexity: O(1)
Optimal Approach (Binary Search)
Initialize
ans = -1,left = 0,right = n-1.While
left <= right:Compute
mid.If
nums[mid] == target, updateans = midand search right (since we want the last occurrence).If
nums[mid] < target, moveleft = mid + 1.Else move
right = mid - 1.
Return
ans.
Time Complexity: O(log n)
Space Complexity: O(1)
| Method | Time Complexity | Space Complexity |
| Brute Force | O(n) | O(1) |
| Optimal | O(log n) | O(1) |
import java.util.Arrays;
/**
* Demonstrates finding Last Occurrence of a target in a sorted array.
* This class showcases both brute force and optimal approaches for solving
* the problem of finding the last occurrence of an element in a sorted array.
*/
class Main {
public static void main(String[] args) {
int[] nums = {2, 4, 4, 4, 7, 8, 10};
System.out.println("Array: " + Arrays.toString(nums));
// Brute Force Approach
// Time Complexity: O(n) - Linear search through entire array
// Space Complexity: O(1) - Constant extra space
System.out.println("Brute Force Last Occurrence of 4: " + lastOccurrenceBruteForce(nums, 4));
// Optimal Approach (Binary Search)
// Time Complexity: O(log n) - Binary search halves search space each iteration
// Space Complexity: O(1) - Constant extra space
System.out.println("Optimal Last Occurrence of 4: " + lastOccurrenceOptimal(nums, 4));
/* Expected Output:
Array: [2, 4, 4, 4, 7, 8, 10]
Brute Force Last Occurrence of 4: 3
Optimal Last Occurrence of 4: 3
*/
}
/**
* BRUTE FORCE APPROACH
* Finds the last occurrence of target by scanning the entire array linearly.
*
* Algorithm:
* 1. Initialize index to -1 (indicating target not found)
* 2. Traverse the array from start to end
* 3. For each element equal to target, update index to current position
* 4. The last update will be the last occurrence
*
* Pros: Simple to implement and understand
* Cons: Inefficient for large arrays (O(n) time complexity)
*
* @param nums The sorted array to search in
* @param target The element to find the last occurrence of
* @return The index of the last occurrence, or -1 if not found
*/
public static int lastOccurrenceBruteForce(int[] nums, int target) {
int index = -1; // Initialize to -1 (not found)
// Linear scan through entire array
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
index = i; // Update index whenever target is found
// This naturally captures the last occurrence because
// we keep updating until we find a larger element
}
}
return index;
}
/**
* OPTIMAL APPROACH (BINARY SEARCH)
* Finds the last occurrence of target using modified binary search.
*
* Algorithm:
* 1. Use binary search to quickly locate the target
* 2. When target is found at mid, don't stop immediately
* 3. Instead, continue searching in the right half to find later occurrences
* 4. Keep updating the answer whenever target is found
* 5. The binary search continues until the entire array is processed
*
* Pros: Extremely efficient (O(log n) time complexity)
* Cons: Slightly more complex implementation
*
* @param nums The sorted array to search in (MUST be sorted for binary search)
* @param target The element to find the last occurrence of
* @return The index of the last occurrence, or -1 if not found
*/
public static int lastOccurrenceOptimal(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int ans = -1; // Stores the best answer found so far
// Binary search loop - continues while search space is valid
while (left <= right) {
// Calculate mid point (avoids integer overflow compared to (left+right)/2)
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// Target found at mid, but might not be the last occurrence
ans = mid; // Update answer to current position
left = mid + 1; // Continue searching in RIGHT half for later occurrences
// This is the key insight: even though we found the target,
// we continue searching to the right to find the last occurrence
}
else if (nums[mid] < target) {
// Target is larger than current mid element
left = mid + 1; // Search in RIGHT half
}
else {
// Target is smaller than current mid element
right = mid - 1; // Search in LEFT half
}
}
return ans;
}
}
Count Occurrences in Sorted Array
Definition: Given a sorted array (possibly with duplicates) and a target, return how many times the target appears.
Example
Array: [2, 4, 4, 4, 7, 8, 10]
Target = 4
Occurrences = 3
Target = 7
Occurrences = 1
Target = 5
Occurrences = 0
Brute Force Approach
Traverse the array linearly.
Maintain a counter that increments whenever
nums[i] == target.Return the counter.
Time Complexity: O(n)
Space Complexity: O(1)
Optimal Approach (Binary Search)
Find the First Occurrence of the target using binary search.
Find the Last Occurrence of the target using binary search.
If the target does not exist (
first == -1), return0.Otherwise, occurrences =
(last - first + 1).
Time Complexity: O(log n)
Space Complexity: O(1)
| Method | Time Complexity | Space Complexity |
| Brute Force | O(n) | O(1) |
| Optimal | O(log n) | O(1) |
import java.util.Arrays;
/**
* Demonstrates counting occurrences of a target in a sorted array.
* This class showcases both brute force and optimal approaches for
* counting the frequency of an element in a sorted array.
*/
class Main {
public static void main(String[] args) {
int[] nums = {2, 4, 4, 4, 7, 8, 10};
System.out.println("Array: " + Arrays.toString(nums));
// Brute Force Approach
// Time Complexity: O(n) - Linear scan through entire array
// Space Complexity: O(1) - Constant extra space
System.out.println("Brute Force Count of 4: " + countOccurrencesBruteForce(nums, 4));
// Optimal Approach using Binary Search
// Time Complexity: O(log n) - Two binary searches
// Space Complexity: O(1) - Constant extra space
System.out.println("Optimal Count of 4: " + countOccurrencesOptimal(nums, 4));
/* Expected Output:
Array: [2, 4, 4, 4, 7, 8, 10]
Brute Force Count of 4: 3
Optimal Count of 4: 3
*/
}
/**
* BRUTE FORCE APPROACH
* Counts occurrences of target by scanning the entire array linearly.
*
* Algorithm:
* 1. Initialize count to 0
* 2. Traverse the array from start to end
* 3. For each element equal to target, increment count
* 4. Return the total count
*
* Pros: Simple implementation, easy to understand
* Cons: Inefficient for large arrays (O(n) time complexity)
* Doesn't leverage the sorted property of the array
*
* @param nums The sorted array to search in
* @param target The element to count occurrences of
* @return The number of times target appears in the array
*/
public static int countOccurrencesBruteForce(int[] nums, int target) {
int count = 0; // Initialize counter
// Enhanced for loop: iterate through each element
for (int num : nums) {
if (num == target) {
count++; // Increment count for each occurrence
}
// Since array is sorted, we could break early if num > target
// but this implementation doesn't optimize for that
}
return count;
}
/**
* OPTIMAL APPROACH USING BINARY SEARCH
* Counts occurrences by finding first and last positions using binary search.
*
* Algorithm:
* 1. Find first occurrence of target using binary search
* 2. If not found, return 0 (target doesn't exist)
* 3. Find last occurrence of target using binary search
* 4. Calculate count = (last index - first index + 1)
*
* Pros: Extremely efficient (O(log n) time complexity)
* Leverages sorted property optimally
* Cons: More complex implementation with helper methods
*
* @param nums The sorted array to search in (MUST be sorted)
* @param target The element to count occurrences of
* @return The number of times target appears in the array
*/
public static int countOccurrencesOptimal(int[] nums, int target) {
// Step 1: Find the first occurrence index
int first = firstOccurrence(nums, target);
// If target not found, return 0 immediately
if (first == -1) {
return 0;
}
// Step 2: Find the last occurrence index
int last = lastOccurrence(nums, target);
// Step 3: Calculate total occurrences
// Formula: (last_index - first_index + 1)
return last - first + 1;
}
/**
* HELPER METHOD: FIND FIRST OCCURRENCE
* Uses modified binary search to find the first occurrence of target.
*
* Algorithm:
* 1. Use binary search to locate target
* 2. When target found at mid, don't stop immediately
* 3. Instead, continue searching LEFT half to find earlier occurrences
* 4. Keep updating answer to track the earliest found position
*
* @param nums The sorted array to search in
* @param target The element to find first occurrence of
* @return Index of first occurrence, or -1 if not found
*/
private static int firstOccurrence(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int ans = -1; // Stores the earliest found position
while (left <= right) {
// Calculate mid point (prevents integer overflow)
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
ans = mid; // Update answer to current position
right = mid - 1; // Continue searching LEFT half for earlier occurrences
// This is the key: even though we found target, we search left
// to find the first occurrence
}
else if (nums[mid] < target) {
// Target is in right half
left = mid + 1;
}
else {
// Target is in left half
right = mid - 1;
}
}
return ans;
}
/**
* HELPER METHOD: FIND LAST OCCURRENCE
* Uses modified binary search to find the last occurrence of target.
*
* Algorithm:
* 1. Use binary search to locate target
* 2. When target found at mid, don't stop immediately
* 3. Instead, continue searching RIGHT half to find later occurrences
* 4. Keep updating answer to track the latest found position
*
* @param nums The sorted array to search in
* @param target The element to find last occurrence of
* @return Index of last occurrence, or -1 if not found
*/
private static int lastOccurrence(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int ans = -1; // Stores the latest found position
while (left <= right) {
// Calculate mid point (prevents integer overflow)
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
ans = mid; // Update answer to current position
left = mid + 1; // Continue searching RIGHT half for later occurrences
// This is the key: even though we found target, we search right
// to find the last occurrence
}
else if (nums[mid] < target) {
// Target is in right half
left = mid + 1;
}
else {
// Target is in left half
right = mid - 1;
}
}
return ans;
}
}
Search Element in a Rotated Sorted Array
Definition: You are given a sorted array that is rotated at some pivot unknown to you. Your task is to determine if a target element exists in the array and return its index. If not found, return -1.
Array does not contain duplicate elements.
Example
Array: [4, 5, 6, 7, 0, 1, 2]
Target = 0 → Output = 4
Array: [4, 5, 6, 7, 0, 1, 2]
Target = 3 → Output = -1
Array: [1]
Target = 1 → Output = 0
Brute Force Approach
Traverse the array linearly.
If element matches target, return its index.
If not found, return
-1.
Time Complexity: O(n)
Space Complexity: O(1)
Optimal Approach (Modified Binary Search)
Initialize
left = 0,right = n - 1.While
left <= right:Find
mid.If
nums[mid] == target, returnmid.Determine which half is sorted:
If
nums[left] <= nums[mid]: left half is sorted.Check if
targetlies in this half.If yes, move
right = mid - 1, elseleft = mid + 1.
Else: right half is sorted.
Check if
targetlies in this half.If yes, move
left = mid + 1, elseright = mid - 1.
If not found, return
-1.
Time Complexity: O(log n)
Space Complexity: O(1)
| Method | Time Complexity | Space Complexity |
| Brute Force | O(n) | O(1) |
| Optimal | O(log n) | O(1) |
import java.util.Arrays;
/**
* Demonstrates searching in a rotated sorted array.
* A rotated sorted array is a sorted array that has been rotated at some pivot point.
* Example: [4,5,6,7,0,1,2] is rotated at index 3 (element 7)
*/
class Main {
public static void main(String[] args) {
int[] nums = {4, 5, 6, 7, 0, 1, 2};
System.out.println("Array: " + Arrays.toString(nums));
// Brute Force Approach
// Time Complexity: O(n) - Linear scan through entire array
// Space Complexity: O(1) - Constant extra space
System.out.println("Brute Force Search for 0: " + searchBruteForce(nums, 0));
// Optimal Approach using Modified Binary Search
// Time Complexity: O(log n) - Binary search with rotation handling
// Space Complexity: O(1) - Constant extra space
System.out.println("Optimal Search for 0: " + searchOptimal(nums, 0));
System.out.println("Optimal Search for 3: " + searchOptimal(nums, 3));
/* Expected Output:
Array: [4, 5, 6, 7, 0, 1, 2]
Brute Force Search for 0: 4
Optimal Search for 0: 4
Optimal Search for 3: -1
*/
}
/**
* BRUTE FORCE APPROACH
* Searches for target by scanning the entire array linearly.
*
* Algorithm:
* 1. Iterate through each element from start to end
* 2. Return index immediately when target is found
* 3. Return -1 if target not found after scanning entire array
*
* Pros: Simple implementation, works on any array (sorted or not)
* Cons: Inefficient for large arrays (O(n) time complexity)
* Doesn't leverage the partially sorted nature of rotated array
*
* @param nums The rotated sorted array to search in
* @param target The element to search for
* @return The index of target, or -1 if not found
*/
public static int searchBruteForce(int[] nums, int target) {
// Linear scan through entire array
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return i; // Return immediately when found
}
}
return -1; // Target not found
}
/**
* OPTIMAL APPROACH USING MODIFIED BINARY SEARCH
* Searches for target using binary search adapted for rotated arrays.
*
* Key Insight: In a rotated sorted array, at least one half
* (left or right of mid) is always properly sorted.
*
* Algorithm:
* 1. Use binary search to find mid point
* 2. Check if target is at mid (return if found)
* 3. Determine which half is sorted
* 4. Check if target lies within the sorted half
* 5. Adjust search boundaries accordingly
*
* Pros: Extremely efficient (O(log n) time complexity)
* Leverages the partially sorted property optimally
* Cons: More complex logic to handle rotation
*
* @param nums The rotated sorted array to search in
* @param target The element to search for
* @return The index of target, or -1 if not found
*/
public static int searchOptimal(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Prevents integer overflow
// Case 1: Target found at mid point
if (nums[mid] == target) {
return mid;
}
// Case 2: Left half [left...mid] is sorted
if (nums[left] <= nums[mid]) {
/**
* Check if target is within the sorted left half:
* - target >= nums[left]: Target is greater than or equal to left boundary
* - target < nums[mid]: Target is less than mid (since we already checked equality)
*
* If both conditions true, target must be in left sorted half
*/
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1; // Search in left sorted half
} else {
left = mid + 1; // Search in right half (which may be rotated)
}
}
// Case 3: Right half [mid...right] is sorted
else {
/**
* Check if target is within the sorted right half:
* - target > nums[mid]: Target is greater than mid
* - target <= nums[right]: Target is less than or equal to right boundary
*
* If both conditions true, target must be in right sorted half
*/
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1; // Search in right sorted half
} else {
right = mid - 1; // Search in left half (which may be rotated)
}
}
}
return -1; // Target not found
}
}
Search Element in a Rotated Sorted Array (With Duplicates)
Definition: You are given a sorted array that is rotated at some pivot unknown to you. The array may contain duplicates.
Your task is to determine if a target exists in the array and return its index. If not found, return
-1.
Example
Array: [2, 5, 6, 0, 0, 1, 2]
Target = 0 → Output = 3 or 4 (any valid index)
Array: [2, 5, 6, 0, 0, 1, 2]
Target = 3 → Output = -1
Array: [1, 1, 3, 1]
Target = 3 → Output = 2
Brute Force Approach
Traverse the array linearly.
If element matches target, return its index.
If not found, return
-1.
Time Complexity: O(n)
Space Complexity: O(1)
Optimal Approach (Modified Binary Search with Duplicates)
The only difference from the unique-element version is handling duplicates.
Initialize
left = 0,right = n - 1.While
left <= right:Find
mid.If
nums[mid] == target, returnmid.If duplicates cause ambiguity (
nums[left] == nums[mid] == nums[right]), shrink the window:left++andright--.Otherwise, proceed like before:
If left half is sorted (
nums[left] <= nums[mid]):If target lies within
[nums[left], nums[mid]), moveright = mid - 1.Else, move
left = mid + 1.
Else right half is sorted:
If target lies within
(nums[mid], nums[right]], moveleft = mid + 1.Else, move
right = mid - 1.
If not found, return
-1.
Time Complexity:
Worst-case: O(n) (when many duplicates exist, e.g.,
[1,1,1,1,1])Average: O(log n)
Space Complexity: O(1)
| Method | Time Complexity | Space Complexity |
| Brute Force | O(n) | O(1) |
| Optimal | O(log n) avg, O(n) worst | O(1) |
import java.util.Arrays;
/**
* Demonstrates searching in a rotated sorted array with duplicates.
* This handles the more complex case where the array may contain duplicate values.
*/
class Main {
public static void main(String[] args) {
int[] nums = {2, 5, 6, 0, 0, 1, 2};
System.out.println("Array: " + Arrays.toString(nums));
// Brute Force Approach
// Time Complexity: O(n) - Linear scan through entire array
// Space Complexity: O(1) - Constant extra space
System.out.println("Brute Force Search for 0: " + searchBruteForce(nums, 0));
// Optimal Approach using Modified Binary Search
// Time Complexity: O(n) in worst case due to duplicates, O(log n) in best case
// Space Complexity: O(1) - Constant extra space
System.out.println("Optimal Search for 0: " + searchOptimal(nums, 0));
System.out.println("Optimal Search for 3: " + searchOptimal(nums, 3));
/* Expected Output (Index may vary for duplicates):
Array: [2, 5, 6, 0, 0, 1, 2]
Brute Force Search for 0: 3
Optimal Search for 0: 3
Optimal Search for 3: -1
*/
}
/**
* BRUTE FORCE APPROACH
* Searches for target by scanning the entire array linearly.
*
* Algorithm:
* 1. Iterate through each element from start to end
* 2. Return index immediately when target is found
* 3. Return -1 if target not found after scanning entire array
*
* Pros: Simple implementation, guaranteed to work with duplicates
* Cons: Inefficient for large arrays (O(n) time complexity)
* Doesn't leverage the partially sorted nature
*
* @param nums The rotated sorted array with duplicates
* @param target The element to search for
* @return The index of target, or -1 if not found
*/
public static int searchBruteForce(int[] nums, int target) {
// Linear scan through entire array
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return i; // Return immediately when found
}
}
return -1; // Target not found
}
/**
* OPTIMAL APPROACH USING MODIFIED BINARY SEARCH
* Searches for target using binary search adapted for rotated arrays with duplicates.
*
* Key Challenges with Duplicates:
* - Cannot always determine which half is sorted due to duplicates
* - Worst case degenerates to O(n) when many duplicates exist
* - Requires additional checks to handle edge cases
*
* Algorithm:
* 1. Use binary search to find mid point
* 2. Check if target is at mid (return if found)
* 3. Handle the duplicate case where boundaries are equal
* 4. Determine which half is sorted (if possible)
* 5. Check if target lies within the sorted half
* 6. Adjust search boundaries accordingly
*
* @param nums The rotated sorted array with duplicates
* @param target The element to search for
* @return The index of target, or -1 if not found
*/
public static int searchOptimal(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Prevents integer overflow
// Case 1: Target found at mid point
if (nums[mid] == target) {
return mid;
}
// Case 2: Handle duplicates - when left, mid, and right are equal
// This is the key addition for handling duplicates
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
/**
* When all three points are equal, we cannot determine which half is sorted.
* Example: [1,1,1,2,1,1,1] - both halves might contain the target
* Strategy: Shrink the search space from both ends
* Time Complexity: This can degenerate to O(n) in worst case
*/
left++; // Move left boundary inward
right--; // Move right boundary inward
continue; // Restart the loop with updated boundaries
}
// Case 3: Left half [left...mid] is sorted (or mostly sorted)
else if (nums[left] <= nums[mid]) {
/**
* Check if target is within the sorted left half:
* - target >= nums[left]: Target is in range of left boundary
* - target < nums[mid]: Target is less than mid value
*
* If both conditions true, target must be in left sorted half
*/
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1; // Search in left sorted half
} else {
left = mid + 1; // Search in right half
}
}
// Case 4: Right half [mid...right] is sorted (or mostly sorted)
else {
/**
* Check if target is within the sorted right half:
* - target > nums[mid]: Target is greater than mid value
* - target <= nums[right]: Target is in range of right boundary
*
* If both conditions true, target must be in right sorted half
*/
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1; // Search in right sorted half
} else {
right = mid - 1; // Search in left half
}
}
}
return -1; // Target not found
}
}
Minimum in Rotated Sorted Array
Definition: You are given a rotated sorted array without duplicates. Find the minimum element.
Example
Array: [3, 4, 5, 1, 2] → Minimum = 1
Array: [4, 5, 6, 7, 0, 1, 2] → Minimum = 0
Array: [11, 13, 15, 17] → Minimum = 11
Brute Force Approach
Traverse the entire array.
Track the minimum element.
Return the minimum at the end.
Time Complexity: O(n)
Space Complexity: O(1)
Optimal Approach (Binary Search)
Initialize
left = 0,right = n - 1.While
left < right:Find
mid = left + (right - left) / 2.If
nums[mid] > nums[right], the minimum lies in the right half →left = mid + 1.Otherwise, the minimum lies in the left half →
right = mid.
After the loop,
nums[left]will be the minimum.
Time Complexity: O(log n)
Space Complexity: O(1)
| Method | Time Complexity | Space Complexity |
| Brute Force | O(n) | O(1) |
| Optimal | O(log n) | O(1) |
import java.util.Arrays;
/**
* Demonstrates finding minimum in a rotated sorted array without duplicates.
* The array is sorted in ascending order and then rotated at some unknown pivot.
*/
class Main {
public static void main(String[] args) {
int[] nums1 = {3, 4, 5, 1, 2}; // Rotated at pivot 3 (element 5)
int[] nums2 = {4, 5, 6, 7, 0, 1, 2}; // Rotated at pivot 4 (element 7)
int[] nums3 = {11, 13, 15, 17}; // Not rotated (already sorted)
System.out.println("Array: " + Arrays.toString(nums1));
System.out.println("Brute Force Minimum: " + findMinBruteForce(nums1));
System.out.println("Optimal Minimum: " + findMinOptimal(nums1));
System.out.println("\nArray: " + Arrays.toString(nums2));
System.out.println("Brute Force Minimum: " + findMinBruteForce(nums2));
System.out.println("Optimal Minimum: " + findMinOptimal(nums2));
System.out.println("\nArray: " + Arrays.toString(nums3));
System.out.println("Brute Force Minimum: " + findMinBruteForce(nums3));
System.out.println("Optimal Minimum: " + findMinOptimal(nums3));
/* Expected Output:
Array: [3, 4, 5, 1, 2]
Brute Force Minimum: 1
Optimal Minimum: 1
Array: [4, 5, 6, 7, 0, 1, 2]
Brute Force Minimum: 0
Optimal Minimum: 0
Array: [11, 13, 15, 17]
Brute Force Minimum: 11
Optimal Minimum: 11
*/
}
/**
* BRUTE FORCE APPROACH
* Finds the minimum value by scanning the entire array linearly.
*
* Algorithm:
* 1. Initialize min to the first element
* 2. Traverse through each element in the array
* 3. Update min whenever a smaller element is found
* 4. Return the minimum value
*
* Pros: Simple implementation, works on any array (sorted, rotated, or unsorted)
* Cons: Inefficient for large arrays (O(n) time complexity)
* Doesn't leverage the sorted-rotated property
*
* @param nums The rotated sorted array without duplicates
* @return The minimum element in the array
*/
public static int findMinBruteForce(int[] nums) {
int min = nums[0]; // Assume first element is minimum initially
// Iterate through all elements to find the actual minimum
for (int num : nums) {
if (num < min) {
min = num; // Update min if current element is smaller
}
}
return min;
}
/**
* OPTIMAL APPROACH USING BINARY SEARCH
* Finds the minimum value using binary search adapted for rotated arrays.
*
* Key Insight: In a rotated sorted array, the minimum element is the only element
* that is smaller than both its neighbors (if they exist). More importantly:
* - The minimum element is at the pivot point where the array was rotated
* - All elements to the left of minimum are greater than all elements to the right
*
* Algorithm:
* 1. Use binary search to compare mid element with right boundary
* 2. If nums[mid] > nums[right], the minimum must be in the right half
* 3. Otherwise, the minimum must be in the left half (including mid)
* 4. Continue until left == right, then nums[left] is the minimum
*
* Time Complexity: O(log n) - Binary search halves the search space each iteration
* Space Complexity: O(1) - Constant extra space
*
* @param nums The rotated sorted array without duplicates
* @return The minimum element in the array
*/
public static int findMinOptimal(int[] nums) {
int left = 0, right = nums.length - 1;
// Continue until search space is reduced to one element
while (left < right) {
int mid = left + (right - left) / 2; // Prevents integer overflow
/**
* CRITICAL COMPARISON:
* Compare mid element with right boundary element
*
* If nums[mid] > nums[right]:
* - The right half must contain the minimum because:
* - The array was rotated, so the right half contains smaller values
* - Example: [3,4,5,1,2] where mid=2 (value=5) > right=4 (value=2)
* - Minimum (1) is indeed in the right half
*/
if (nums[mid] > nums[right]) {
left = mid + 1; // Minimum is in the right half (excluding mid)
}
/**
* If nums[mid] <= nums[right]:
* - The minimum is in the left half (including mid) because:
* - The right half is properly sorted and mid is already smaller than right
* - Example: [4,5,6,7,0,1,2] where mid=3 (value=7) > right=6 (value=2)
* (This case would be handled by the first condition)
* - Example: [11,13,15,17] where mid=1 (value=13) <= right=3 (value=17)
* Minimum is in left half including mid
*/
else {
right = mid; // Minimum is in left half (including mid)
}
}
// When left == right, we've found the minimum element
return nums[left];
}
}
Find out how many times the array has been rotated
Example
Array: [4, 5, 6, 7, 0, 1, 2] → Rotations = 4
Array: [11, 13, 15, 17] → Rotations = 0
Array: [3, 4, 5, 1, 2] → Rotations = 3
Brute Force Approach
Traverse the entire array.
Find the minimum element and its index.
Return the index as the rotation count.
Time Complexity: O(n)
Space Complexity: O(1)
Optimal Approach (Binary Search)
Initialize
left = 0,right = n - 1.If
nums[left] <= nums[right], the array is already sorted → Rotations = 0.While
left <= right:Find
mid.If
nums[mid] <= nums[right], move to left half → update answer andright = mid - 1.Else, move to right half →
left = mid + 1.
The final index of the minimum element is the rotation count.
Time Complexity: O(log n)
Space Complexity: O(1)
| Method | Time Complexity | Space Complexity |
| Brute Force | O(n) | O(1) |
| Optimal | O(log n) | O(1) |
import java.util.Arrays;
/**
* Demonstrates finding number of times a sorted array is rotated.
* A rotated sorted array is one where elements have been shifted circularly.
* Example: [1,2,3,4,5] rotated 2 times becomes [3,4,5,1,2]
* The number of rotations equals the index of the minimum element.
*/
class Main {
public static void main(String[] args) {
// Test cases with different rotation scenarios
int[] nums1 = {4, 5, 6, 7, 0, 1, 2}; // Rotated 4 times
int[] nums2 = {11, 13, 15, 17}; // Not rotated (0 times)
int[] nums3 = {3, 4, 5, 1, 2}; // Rotated 3 times
// Test case 1: Array rotated multiple times
System.out.println("Array: " + Arrays.toString(nums1));
System.out.println("Brute Force Rotations: " + findRotationsBruteForce(nums1));
System.out.println("Optimal Rotations: " + findRotationsOptimal(nums1));
// Test case 2: Array not rotated (already sorted)
System.out.println("\nArray: " + Arrays.toString(nums2));
System.out.println("Brute Force Rotations: " + findRotationsBruteForce(nums2));
System.out.println("Optimal Rotations: " + findRotationsOptimal(nums2));
// Test case 3: Array rotated with minimum at different position
System.out.println("\nArray: " + Arrays.toString(nums3));
System.out.println("Brute Force Rotations: " + findRotationsBruteForce(nums3));
System.out.println("Optimal Rotations: " + findRotationsOptimal(nums3));
/* Expected Output:
Array: [4, 5, 6, 7, 0, 1, 2]
Brute Force Rotations: 4
Optimal Rotations: 4
Array: [11, 13, 15, 17]
Brute Force Rotations: 0
Optimal Rotations: 0
Array: [3, 4, 5, 1, 2]
Brute Force Rotations: 3
Optimal Rotations: 3
*/
}
/**
* Brute Force Method: Linear search for minimum element
* Time Complexity: O(n) - scans entire array in worst case
* Space Complexity: O(1) - uses constant extra space
*
* @param nums the rotated sorted array
* @return the number of rotations (index of minimum element)
*/
public static int findRotationsBruteForce(int[] nums) {
int minIndex = 0; // Assume first element is minimum initially
// Iterate through array to find actual minimum element
for (int i = 1; i < nums.length; i++) {
// If current element is smaller than current minimum
if (nums[i] < nums[minIndex]) {
minIndex = i; // Update minimum index
}
}
return minIndex; // Number of rotations equals index of minimum element
}
/**
* Optimal Method: Binary search for minimum element
* Time Complexity: O(log n) - halves search space each iteration
* Space Complexity: O(1) - uses constant extra space
*
* Key Insight: In a rotated sorted array, the minimum element is the only
* element that is smaller than both its neighbors (if they exist).
*
* @param nums the rotated sorted array
* @return the number of rotations (index of minimum element)
*/
public static int findRotationsOptimal(int[] nums) {
int left = 0, right = nums.length - 1;
int ans = 0; // Store index of minimum element
// Binary search loop
while (left <= right) {
// If current subarray is already sorted, left is minimum
if (nums[left] <= nums[right]) {
ans = left;
break; // Exit early since array is sorted
}
int mid = left + (right - left) / 2; // Prevent integer overflow
// Check if mid is the minimum element
// Minimum element is smaller than or equal to both neighbors
if (nums[mid] <= nums[right]) {
// Right half is sorted, so minimum must be in left half
ans = mid; // mid could be minimum, so store it
right = mid - 1; // Search left half (including mid)
} else {
// Left half is sorted, so minimum must be in right half
left = mid + 1; // Search right half (excluding mid)
}
}
return ans;
}
}
Search Single Element in a sorted array
You are given a sorted array where every element appears exactly twice, except for one element which appears only once.
Example
Array: [1, 1, 2, 2, 3, 4, 4] → Single Element = 3
Array: [3, 3, 7, 7, 10, 11, 11] → Single Element = 10
Array: [1] → Single Element = 1
Brute Force Approach
Traverse the array.
Compare each element with its neighbors.
If it doesn’t match either neighbor, return it.
Time Complexity: O(n)
Space Complexity: O(1)
Optimal Approach (Binary Search)
Since the array is sorted and elements appear in pairs:
Before the single element, pairs start at even indices.
After the single element, pairs start at odd indices.
Use binary search:
Check
mid.If
midis even andnums[mid] == nums[mid + 1], search right.If
midis odd andnums[mid] == nums[mid - 1], search right.Else, search left.
When loop ends,
leftwill point to the single element.
Time Complexity: O(log n)
Space Complexity: O(1)
| Method | Time Complexity | Space Complexity |
| Brute Force | O(n) | O(1) |
| Optimal | O(log n) | O(1) |
import java.util.Arrays;
/**
* Demonstrates searching the single element in a sorted array
* where every other element appears twice.
* The array is sorted and all elements appear exactly twice except for one unique element.
*/
class Main {
public static void main(String[] args) {
// Test cases with different scenarios
int[] nums1 = {1, 1, 2, 2, 3, 4, 4}; // Single element in middle
int[] nums2 = {3, 3, 7, 7, 10, 11, 11}; // Single element in middle
int[] nums3 = {1}; // Edge case: only one element
// Test case 1: Single element surrounded by pairs
System.out.println("Array: " + Arrays.toString(nums1));
System.out.println("Brute Force Single Element: " + singleElementBruteForce(nums1));
System.out.println("Optimal Single Element: " + singleElementOptimal(nums1));
// Test case 2: Another single element scenario
System.out.println("\nArray: " + Arrays.toString(nums2));
System.out.println("Brute Force Single Element: " + singleElementBruteForce(nums2));
System.out.println("Optimal Single Element: " + singleElementOptimal(nums2));
// Test case 3: Edge case with only one element
System.out.println("\nArray: " + Arrays.toString(nums3));
System.out.println("Brute Force Single Element: " + singleElementBruteForce(nums3));
System.out.println("Optimal Single Element: " + singleElementOptimal(nums3));
/* Expected Output:
Array: [1, 1, 2, 2, 3, 4, 4]
Brute Force Single Element: 3
Optimal Single Element: 3
Array: [3, 3, 7, 7, 10, 11, 11]
Brute Force Single Element: 10
Optimal Single Element: 10
Array: [1]
Brute Force Single Element: 1
Optimal Single Element: 1
*/
}
/**
* Brute Force Method: Linear search for the unique element
* Time Complexity: O(n) - scans entire array in worst case
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Check each element to see if it's different from both neighbors
*
* @param nums the sorted array with all elements appearing twice except one
* @return the single unique element
*/
public static int singleElementBruteForce(int[] nums) {
int n = nums.length;
// Edge case: array has only one element
if (n == 1) return nums[0];
// Iterate through each element
for (int i = 0; i < n; i++) {
// Check if left neighbor exists and is equal to current element
boolean leftSame = (i > 0 && nums[i] == nums[i - 1]);
// Check if right neighbor exists and is equal to current element
boolean rightSame = (i < n - 1 && nums[i] == nums[i + 1]);
// If current element is different from both neighbors, it's unique
if (!leftSame && !rightSame) {
return nums[i];
}
}
return -1; // Should not happen if input is valid
}
/**
* Optimal Method: Binary search for the unique element
* Time Complexity: O(log n) - halves search space each iteration
* Space Complexity: O(1) - uses constant extra space
*
* Key Insight: In a sorted array with pairs, before the single element,
* pairs appear at even-odd indices, and after the single element,
* pairs appear at odd-even indices.
*
* Strategy: Use binary search and check index patterns to locate the single element
*
* @param nums the sorted array with all elements appearing twice except one
* @return the single unique element
*/
public static int singleElementOptimal(int[] nums) {
int left = 0, right = nums.length - 1;
// Edge case: array has only one element
if (nums.length == 1) return nums[0];
// Binary search loop
while (left < right) {
int mid = left + (right - left) / 2;
/**
* Ensure mid is at an even index to maintain the pair pattern:
* - Before single element: pairs at (even, odd) indices
* - After single element: pairs at (odd, even) indices
* By making mid even, we can consistently compare with mid+1
*/
if (mid % 2 == 1) mid--;
/**
* Check if mid and mid+1 form a valid pair:
* - If nums[mid] == nums[mid + 1]:
* This pair is valid, so the single element must be on the RIGHT side
* Move left pointer to mid + 2 (skip the current pair)
*
* - If nums[mid] != nums[mid + 1]:
* This indicates the single element is on the LEFT side including mid
* Move right pointer to mid
*/
if (nums[mid] == nums[mid + 1]) {
left = mid + 2; // Single element is on the right
} else {
right = mid; // Single element is on the left including mid
}
}
return nums[left]; // When left == right, we found the single element
}
}
Peak element in Array
Given an array nums, find any peak element.
A peak element is one strictly greater than its neighbors.
Assume
nums[-1] = nums[n] = -∞.
Brute Force Approach
Intuition:
A peak is an element greater than both its neighbors. The simplest approach is to check every element one by one and see if it satisfies this condition.
Steps:
Loop through each element
nums[i]in the array.For each element, check:
If it is the first element: only check if
nums[i] > nums[i+1].If it is the last element: only check if
nums[i] > nums[i-1].Otherwise, check if
nums[i] > nums[i-1]andnums[i] > nums[i+1].
Return the element as soon as a peak is found.
Why it works:
Every array must have at least one peak, because:
If the array is strictly increasing, the last element is a peak.
If the array is strictly decreasing, the first element is a peak.
Otherwise, there will be a local peak somewhere in between.
Complexity:
Time Complexity: O(n), because we may have to check each element.
Space Complexity: O(1), no extra memory is needed.
Optimal Approach (Binary Search)
Intuition:
We can use binary search instead of linear scan.
Think of the array as a mountain-like slope.
If
nums[mid] < nums[mid + 1], the slope is rising → a peak must exist on the right.If
nums[mid] > nums[mid + 1], the slope is falling → a peak must exist on the left (including mid).
This works because a peak exists wherever the slope changes from rising to falling.
Steps:
Initialize
left = 0andright = n - 1.While
left < right:Find
mid = left + (right - left)/2.Compare
nums[mid]withnums[mid + 1].If
nums[mid] < nums[mid + 1], setleft = mid + 1.Else, set
right = mid.
When
left == right, returnnums[left]. This is a peak.
Why it works:
Binary search reduces the search space in half every step.
At least one peak always exists in any array.
By moving toward the higher neighbor, we ensure we eventually land on a peak.
Complexity:
Time Complexity: O(log n), because we halve the search space at each step.
Space Complexity: O(1), no extra memory is used.
Example Walkthrough (Optimal)
Array: [1, 3, 20, 4, 1, 0]
left = 0, right = 5→mid = 2→nums[2] = 20, nums[3] = 420 > 4→ move left →right = mid = 2
left = 0, right = 2→mid = 1→nums[1] = 3, nums[2] = 203 < 20→ move right →left = mid + 1 = 2
left == right == 2→ peak =20
Notice how we never check every element but still find a peak.
| Approach | Time Complexity | Space Complexity | Key Idea |
| Brute Force | O(n) | O(1) | Check each element and compare neighbors |
| Optimal (Binary Search) | O(log n) | O(1) | Use slope property; move toward higher neighbor until peak |
import java.util.Arrays;
class Main {
public static void main(String[] args) {
// Test cases with different peak scenarios
int[] nums1 = {1, 2, 3, 1}; // Peak at index 2 (value 3)
int[] nums2 = {1, 2, 1, 3, 5, 6, 4}; // Multiple peaks (2 and 6)
int[] nums3 = {1}; // Edge case: single element
// Test case 1: Simple mountain peak
System.out.println("Array: " + Arrays.toString(nums1));
System.out.println("Brute Force Peak: " + peakBruteForce(nums1));
System.out.println("Optimal Peak: " + peakOptimal(nums1));
// Test case 2: Array with multiple peaks (may return first found)
System.out.println("\nArray: " + Arrays.toString(nums2));
System.out.println("Brute Force Peak: " + peakBruteForce(nums2));
System.out.println("Optimal Peak: " + peakOptimal(nums2));
// Test case 3: Single element array
System.out.println("\nArray: " + Arrays.toString(nums3));
System.out.println("Brute Force Peak: " + peakBruteForce(nums3));
System.out.println("Optimal Peak: " + peakOptimal(nums3));
/* Expected Output:
Array: [1, 2, 3, 1]
Brute Force Peak: 3
Optimal Peak: 3
Array: [1, 2, 1, 3, 5, 6, 4]
Brute Force Peak: 2
Optimal Peak: 6
Array: [1]
Brute Force Peak: 1
Optimal Peak: 1
*/
}
/**
* Brute Force Method: Linear search for peak element
* Time Complexity: O(n) - scans entire array in worst case
* Space Complexity: O(1) - uses constant extra space
*
* A peak element is defined as an element that is greater than its neighbors.
* For array boundaries, only one neighbor needs to be considered.
*
* @param nums the input array
* @return the value of a peak element (returns first peak found)
*/
public static int peakBruteForce(int[] nums) {
int n = nums.length;
// Check each element to see if it's a peak
for (int i = 0; i < n; i++) {
// Check left neighbor: if at start, automatically OK
boolean leftOk = (i == 0 || nums[i] > nums[i - 1]);
// Check right neighbor: if at end, automatically OK
boolean rightOk = (i == n - 1 || nums[i] > nums[i + 1]);
// If both conditions are satisfied, we found a peak
if (leftOk && rightOk) return nums[i];
}
return -1; // Should not happen if array has at least one peak
}
/**
* Optimal Method: Binary search for peak element
* Time Complexity: O(log n) - halves search space each iteration
* Space Complexity: O(1) - uses constant extra space
*
* Key Insight: In any array, there's always at least one peak element.
* We can use binary search by comparing mid with its right neighbor:
* - If nums[mid] < nums[mid + 1]: ascending slope, peak must be on right
* - If nums[mid] > nums[mid + 1]: descending slope, peak must be on left (including mid)
*
* This approach finds a peak, but not necessarily the highest or first peak.
*
* @param nums the input array
* @return the value of a peak element
*/
public static int peakOptimal(int[] nums) {
int left = 0, right = nums.length - 1;
// Binary search loop (note: left < right, not <=)
while (left < right) {
int mid = left + (right - left) / 2; // Prevents integer overflow
/**
* Compare mid element with its right neighbor:
*
* Case 1: nums[mid] < nums[mid + 1]
* - We're on an ascending slope
* - The peak must be to the RIGHT of mid (could be mid+1 or beyond)
* - Move left pointer to mid + 1
*
* Case 2: nums[mid] >= nums[mid + 1]
* - We're on a descending slope or plateau
* - The peak could be mid itself or to the LEFT of mid
* - Move right pointer to mid (include mid in search space)
*/
if (nums[mid] < nums[mid + 1]) {
left = mid + 1; // Peak is on the right
} else {
right = mid; // Peak is on the left including mid
}
}
// When left == right, we've found a peak element
return nums[left];
}
}
Finding Sqrt of a number using Binary Search
Given a non-negative integer x, return the floor value of its square root (i.e., the greatest integer r such that r * r <= x).
Example
Input: x = 16 → Output: 4
Input: x = 8 → Output: 2 (since sqrt(8) ≈ 2.82 and floor is 2)
Input: x = 1 → Output: 1
Input: x = 0 → Output: 0
Brute Force Approach
Intuition:
We can try all numbers from 1 up to x, and find the largest number i such that i * i <= x.
Steps:
Start with
i = 1.Increment
iwhilei * i <= x.Once it exceeds, return
i - 1.
Why it works:
The square root must lie between 0 and x. A linear check ensures we eventually find the floor value.
Complexity:
Time Complexity: O(√x) (we only need to go up to
√x)Space Complexity: O(1)
Optimal Approach (Binary Search)
Intuition:
Instead of checking one by one, we can apply binary search between 0 and x.
If
mid * mid == x, returnmid.If
mid * mid < x, storemidas a possible answer and search right.If
mid * mid > x, search left.
Steps:
Set
left = 0,right = x,ans = -1.While
left <= right:Compute
mid = (left + right) / 2.If
mid * mid == x, returnmid.If
mid * mid < x, updateans = midand search right (left = mid + 1).Else, search left (
right = mid - 1).
Return
ans.
Why it works:
Binary search eliminates half of the search space at every step, quickly converging to the square root.
Complexity:
Time Complexity: O(log x)
Space Complexity: O(1)
Summary Table
| Approach | Time Complexity | Space Complexity | Key Idea |
| Brute Force | O(√x) | O(1) | Linearly check each number up to sqrt(x) |
| Optimal (Binary Search) | O(log x) | O(1) | Use binary search to narrow down the answer |
class Main {
public static void main(String[] args) {
// Test cases with different input values
int x1 = 16; // Perfect square
int x2 = 8; // Non-perfect square
int x3 = 1; // Edge case: smallest perfect square
int x4 = 0; // Edge case: zero
// Test case 1: Perfect square
System.out.println("Brute Force sqrt(" + x1 + "): " + sqrtBruteForce(x1));
System.out.println("Optimal sqrt(" + x1 + "): " + sqrtOptimal(x1));
// Test case 2: Non-perfect square (floor value)
System.out.println("\nBrute Force sqrt(" + x2 + "): " + sqrtBruteForce(x2));
System.out.println("Optimal sqrt(" + x2 + "): " + sqrtOptimal(x2));
// Test case 3: Smallest non-zero perfect square
System.out.println("\nBrute Force sqrt(" + x3 + "): " + sqrtBruteForce(x3));
System.out.println("Optimal sqrt(" + x3 + "): " + sqrtOptimal(x3));
// Test case 4: Zero input
System.out.println("\nBrute Force sqrt(" + x4 + "): " + sqrtBruteForce(x4));
System.out.println("Optimal sqrt(" + x4 + "): " + sqrtOptimal(x4));
/* Expected Output:
Brute Force sqrt(16): 4
Optimal sqrt(16): 4
Brute Force sqrt(8): 2
Optimal sqrt(8): 2
Brute Force sqrt(1): 1
Optimal sqrt(1): 1
Brute Force sqrt(0): 0
Optimal sqrt(0): 0
*/
}
/**
* Brute Force Method: Linear search for integer square root
* Time Complexity: O(√n) - iterates up to the square root of x
* Space Complexity: O(1) - uses constant extra space
*
* Finds the largest integer i such that i² ≤ x (floor of square root)
*
* @param x the number to find square root of (non-negative)
* @return the integer square root (floor value for non-perfect squares)
*/
public static int sqrtBruteForce(int x) {
// Handle edge cases: 0 and 1 are their own square roots
if (x == 0 || x == 1) return x;
int i = 1;
// Iterate until i² exceeds x
while (i * i <= x) {
i++;
}
// Return i-1 because the loop exits when i² > x
// So (i-1)² ≤ x < i², making i-1 the floor square root
return i - 1;
}
/**
* Optimal Method: Binary search for integer square root
* Time Complexity: O(log n) - halves search space each iteration
* Space Complexity: O(1) - uses constant extra space
*
* Uses binary search to find the largest integer mid such that mid² ≤ x
*
* @param x the number to find square root of (non-negative)
* @return the integer square root (floor value for non-perfect squares)
*/
public static int sqrtOptimal(int x) {
// Handle edge cases: 0 and 1 are their own square roots
if (x == 0 || x == 1) return x;
int left = 1, right = x, ans = -1;
// Binary search loop
while (left <= right) {
int mid = left + (right - left) / 2; // Prevents integer overflow
// Use long to prevent integer overflow for large values
long square = (long) mid * mid;
if (square == x) {
// Found perfect square root
return mid;
} else if (square < x) {
// mid² < x, so mid is a potential answer
// Store it and search right half for potentially larger answer
ans = mid;
left = mid + 1;
} else {
// mid² > x, so mid is too large
// Search left half for smaller values
right = mid - 1;
}
}
// Return the largest integer found where i² ≤ x
return ans;
}
}
Nth Root of a Number using Binary Search
Problem Statement:
Given two integers x (the number) and n (the root), find the integer part of the nth root of x.
That is, find the greatest integer r such that r^n <= x.
Example
Input: x = 27, n = 3 → Output: 3 (since 3^3 = 27)
Input: x = 64, n = 3 → Output: 4 (since 4^3 = 64)
Input: x = 16, n = 4 → Output: 2 (since 2^4 = 16)
Input: x = 15, n = 2 → Output: 3 (since sqrt(15) ≈ 3.87, floor = 3)
Brute Force Approach
Intuition:
Try all numbers i starting from 1 until i^n > x. The last valid i is the answer.
Steps:
Loop
i = 1tox.Compute
i^n.If
i^n > x, stop and returni-1.
Why it works:
The nth root of x must lie between 1 and x. Checking sequentially guarantees correctness.
Complexity:
Time Complexity: O(x^(1/n)) → worst-case when n = 2 (O(√x)).
Space Complexity: O(1).
Optimal Approach (Binary Search)
Intuition:
Instead of checking every number, use binary search between 1 and x:
If
mid^n == x, returnmid.If
mid^n < x, storemidas possible answer and search right.If
mid^n > x, search left.
Steps:
Set
low = 1,high = x,ans = -1.While
low <= high:Compute
mid = (low + high)/2.Compare
mid^nwithx.If equal, return
mid.If less, update
ans = midand search right.If greater, search left.
Return
ans.
Why it works:
Binary search halves the search range each time. Since nth root is monotonic, we quickly converge to the integer root.
Complexity:
Time Complexity: O(log x)
Space Complexity: O(1)
Summary Table
| Approach | Time Complexity | Space Complexity | Key Idea |
| Brute Force | O(x^(1/n)) | O(1) | Try all numbers sequentially |
| Optimal (Binary Search) | O(log x) | O(1) | Use binary search on range [1, x] |
class Main {
public static void main(String[] args) {
// Test cases with different roots and values
System.out.println("Brute Force 3rd root of 27: " + nthRootBruteForce(27, 3));
System.out.println("Optimal 3rd root of 27: " + nthRootOptimal(27, 3));
System.out.println("\nBrute Force 3rd root of 64: " + nthRootBruteForce(64, 3));
System.out.println("Optimal 3rd root of 64: " + nthRootOptimal(64, 3));
System.out.println("\nBrute Force 4th root of 16: " + nthRootBruteForce(16, 4));
System.out.println("Optimal 4th root of 16: " + nthRootOptimal(16, 4));
System.out.println("\nBrute Force 2nd root of 15: " + nthRootBruteForce(15, 2));
System.out.println("Optimal 2nd root of 15: " + nthRootOptimal(15, 2));
/* Expected Output:
Brute Force 3rd root of 27: 3
Optimal 3rd root of 27: 3
Brute Force 3rd root of 64: 4
Optimal 3rd root of 64: 4
Brute Force 4th root of 16: 2
Optimal 4th root of 16: 2
Brute Force 2nd root of 15: 3
Optimal 2nd root of 15: 3
*/
}
/**
* Brute Force Method: Linear search for integer nth root
* Time Complexity: O(x^(1/n)) - iterates up to the nth root of x
* Space Complexity: O(1) - uses constant extra space
*
* Finds the largest integer i such that iⁿ ≤ x (floor of nth root)
*
* @param x the number to find nth root of (non-negative)
* @param n the degree of the root (positive integer)
* @return the integer nth root (floor value for non-perfect nth powers)
*/
public static int nthRootBruteForce(int x, int n) {
// Handle edge cases: 0 and 1 are their own nth roots for any n
if (x == 0 || x == 1) return x;
int i = 1;
// Iterate until iⁿ exceeds x
while (power(i, n) <= x) {
i++;
}
// Return i-1 because the loop exits when iⁿ > x
// So (i-1)ⁿ ≤ x < iⁿ, making i-1 the floor nth root
return i - 1;
}
/**
* Optimal Method: Binary search for integer nth root
* Time Complexity: O(log x) - halves search space each iteration
* Space Complexity: O(1) - uses constant extra space
*
* Uses binary search to find the largest integer mid such that midⁿ ≤ x
*
* @param x the number to find nth root of (non-negative)
* @param n the degree of the root (positive integer)
* @return the integer nth root (floor value for non-perfect nth powers)
*/
public static int nthRootOptimal(int x, int n) {
// Handle edge cases: 0 and 1 are their own nth roots for any n
if (x == 0 || x == 1) return x;
int low = 1, high = x, ans = -1;
// Binary search loop
while (low <= high) {
int mid = low + (high - low) / 2; // Prevents integer overflow
// Calculate midⁿ safely using long to prevent overflow
long midPower = power(mid, n);
if (midPower == x) {
// Found exact nth root
return mid;
} else if (midPower < x) {
// midⁿ < x, so mid is a potential answer
// Store it and search right half for potentially larger answer
ans = mid;
low = mid + 1;
} else {
// midⁿ > x, so mid is too large
// Search left half for smaller values
high = mid - 1;
}
}
// Return the largest integer found where iⁿ ≤ x
return ans;
}
/**
* Helper function to calculate a^b (a raised to power b) safely
* Uses long to prevent integer overflow for large values
* Time Complexity: O(b) - linear in the exponent
* Space Complexity: O(1) - constant space
*
* @param a the base (positive integer)
* @param b the exponent (positive integer)
* @return a^b as a long to prevent overflow
*/
private static long power(int a, int b) {
long result = 1;
// Multiply a by itself b times
for (int i = 0; i < b; i++) {
result *= a;
// Early termination if result becomes too large (though we handle this in caller)
}
return result;
}
}
Koko Eating Bananas
Problem Statement:
Koko loves to eat bananas. There are piles[] of bananas where piles[i] represents bananas in the i-th pile. Koko eats at a constant speed k bananas per hour.
Each hour she chooses a pile and eats up to k bananas from it (if pile has less than k, she eats the whole pile).
Given an integer h (the number of hours available), find the minimum integer eating speed k such that Koko can eat all the bananas in h hours.
Example
Input: piles = [3, 6, 7, 11], h = 8
Output: 4
Explanation:
- At speed k=4 → Hours taken = 2 (pile 3,6) + 2 (pile 7,11) = 8
- Any slower speed would exceed 8 hours.
Input: piles = [30, 11, 23, 4, 20], h = 5
Output: 30
Brute Force Approach
Intuition:
Try all possible speeds k from 1 to max(piles).
For each k, calculate the total hours required:
hours = Σ ceil(pile/k)for each pile.
Pick the minimumksuch thathours <= h.
Steps:
Find
maxPile = max(piles).For
k = 1tomaxPile:Compute hours required.
If
hours <= h, returnk.
Why it works:
The minimum valid k must lie between 1 and max(piles).
Complexity:
Time Complexity: O(maxPile × n) (very slow for large inputs).
Space Complexity: O(1).
Optimal Approach (Binary Search)
Intuition:
The "is possible with speed k?" function is monotonic:
If she can finish with speed
k, then she can also finish with any speed> k.If she cannot finish with speed
k, then she cannot finish with any speed< k.
This monotonic property makes it perfect for binary search.
Steps:
Set
low = 1,high = max(piles),ans = max(piles).While
low <= high:mid = (low + high)/2.Calculate hours needed at speed
mid.If hours <= h → possible answer, move left (high = mid-1).
Else move right (low = mid+1).
Return
ans.
Complexity:
Time Complexity: O(n × log(maxPile))
Space Complexity: O(1)
Summary Table
| Approach | Time Complexity | Space Complexity | Key Idea |
| Brute Force | O(n × maxPile) | O(1) | Try all speeds sequentially |
| Optimal (Binary Search) | O(n × log(maxPile)) | O(1) | Use binary search on speed |
class Main {
public static void main(String[] args) {
// Test case 1: Multiple piles with limited time
int[] piles1 = {3, 6, 7, 11};
int h1 = 8;
System.out.println("Brute Force Answer: " + minEatingSpeedBruteForce(piles1, h1));
System.out.println("Optimal Answer: " + minEatingSpeedOptimal(piles1, h1));
// Test case 2: Larger piles with exact time constraint
int[] piles2 = {30, 11, 23, 4, 20};
int h2 = 5;
System.out.println("\nBrute Force Answer: " + minEatingSpeedBruteForce(piles2, h2));
System.out.println("Optimal Answer: " + minEatingSpeedOptimal(piles2, h2));
/*
Expected Output:
Brute Force Answer: 4
Optimal Answer: 4
Brute Force Answer: 30
Optimal Answer: 30
*/
}
/**
* Brute Force Method: Linear search for minimum eating speed
* Time Complexity: O(n * m) where n = piles.length, m = max pile size
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Try every possible eating speed from 1 to max pile size
* and return the first speed that allows Koko to eat all bananas in time
*
* @param piles array of banana pile sizes
* @param h hours available to eat all bananas
* @return minimum eating speed k that allows completion within h hours
*/
public static int minEatingSpeedBruteForce(int[] piles, int h) {
// Find the maximum pile size (upper bound for eating speed)
int maxPile = 0;
for (int pile : piles) maxPile = Math.max(maxPile, pile);
// Try every possible eating speed from 1 to maxPile
for (int k = 1; k <= maxPile; k++) {
if (canEatAll(piles, k, h)) return k;
}
// If no smaller speed works, return maxPile (guaranteed to work)
return maxPile;
}
/**
* Optimal Method: Binary search for minimum eating speed
* Time Complexity: O(n * log m) where n = piles.length, m = max pile size
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Use binary search to find the minimum eating speed that
* satisfies the time constraint. The search space is [1, maxPile].
*
* @param piles array of banana pile sizes
* @param h hours available to eat all bananas
* @return minimum eating speed k that allows completion within h hours
*/
public static int minEatingSpeedOptimal(int[] piles, int h) {
// Find the maximum pile size (upper bound for eating speed)
int maxPile = 0;
for (int pile : piles) maxPile = Math.max(maxPile, pile);
int low = 1, high = maxPile, ans = maxPile;
// Binary search over possible eating speeds
while (low <= high) {
int mid = low + (high - low) / 2; // Prevent integer overflow
if (canEatAll(piles, mid, h)) {
// mid speed works, try to find smaller speed
ans = mid;
high = mid - 1; // search left half for smaller valid speed
} else {
// mid speed is too slow, need faster speed
low = mid + 1; // search right half for larger speed
}
}
return ans;
}
/**
* Helper function to check if Koko can eat all bananas at a given speed
* Time Complexity: O(n) where n = piles.length
* Space Complexity: O(1) - uses constant extra space
*
* Calculates total hours needed to eat all piles at speed k:
* For each pile: hours += ceil(pile / k)
*
* @param piles array of banana pile sizes
* @param k eating speed (bananas per hour)
* @param h hours available
* @return true if total hours ≤ h, false otherwise
*/
private static boolean canEatAll(int[] piles, int k, int h) {
int hours = 0;
for (int pile : piles) {
// Calculate hours needed for this pile: ceil(pile / k)
// Using (pile + k - 1) / k avoids floating point and provides integer ceiling
hours += (pile + k - 1) / k;
// Alternative using Math.ceil:
// hours += Math.ceil((double) pile / k);
}
return hours <= h;
}
}
Minimum days to make M bouquets
Problem Statement:
You are given an array bloomDay[] where bloomDay[i] is the day the i-th flower blooms.
You need to make m bouquets, each consisting of k consecutive flowers.
Return the minimum number of days needed to make m bouquets.
If it is not possible, return -1.
Example
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: By day 3 → Flowers {1,3,2} are bloomed, enough for 3 bouquets.
Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: Need 6 flowers, but only 5 exist → impossible.
Brute Force Approach
Intuition:
We want the earliest day d such that we can make m bouquets of k consecutive flowers.
Try every possible day
dfrommin(bloomDay)tomax(bloomDay).For each day, check if at least
mbouquets can be made.
Steps:
If
m * k > n(more flowers needed than available), return-1.For
din rangemin(bloomDay)→max(bloomDay):Traverse
bloomDay[], count how many consecutive flowers are bloomed (bloomDay[i] <= d).Every time we get
kconsecutive bloomed flowers, form a bouquet.If bouquets ≥ m, return
d.
If no day works, return
-1.
Complexity:
Time Complexity: O(n × (maxDay - minDay)) → Too slow for large inputs.
Space Complexity: O(1).
Optimal Approach (Binary Search)
Intuition:
The condition “Can we make m bouquets on day d?” is monotonic:
If it is possible on day
d, then it is also possible on any later day> d.If it is not possible on day
d, it is also not possible on any earlier day< d.
This allows us to use binary search on days.
Steps:
If
m * k > n, return-1.Set search range:
low = min(bloomDay),high = max(bloomDay).
While
low <= high:mid = (low + high) / 2.Check if we can make at least
mbouquets on daymid.Traverse
bloomDay.Count consecutive bloomed flowers.
Every time count reaches
k, form a bouquet and reset count.
If possible, store
midand move left (high = mid - 1).Else, move right (
low = mid + 1).
Return the stored answer.
Complexity:
Time Complexity: O(n × log(maxDay - minDay))
Space Complexity: O(1).
class Main {
public static void main(String[] args) {
// Test case 1: Make 3 bouquets with 1 flower each
int[] bloomDay1 = {1, 10, 3, 10, 2};
System.out.println("Brute Force Answer: " + minDaysBruteForce(bloomDay1, 3, 1));
System.out.println("Optimal Answer: " + minDaysOptimal(bloomDay1, 3, 1));
// Test case 2: Make 3 bouquets with 2 flowers each
int[] bloomDay2 = {1, 10, 3, 10, 2};
System.out.println("\nBrute Force Answer: " + minDaysBruteForce(bloomDay2, 3, 2));
System.out.println("Optimal Answer: " + minDaysOptimal(bloomDay2, 3, 2));
}
/**
* Brute Force Method: Linear search for minimum days
* Time Complexity: O(n * d) where n = bloomDay.length, d = range of bloom days
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Try every possible day from min bloom day to max bloom day
* and return the first day that allows making m bouquets of k adjacent flowers
*
* @param bloomDay array of days when each flower blooms
* @param m number of bouquets required
* @param k number of adjacent flowers needed per bouquet
* @return minimum day to make m bouquets, or -1 if impossible
*/
public static int minDaysBruteForce(int[] bloomDay, int m, int k) {
// Check if it's possible: need at least m * k flowers
if ((long)m * k > bloomDay.length) return -1;
// Find the range of possible days to search
int minDay = Integer.MAX_VALUE, maxDay = Integer.MIN_VALUE;
for (int day : bloomDay) {
minDay = Math.min(minDay, day);
maxDay = Math.max(maxDay, day);
}
// Try each day in the range
for (int d = minDay; d <= maxDay; d++) {
if (canMake(bloomDay, d, m, k)) return d;
}
return -1;
}
/**
* Optimal Method: Binary search for minimum days
* Time Complexity: O(n * log d) where n = bloomDay.length, d = range of bloom days
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Use binary search to find the minimum day that allows
* making m bouquets. The search space is [minDay, maxDay].
*
* @param bloomDay array of days when each flower blooms
* @param m number of bouquets required
* @param k number of adjacent flowers needed per bouquet
* @return minimum day to make m bouquets, or -1 if impossible
*/
public static int minDaysOptimal(int[] bloomDay, int m, int k) {
// Check if it's possible: need at least m * k flowers
if ((long)m * k > bloomDay.length) return -1;
// Find the range of possible days to search
int minDay = Integer.MAX_VALUE, maxDay = Integer.MIN_VALUE;
for (int day : bloomDay) {
minDay = Math.min(minDay, day);
maxDay = Math.max(maxDay, day);
}
int low = minDay, high = maxDay, ans = -1;
// Binary search over possible days
while (low <= high) {
int mid = low + (high - low) / 2; // Prevent integer overflow
if (canMake(bloomDay, mid, m, k)) {
// mid day works, try to find smaller day
ans = mid;
high = mid - 1; // search left half for smaller valid day
} else {
// mid day is too early, need later day
low = mid + 1; // search right half for larger day
}
}
return ans;
}
/**
* Helper function to check if we can make m bouquets by a given day
* Time Complexity: O(n) where n = bloomDay.length
* Space Complexity: O(1) - uses constant extra space
*
* Counts adjacent flowers that have bloomed by the given day and
* forms bouquets whenever k adjacent flowers are found
*
* @param bloomDay array of days when each flower blooms
* @param day the day to check
* @param m number of bouquets required
* @param k number of adjacent flowers needed per bouquet
* @return true if m bouquets can be made by the given day
*/
private static boolean canMake(int[] bloomDay, int day, int m, int k) {
int count = 0; // Count of consecutive bloomed flowers
int bouquets = 0; // Number of bouquets made so far
for (int d : bloomDay) {
if (d <= day) {
// Flower has bloomed by this day
count++;
if (count == k) {
// Found k adjacent flowers, make a bouquet
bouquets++;
count = 0; // Reset counter for next bouquet
// Early termination: if we've made enough bouquets
if (bouquets >= m) return true;
}
} else {
// Flower hasn't bloomed yet, break the sequence
count = 0;
}
}
return bouquets >= m;
}
}
Dry Run Example
Input: bloomDay = [1,10,3,10,2], m=3, k=1
Search space = [1, 10]
mid = 5 → Can we make 3 bouquets by day 5?
- Bloomed by day 5 → {1,3,2} → Yes → ans=5 → search left.
mid = 3 → Can we make 3 bouquets by day 3?
- Bloomed by day 3 → {1,3,2} → Yes → ans=3 → search left.
mid = 2 → Only {1,2} → 2 bouquets → Not enough → move right.
Final Answer = 3.
Summary
| Approach | Time Complexity | Space Complexity | Key Idea |
| Brute Force | O(n × (maxDay-minDay)) | O(1) | Try each day sequentially |
| Optimal (Binary Search) | O(n × log(maxDay-minDay)) | O(1) | Monotonic property of feasibility → binary search |
- Find the Smallest Divisor Given a Threshold
Problem Statement:
You are given an integer array nums and an integer threshold.
Example
Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation:
divisor = 5 → [ceil(1/5), ceil(2/5), ceil(5/5), ceil(9/5)] = [1,1,1,2] = 5 ≤ 6 ✅
divisor = 4 → [1,1,2,3] = 7 > 6 ❌
So smallest valid divisor = 5
Input: nums = [44,22,33,11,1], threshold = 5
Output: 44
Brute Force Approach
Intuition:
The divisor must be in the range [1, max(nums)].
Try every divisor from 1 → max(nums).
For each divisor, compute the sum of
ceil(nums[i] / divisor).Return the first divisor where sum ≤ threshold.
Steps:
Initialize
maxNum = max(nums).Loop
d = 1 → maxNum.Compute
sum = Σ ceil(nums[i] / d).If
sum ≤ threshold, returnd.
Complexity:
Time Complexity: O(n × max(nums)) → Too slow for large inputs.
Space Complexity: O(1).
Optimal Approach (Binary Search)
Intuition:
The function
f(divisor) = Σ ceil(nums[i]/divisor)is monotonic:If divisor increases → sum decreases.
If divisor decreases → sum increases.
This allows us to apply binary search on divisor values.
Steps:
Search space for divisor = [1, max(nums)].
While
low <= high:mid = (low + high)/2.Compute sum with divisor = mid.
If
sum ≤ threshold, store mid as answer and move left (try smaller divisor).Else, move right (need bigger divisor).
Return smallest valid divisor.
Complexity:
Time Complexity: O(n × log(max(nums))).
Space Complexity: O(1).
class Main {
public static void main(String[] args) {
// Test case 1: Normal case with threshold
int[] nums1 = {1, 2, 5, 9};
int threshold1 = 6;
System.out.println("Brute Force Answer: " + smallestDivisorBruteForce(nums1, threshold1));
System.out.println("Optimal Answer: " + smallestDivisorOptimal(nums1, threshold1));
// Test case 2: More challenging case with smaller threshold
int[] nums2 = {44, 22, 33, 11, 1};
int threshold2 = 5;
System.out.println("\nBrute Force Answer: " + smallestDivisorBruteForce(nums2, threshold2));
System.out.println("Optimal Answer: " + smallestDivisorOptimal(nums2, threshold2));
}
/**
* Brute Force Method: Linear search for smallest divisor
* Time Complexity: O(n * m) where n = nums.length, m = max number in nums
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Try every possible divisor from 1 to max number
* and return the first divisor that gives sum ≤ threshold
*
* @param nums array of numbers to divide
* @param threshold maximum allowed sum of ceilings
* @return smallest divisor that makes sum of ceilings ≤ threshold
*/
public static int smallestDivisorBruteForce(int[] nums, int threshold) {
// Find the maximum number (upper bound for divisor search)
int maxNum = 0;
for (int num : nums) maxNum = Math.max(maxNum, num);
// Try every divisor from 1 to maxNum
for (int d = 1; d <= maxNum; d++) {
if (computeSum(nums, d) <= threshold) {
return d;
}
}
return -1; // Should never reach here if threshold >= nums.length
}
/**
* Optimal Method: Binary search for smallest divisor
* Time Complexity: O(n * log m) where n = nums.length, m = max number in nums
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Use binary search to find the smallest divisor that
* satisfies the threshold constraint. The search space is [1, maxNum].
*
* Key Insight: The sum of ceilings is a monotonic function:
* - As divisor increases, the sum of ceilings decreases
* - If divisor d works, any divisor > d also works
* - If divisor d doesn't work, any divisor < d also won't work
*
* @param nums array of numbers to divide
* @param threshold maximum allowed sum of ceilings
* @return smallest divisor that makes sum of ceilings ≤ threshold
*/
public static int smallestDivisorOptimal(int[] nums, int threshold) {
// Find the maximum number (upper bound for divisor search)
int maxNum = 0;
for (int num : nums) maxNum = Math.max(maxNum, num);
int low = 1, high = maxNum, ans = -1;
// Binary search over possible divisors
while (low <= high) {
int mid = low + (high - low) / 2; // Prevent integer overflow
int currentSum = computeSum(nums, mid);
if (currentSum <= threshold) {
// mid divisor works, try to find smaller divisor
ans = mid;
high = mid - 1; // search left half for smaller valid divisor
} else {
// mid divisor is too small, sum is too large
low = mid + 1; // search right half for larger divisor
}
}
return ans;
}
/**
* Helper function: Compute sum of ceilings after division
* Time Complexity: O(n) where n = nums.length
* Space Complexity: O(1) - uses constant extra space
*
* Calculates: sum(ceil(num / divisor)) for all numbers
* Uses integer arithmetic: ceil(a/b) = (a + b - 1) / b
*
* @param nums array of numbers to divide
* @param divisor the divisor to use
* @return sum of ceilings after dividing each number by divisor
*/
private static int computeSum(int[] nums, int divisor) {
int sum = 0;
for (int num : nums) {
// Calculate ceil(num / divisor) using integer arithmetic
// Equivalent to: (int) Math.ceil((double) num / divisor)
sum += (num + divisor - 1) / divisor;
}
return sum;
}
}
Dry Run Example
Input: nums = [1,2,5,9], threshold=6
Search Space = [1, 9]
mid = 5 → sum = 5 ≤ 6 → ans=5, search left
mid = 3 → sum = 1+1+2+3=7 > 6 → move right
mid = 4 → sum = 7 > 6 → move right
Final Answer = 5
Summary
| Approach | Time Complexity | Space Complexity | Key Idea |
| Brute Force | O(n × max(nums)) | O(1) | Try all divisors |
| Optimal (Binary Search) | O(n × log(max(nums))) | O(1) | Monotonic divisor → binary search |
Capacity to Ship Packages within D Days
Problem Statement:
You are given an array weights[], where weights[i] is the weight of the i-th package, and an integer days.
You need to ship all the packages within D days using a ship with a given capacity.
Find the minimum ship capacity that can achieve this.
Example
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation:
- Day 1: [1,2,3,4,5] = 15
- Day 2: [6,7] = 13
- Day 3: [8] = 8
- Day 4: [9] = 9
- Day 5: [10] = 10
So capacity = 15 works, but anything < 15 fails.
Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Brute Force Approach
Intuition:
The minimum possible capacity must be at least
max(weights)(since the largest package must fit).The maximum possible capacity is
sum(weights)(if we take all in one day).Try each capacity from
max(weights)→sum(weights)and check if it is possible.
Steps:
Compute
maxWeight = max(weights)andsumWeight = sum(weights).For
capacity = maxWeight → sumWeight:Simulate shipping:
- Accumulate package weights until exceeding capacity → count as a new day.
If days ≤ D → return capacity.
Complexity:
Time Complexity: O(n × (sum - max)) → Too slow for large inputs.
Space Complexity: O(1).
Optimal Approach (Binary Search on Answer)
Intuition:
The problem is monotonic:
If a capacity works for D days, any larger capacity also works.
If a capacity does not work, any smaller capacity won’t work.
Hence, we can apply binary search between [max(weights), sum(weights)].
Steps:
Set search range:
low = max(weights)high = sum(weights)
While
low <= high:mid = (low + high) / 2(candidate capacity).Simulate shipping with this capacity.
If days needed ≤ D → store mid, move left (
high = mid - 1).Else → move right (
low = mid + 1).
Return smallest valid capacity.
Complexity:
Time Complexity: O(n × log(sum - max))
Space Complexity: O(1).
class Main {
public static void main(String[] args) {
// Test case 1: Standard case with 10 packages and 5 days
int[] weights1 = {1,2,3,4,5,6,7,8,9,10};
int days1 = 5;
System.out.println("Brute Force Answer: " + shipWithinDaysBruteForce(weights1, days1));
System.out.println("Optimal Answer: " + shipWithinDaysOptimal(weights1, days1));
// Test case 2: Another case with different weights and 3 days
int[] weights2 = {3,2,2,4,1,4};
int days2 = 3;
System.out.println("\nBrute Force Answer: " + shipWithinDaysBruteForce(weights2, days2));
System.out.println("Optimal Answer: " + shipWithinDaysOptimal(weights2, days2));
}
/**
* Brute Force Method: Linear search for minimum ship capacity
* Time Complexity: O(n * (sum - max)) where n = weights.length
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Try every possible capacity from max weight to total weight
* and return the first capacity that allows shipping within given days
*
* @param weights array of package weights
* @param days maximum allowed shipping days
* @return minimum ship capacity that allows shipping within given days
*/
public static int shipWithinDaysBruteForce(int[] weights, int days) {
// Calculate bounds: capacity must be at least max weight (can't split packages)
// and at most total weight (ship everything in one day)
int maxWeight = 0, sumWeight = 0;
for (int w : weights) {
maxWeight = Math.max(maxWeight, w);
sumWeight += w;
}
// Try every capacity from maxWeight to sumWeight
for (int cap = maxWeight; cap <= sumWeight; cap++) {
if (canShip(weights, days, cap)) return cap;
}
return -1; // Should never reach here if days >= 1
}
/**
* Optimal Method: Binary search for minimum ship capacity
* Time Complexity: O(n * log(sum - max)) where n = weights.length
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Use binary search to find the minimum capacity that
* satisfies the days constraint. The search space is [maxWeight, sumWeight].
*
* Key Insight: The number of days needed is a monotonic function:
* - As capacity increases, the number of days needed decreases
* - If capacity c works, any capacity > c also works
* - If capacity c doesn't work, any capacity < c also won't work
*
* @param weights array of package weights
* @param days maximum allowed shipping days
* @return minimum ship capacity that allows shipping within given days
*/
public static int shipWithinDaysOptimal(int[] weights, int days) {
// Calculate bounds for binary search
int maxWeight = 0, sumWeight = 0;
for (int w : weights) {
maxWeight = Math.max(maxWeight, w);
sumWeight += w;
}
int low = maxWeight, high = sumWeight, ans = sumWeight;
// Binary search over possible capacities
while (low <= high) {
int mid = low + (high - low) / 2; // Prevent integer overflow
if (canShip(weights, days, mid)) {
// mid capacity works, try to find smaller capacity
ans = mid;
high = mid - 1; // search left half for smaller valid capacity
} else {
// mid capacity is too small, need larger capacity
low = mid + 1; // search right half for larger capacity
}
}
return ans;
}
/**
* Helper function: Simulate shipping with given capacity
* Time Complexity: O(n) where n = weights.length
* Space Complexity: O(1) - uses constant extra space
*
* Simulates the shipping process:
* - Load packages one by one
* - When adding a package would exceed capacity, start new day
* - Count total days needed
*
* @param weights array of package weights
* @param days maximum allowed shipping days
* @param capacity ship capacity to test
* @return true if packages can be shipped within given days with this capacity
*/
private static boolean canShip(int[] weights, int days, int capacity) {
int dayCount = 1; // Start with day 1
int currentLoad = 0; // Current load for the day
for (int w : weights) {
// Check if adding this package would exceed capacity
if (currentLoad + w > capacity) {
// Start new day
dayCount++;
currentLoad = 0;
// Early termination: if we already exceed allowed days
if (dayCount > days) return false;
}
currentLoad += w;
}
return dayCount <= days;
}
}
Dry Run Example
Input: weights = [1,2,3,4,5,6,7,8,9,10], days=5
Search Space = [10, 55]
mid = 32 → Can ship in 2 days → works → try smaller
mid = 21 → Can ship in 3 days → works → try smaller
mid = 15 → Can ship in 5 days → works → try smaller
mid = 12 → Needs 6 days → too small
Answer = 15
Summary
| Approach | Time Complexity | Space Complexity | Key Idea |
| Brute Force | O(n × (sum-max)) | O(1) | Try each capacity |
| Optimal (Binary Search) | O(n × log(sum-max)) | O(1) | Monotonic shipping feasibility → binary search |
Kth Missing Positive Number
Problem Statement
You are given a sorted array of positive integers and an integer k. Return the k-th missing positive number.
Example
arr = [2, 3, 4, 7, 11], k = 5
Missing numbers = [1, 5, 6, 8, 9, 10, 12, ...]
5th missing = 9
arr = [1, 2, 3, 4], k = 2
Missing numbers = [5, 6, 7, ...]
2nd missing = 6
Brute Force Approach
Idea
We want to find missing numbers one by one until we reach the k-th.
Iterate over all natural numbers starting from 1.
Use a pointer
iforarr.For each number
num:If
numexists inarr[i], move the pointer.Else, it’s missing → decrement
k.
When
k == 0, returnnum.
Complexity
Time Complexity: O(k + n) (since we may check up to
knumbers and scan array once).Space Complexity: O(1).
Optimal Approach (Binary Search)
Key Observation
For a position mid in the array:
Missing count till index mid = arr[mid] - (mid + 1).
Example: arr = [2, 3, 4, 7, 11]
At index 0 → missing = 2 - (0+1) = 1 (only
1missing).At index 3 → missing = 7 - (3+1) = 3 (missing numbers = {1,5,6}).
Binary Search Logic
Use binary search on indices.
If
missing(mid) < k, it means we need to search right (more missing numbers needed).Else, search left.
At the end, the position where we stop tells us the smallest index where missing ≥ k.
Final Answer:
k + left (because left tells us how many elements of arr are ≤ the position we need).
Complexity
Time Complexity: O(log n).
Space Complexity: O(1).
Summary Table
| Approach | Time Complexity | Space Complexity | Explanation |
| Brute Force | O(k + n) | O(1) | Simulates missing numbers one by one until reaching k-th. |
| Optimal (Binary Search) | O(log n) | O(1) | Uses missing count formula to binary search directly. |
import java.util.Arrays;
/**
* Demonstrates finding K-th Missing Positive Number.
* Given a sorted array of positive integers, find the k-th missing positive integer.
* Example: [2,3,4,7,11], k=5 → The missing numbers are [1,5,6,8,9,10,...] → 5th missing is 9
*/
class Main {
public static void main(String[] args) {
int[] arr = {2, 3, 4, 7, 11};
int k = 5;
System.out.println("Array: " + Arrays.toString(arr) + ", k = " + k);
// Brute Force
System.out.println("Brute Force Answer: " + findKthMissingBruteForce(arr, k));
// Optimal (Binary Search)
System.out.println("Optimal Answer: " + findKthMissingOptimal(arr, k));
/* Expected Output:
Brute Force Answer: 9
Optimal Answer: 9
*/
}
/**
* Brute Force Method: Linear scan through numbers
* Time Complexity: O(n + k) where n = arr.length
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Iterate through all positive integers, skipping those present in array
* Count missing numbers until we find the k-th missing
*
* @param arr sorted array of positive integers
* @param k the k-th missing positive number to find
* @return the k-th missing positive integer
*/
public static int findKthMissingBruteForce(int[] arr, int k) {
int i = 0; // Pointer for array index
int num = 1; // Current positive integer to check
while (true) {
// If current number exists in array, move array pointer
if (i < arr.length && arr[i] == num) {
i++;
} else {
// Current number is missing, decrement k
k--;
// If we've found the k-th missing number, return it
if (k == 0) return num;
}
num++; // Move to next positive integer
}
}
/**
* Optimal Method: Binary search to find the position
* Time Complexity: O(log n) where n = arr.length
* Space Complexity: O(1) - uses constant extra space
*
* Key Insight: For a sorted array, the number of missing numbers before arr[i] is:
* missing = arr[i] - (i + 1)
*
* Example: For arr = [2,3,4,7,11]:
* i=0: arr[0]=2, missing = 2 - (0+1) = 1 (missing: 1)
* i=1: arr[1]=3, missing = 3 - (1+1) = 1 (missing: 1)
* i=2: arr[2]=4, missing = 4 - (2+1) = 1 (missing: 1)
* i=3: arr[3]=7, missing = 7 - (3+1) = 3 (missing: 1,5,6)
* i=4: arr[4]=11, missing = 11 - (4+1) = 6 (missing: 1,5,6,8,9,10)
*
* Strategy: Use binary search to find the position where missing numbers before it < k
* but missing numbers at next position >= k
*
* @param arr sorted array of positive integers
* @param k the k-th missing positive number to find
* @return the k-th missing positive integer
*/
public static int findKthMissingOptimal(int[] arr, int k) {
int left = 0, right = arr.length - 1;
// Binary search to find the position
while (left <= right) {
int mid = left + (right - left) / 2; // Prevent integer overflow
// Calculate missing numbers before arr[mid]
// Formula: arr[mid] should be at position mid+1 if no numbers missing
// So missing numbers = actual value - expected value
int missing = arr[mid] - (mid + 1);
if (missing < k) {
// Too few missing numbers, need to search right half
left = mid + 1;
} else {
// Too many missing numbers, search left half
right = mid - 1;
}
}
/**
* After binary search, left points to the position where:
* - The number of missing numbers before arr[left] is >= k
* - The number of missing numbers before arr[left-1] is < k
*
* The k-th missing number can be calculated as:
* k + left + (number of non-missing numbers up to left)
*
* Alternatively: k + (the index where the k-th missing should be)
*
* Mathematical derivation:
* We know that before index 'left', there are 'left' actual numbers
* The k-th missing number = k + left
*
* Why?
* - If no numbers were missing, arr[i] would be i+1
* - With missing numbers, the k-th missing is k positions after the expected value
* - The 'left' index tells us how many actual numbers come before our answer
*/
return left + k;
}
}
Aggressive Cows
Problem Statement
You are given n stalls at positions stalls[] and k cows.
You must place the cows in stalls such that the minimum distance between any two cows is maximized.
Return this largest minimum distance.
Example
Stalls = [1, 2, 8, 4, 9], k = 3
Sorted stalls = [1, 2, 4, 8, 9]
Placing cows:
- Place 1st cow at stall 1
- Place 2nd cow at stall 4
- Place 3rd cow at stall 9
Minimum distance = min(3, 5) = 3
Answer = 3
Brute Force Approach
Idea
Sort the stalls.
The answer lies between 1 and (max-min) of stalls.
For each possible distance
d(from 1 to max-min):Try placing cows greedily:
Place the 1st cow at the first stall.
Place each next cow in the next stall that is at least
daway from the last cow.
If we can place all
kcows →dis feasible.
Return the largest feasible
d.
Complexity
Checking feasibility takes O(n).
Trying all distances takes O(max(stalls) - min(stalls)).
Time Complexity: O(n * (max-min)) → very large.
Space Complexity: O(1).
Optimal Approach (Binary Search on Answer)
Key Insight
The brute force checks all possible distances.
But the feasibility (
canPlaceCows) is monotonic:If distance
dis possible → all distances ≤ d are also possible.If distance
dis not possible → all distances > d are also not possible.
This means we can use Binary Search on the distance.
Algorithm
Sort the stalls.
Define search space:
low = 1(minimum possible distance).high = stalls[n-1] - stalls[0](max possible distance).
While
low <= high:mid = (low + high) / 2.If
canPlaceCows(stalls, k, mid)→ storemidas answer, and move right (low = mid + 1).Else move left (
high = mid - 1).
Return the stored answer.
Feasibility Function canPlaceCows
Place first cow at the first stall.
For each next stall:
- If distance from last placed cow ≥
mid, place a cow.
- If distance from last placed cow ≥
If we placed ≥ k cows → return true.
Else false.
Complexity
Binary search over distances: O(log(max-min)).
Each check takes O(n).
Time Complexity: O(n log(max-min)).
Space Complexity: O(1).
Summary Table
| Approach | Time Complexity | Space Complexity | Explanation |
| Brute Force | O(n * (max-min)) | O(1) | Try every possible distance. Very slow for large values. |
| Optimal (Binary Search) | O(n log(max-min)) | O(1) | Use binary search on distance with greedy feasibility check. |
import java.util.Arrays;
/**
* Aggressive Cows Problem Solution (Brute Force + Optimal).
* Problem: Place k cows in n stalls such that the minimum distance between any two cows is maximized.
*/
class Main {
public static void main(String[] args) {
int[] stalls = {1, 2, 8, 4, 9};
int k = 3;
System.out.println("Stalls: " + Arrays.toString(stalls) + ", Cows = " + k);
// Brute Force
System.out.println("Brute Force Answer: " + aggressiveCowsBruteForce(stalls, k));
// Optimal (Binary Search)
System.out.println("Optimal Answer: " + aggressiveCowsOptimal(stalls, k));
/* Expected Output:
Brute Force Answer: 3
Optimal Answer: 3
*/
}
/**
* Brute Force Method: Linear search for maximum minimum distance
* Time Complexity: O(n * max_dist) where n = stalls.length, max_dist = range of stalls
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Try every possible distance from 1 to maximum possible distance
* and return the largest distance that allows placing all cows
*
* @param stalls array of stall positions
* @param k number of cows to place
* @return maximum minimum distance between cows
*/
public static int aggressiveCowsBruteForce(int[] stalls, int k) {
// First, sort the stalls to process them in order
Arrays.sort(stalls);
// Calculate maximum possible distance (between first and last stall)
int maxDist = stalls[stalls.length - 1] - stalls[0];
int ans = 0;
// Try every possible distance from 1 to maxDist
for (int d = 1; d <= maxDist; d++) {
if (canPlaceCows(stalls, k, d)) {
// This distance works, update answer
ans = d;
} else {
// Since distances are tried in increasing order,
// once we fail, all larger distances will also fail
break;
}
}
return ans;
}
/**
* Optimal Method: Binary search for maximum minimum distance
* Time Complexity: O(n * log(max_dist)) where n = stalls.length
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Use binary search to find the maximum distance that allows
* placing all cows. The search space is [1, max_distance].
*
* Key Insight: The feasibility function is monotonic:
* - If distance d works, any distance < d also works
* - If distance d doesn't work, any distance > d also won't work
*
* @param stalls array of stall positions
* @param k number of cows to place
* @return maximum minimum distance between cows
*/
public static int aggressiveCowsOptimal(int[] stalls, int k) {
// First, sort the stalls to process them in order
Arrays.sort(stalls);
// Set up binary search bounds
int low = 1; // Minimum possible distance
int high = stalls[stalls.length - 1] - stalls[0]; // Maximum possible distance
int ans = 0;
// Binary search over possible distances
while (low <= high) {
int mid = low + (high - low) / 2; // Prevent integer overflow
if (canPlaceCows(stalls, k, mid)) {
// mid distance works, try larger distance
ans = mid;
low = mid + 1;
} else {
// mid distance is too large, try smaller distance
high = mid - 1;
}
}
return ans;
}
/**
* Helper function: Check if we can place k cows with at least 'dist' distance between them
* Time Complexity: O(n) where n = stalls.length
* Space Complexity: O(1) - uses constant extra space
*
* Greedy strategy: Place first cow at first stall, then try to place each subsequent cow
* at the first stall that is at least 'dist' away from the last placed cow
*
* @param stalls sorted array of stall positions
* @param k number of cows to place
* @param dist minimum distance required between cows
* @return true if k cows can be placed with at least 'dist' distance between them
*/
private static boolean canPlaceCows(int[] stalls, int k, int dist) {
int count = 1; // Place first cow at first stall
int lastPos = stalls[0]; // Position of last placed cow
for (int i = 1; i < stalls.length; i++) {
// Check if current stall is far enough from last placed cow
if (stalls[i] - lastPos >= dist) {
count++; // Place a cow here
lastPos = stalls[i]; // Update last position
// Early termination: if we've placed all cows
if (count >= k) return true;
}
// If not enough distance, skip this stall and continue
}
return count >= k;
}
}
Allocate Minimum Number of Pages
Problem Statement
You are given an array pages[] where pages[i] represents the number of pages in the i-th book.
You have m students, and you must allocate consecutive books to each student such that:
Each book is allocated to exactly one student.
Each student gets at least one book.
The maximum number of pages assigned to a student is minimized.
Return this minimum possible maximum.
Example
pages = [12, 34, 67, 90], m = 2
Possible allocations:
- [12, 34] | [67, 90] → max = 157
- [12] | [34, 67, 90] → max = 191
- [12, 34, 67] | [90] → max = 113
Answer = 113
Brute Force Approach
Idea
The minimum maximum pages a student can get =
max(pages)(because someone must take the largest book).The maximum possible =
sum(pages)(if one student gets all books).Try every possible
limitbetweenmax(pages)andsum(pages).Greedily check if allocation is possible with this limit.
Choose the smallest feasible limit.
Complexity
Checking feasibility = O(n).
Trying all limits = O(sum - max).
Time Complexity: O(n * (sum - max)).
Space Complexity: O(1).
Very slow for large inputs.
Optimal Approach (Binary Search on Answer)
Key Insight
If allocation is possible with
midpages, then it’s possible with any value > mid.If it’s not possible with
mid, it’s not possible with any value < mid.
This monotonic property → Binary Search.
Algorithm
Define search space:
low = max(pages)high = sum(pages)
While
low <= high:mid = (low + high) / 2If allocation is possible with
mid: store answer =mid, move left (high = mid - 1).Else move right (
low = mid + 1).
Return stored answer.
Feasibility Check
Traverse books sequentially.
Keep allocating to a student until adding another book exceeds
limit.Move to next student.
If students used ≤
m, allocation possible.
Complexity
Binary search steps = O(log(sum - max)).
Each check = O(n).
Time Complexity: O(n log(sum - max)).
Space Complexity: O(1).
Summary Table
| Approach | Time Complexity | Space Complexity | Explanation |
| Brute Force | O(n * (sum - max)) | O(1) | Try every possible max pages, slow |
| Optimal (Binary Search) | O(n log(sum - max)) | O(1) | Binary search on possible max pages with feasibility check |
import java.util.Arrays;
/**
* Allocate Minimum Number of Pages Problem Solution
* (Brute Force + Optimal using Binary Search).
* Problem: Allocate books to m students such that:
* 1. Each student gets at least one book
* 2. Each book is allocated to exactly one student
* 3. The maximum number of pages assigned to any student is minimized
*/
class Main {
public static void main(String[] args) {
int[] pages = {12, 34, 67, 90};
int m = 2;
System.out.println("Books: " + Arrays.toString(pages) + ", Students = " + m);
// Brute Force
System.out.println("Brute Force Answer: " + allocatePagesBruteForce(pages, m));
// Optimal (Binary Search)
System.out.println("Optimal Answer: " + allocatePagesOptimal(pages, m));
/* Expected Output:
Brute Force Answer: 113
Optimal Answer: 113
*/
}
/**
* Brute Force Method: Linear search for minimum maximum pages
* Time Complexity: O(n * (sum - max)) where n = pages.length
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Try every possible page limit from max book to total pages
* and return the first limit that allows allocation to all students
*
* @param pages array of book page counts
* @param m number of students
* @return minimum possible maximum pages allocated to any student
*/
public static int allocatePagesBruteForce(int[] pages, int m) {
// Lower bound: maximum book size (each student must get at least one book)
int maxBook = Arrays.stream(pages).max().getAsInt();
// Upper bound: total pages (all books to one student)
int sum = Arrays.stream(pages).sum();
int ans = sum;
// Try every possible page limit from maxBook to sum
for (int limit = maxBook; limit <= sum; limit++) {
if (isPossible(pages, m, limit)) {
// First feasible limit is the answer (since we're searching in increasing order)
ans = limit;
break;
}
}
return ans;
}
/**
* Optimal Method: Binary search for minimum maximum pages
* Time Complexity: O(n * log(sum - max)) where n = pages.length
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Use binary search to find the minimum page limit that allows
* allocation to all students. The search space is [maxBook, sum].
*
* Key Insight: The feasibility function is monotonic:
* - If limit L works, any limit > L also works
* - If limit L doesn't work, any limit < L also won't work
*
* @param pages array of book page counts
* @param m number of students
* @return minimum possible maximum pages allocated to any student
*/
public static int allocatePagesOptimal(int[] pages, int m) {
// Set up binary search bounds
int maxBook = Arrays.stream(pages).max().getAsInt();
int sum = Arrays.stream(pages).sum();
int low = maxBook, high = sum, ans = sum;
// Binary search over possible page limits
while (low <= high) {
int mid = low + (high - low) / 2; // Prevent integer overflow
if (isPossible(pages, m, mid)) {
// mid limit works, try smaller limit
ans = mid;
high = mid - 1;
} else {
// mid limit is too small, need larger limit
low = mid + 1;
}
}
return ans;
}
/**
* Helper function: Check if allocation is possible with given maximum pages per student
* Time Complexity: O(n) where n = pages.length
* Space Complexity: O(1) - uses constant extra space
*
* Greedy strategy: Allocate books to students sequentially, ensuring no student
* exceeds the maximum page limit. If a book would exceed the limit, assign it to the next student.
*
* @param pages array of book page counts
* @param m number of students available
* @param maxPages maximum pages allowed per student
* @return true if books can be allocated without exceeding maxPages for any student
*/
private static boolean isPossible(int[] pages, int m, int maxPages) {
int students = 1; // Start with first student
int currentPages = 0; // Pages allocated to current student
for (int p : pages) {
// Check if adding this book would exceed the maximum
if (currentPages + p > maxPages) {
// Start new student
students++;
currentPages = p; // Current book goes to new student
// If we need more students than available, allocation fails
if (students > m) return false;
} else {
// Add book to current student's allocation
currentPages += p;
}
}
return true; // Allocation successful with given constraints
}
}
- Split Array - Largest Sum
Problem Statement
Given an integer array nums and an integer k, split the array into k non-empty subarrays such that:
Every element must be part of exactly one subarray.
The largest sum among these subarrays is minimized.
Return this minimized largest sum.
Example
nums = [7, 2, 5, 10, 8], k = 2
Possible splits:
- [7, 2, 5] | [10, 8] → max sum = 18
- [7, 2] | [5, 10, 8] → max sum = 23
- [7] | [2, 5, 10, 8] → max sum = 25
Answer = 18
Brute Force Approach
Idea
The minimum possible answer is
max(nums)(since at least one subarray will contain the largest element).The maximum possible answer is
sum(nums)(if everything is in one subarray).Try every possible limit between
max(nums)andsum(nums):Check if it’s possible to split the array into ≤
ksubarrays with that max sum.Pick the smallest valid limit.
Complexity
Feasibility check = O(n).
Range of values =
(sum - max).Time Complexity: O(n * (sum - max)) → very slow for large arrays.
Space Complexity: O(1).
Optimal Approach (Binary Search on Answer)
Key Insight
If a split is possible with
mid, then it’s possible with any larger sum.If it’s not possible with
mid, then it’s not possible with any smaller sum.
Use Binary Search on Answer.
Algorithm
Compute:
low = max(nums)high = sum(nums)
While
low <= high:mid = (low + high) / 2If
canSplit(nums, k, mid)→ storemid, move left (high = mid - 1).Else → move right (
low = mid + 1).
Return stored answer.
Feasibility Function canSplit
Traverse
nums, maintaining a running sum.If adding the next element exceeds
mid:Start a new subarray.
Increase the count of subarrays.
If subarrays exceed
k, return false.Otherwise, return true.
Complexity
Each feasibility check = O(n).
Binary search = O(log(sum - max)).
Time Complexity: O(n log(sum - max))
Space Complexity: O(1).
Summary Table
| Approach | Time Complexity | Space Complexity | Explanation |
| Brute Force | O(n * (sum - max)) | O(1) | Try every possible max sum |
| Optimal (Binary Search) | O(n log(sum - max)) | O(1) | Binary search with greedy feasibility check |
import java.util.Arrays;
/**
* Split Array Largest Sum Problem Solution
* (Brute Force + Optimal using Binary Search).
* Problem: Split an array into k contiguous subarrays such that
* the largest sum of any subarray is minimized.
*/
class Main {
public static void main(String[] args) {
int[] nums = {7, 2, 5, 10, 8};
int k = 2;
System.out.println("Array: " + Arrays.toString(nums) + ", k = " + k);
// Brute Force
System.out.println("Brute Force Answer: " + splitArrayBruteForce(nums, k));
// Optimal (Binary Search)
System.out.println("Optimal Answer: " + splitArrayOptimal(nums, k));
/* Expected Output:
Brute Force Answer: 18
Optimal Answer: 18
*/
}
/**
* Brute Force Method: Linear search for minimum maximum subarray sum
* Time Complexity: O(n * (sum - max)) where n = nums.length
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Try every possible sum limit from maximum element to total sum
* and return the first limit that allows splitting into k subarrays
*
* @param nums array of integers to split
* @param k number of subarrays to create
* @return minimum possible maximum subarray sum
*/
public static int splitArrayBruteForce(int[] nums, int k) {
// Lower bound: maximum element (each subarray must contain at least one element)
int maxVal = Arrays.stream(nums).max().getAsInt();
// Upper bound: total sum (all elements in one subarray)
int sum = Arrays.stream(nums).sum();
int ans = sum;
// Try every possible sum limit from maxVal to sum
for (int limit = maxVal; limit <= sum; limit++) {
if (canSplit(nums, k, limit)) {
// First feasible limit is the answer (since we're searching in increasing order)
ans = limit;
break;
}
}
return ans;
}
/**
* Optimal Method: Binary search for minimum maximum subarray sum
* Time Complexity: O(n * log(sum - max)) where n = nums.length
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: Use binary search to find the minimum sum limit that allows
* splitting into k subarrays. The search space is [maxVal, sum].
*
* Key Insight: The feasibility function is monotonic:
* - If limit L works, any limit > L also works
* - If limit L doesn't work, any limit < L also won't work
*
* @param nums array of integers to split
* @param k number of subarrays to create
* @return minimum possible maximum subarray sum
*/
public static int splitArrayOptimal(int[] nums, int k) {
// Set up binary search bounds
int maxVal = Arrays.stream(nums).max().getAsInt();
int sum = Arrays.stream(nums).sum();
int low = maxVal, high = sum, ans = sum;
// Binary search over possible sum limits
while (low <= high) {
int mid = low + (high - low) / 2; // Prevent integer overflow
if (canSplit(nums, k, mid)) {
// mid limit works, try smaller limit
ans = mid;
high = mid - 1;
} else {
// mid limit is too small, need larger limit
low = mid + 1;
}
}
return ans;
}
/**
* Helper function: Check if array can be split into <= k subarrays with max sum ≤ limit
* Time Complexity: O(n) where n = nums.length
* Space Complexity: O(1) - uses constant extra space
*
* Greedy strategy: Form subarrays sequentially, ensuring no subarray exceeds the sum limit.
* If adding an element would exceed the limit, start a new subarray.
*
* @param nums array of integers to split
* @param k maximum number of subarrays allowed
* @param limit maximum allowed sum for any subarray
* @return true if array can be split into ≤ k subarrays with all sums ≤ limit
*/
private static boolean canSplit(int[] nums, int k, int limit) {
int count = 1; // Start with first subarray
int currentSum = 0; // Current subarray sum
for (int num : nums) {
// Check if adding this element would exceed the limit
if (currentSum + num > limit) {
// Start new subarray
count++;
currentSum = num; // Current element starts the new subarray
// If we need more subarrays than allowed, splitting fails
if (count > k) return false;
} else {
// Add element to current subarray
currentSum += num;
}
}
return true; // Splitting successful with given constraints
}
}
Painter's Partition Problem
Problem Statement:
You are given n boards of different lengths, and k painters. Each painter takes 1 unit of time to paint 1 unit of board. A painter can only paint contiguous boards. The task is to find the minimum time required to paint all boards if painters work simultaneously.
Brute Force Approach (Recursive / Backtracking)
Try all possible partitions of the boards among k painters and calculate the maximum time taken for each partition.
For example, if boards =
[10, 20, 30, 40]and k = 2:Partition 1:
[10,20]and[30,40]→ max = 60Partition 2:
[10,20,30]and[40]→ max = 60Partition 3:
[10]and[20,30,40]→ max = 90
The minimum among these is 60.
Steps
Recursively assign boards to each painter.
Calculate the maximum time taken by any painter for that division.
Take the minimum among all possibilities.
Complexity
Time:
O(n^k)(exponential, since we try all partitions).Space:
O(k)(recursion depth).
Clearly, this is not feasible for larger inputs.
Optimal Approach (Binary Search + Greedy Check)
This is a Partition Problem that can be solved using Binary Search on Answer.
Key Observations
The minimum possible time =
max(board length)(since at least one painter has to paint the longest board).The maximum possible time =
sum(all boards)(if only one painter paints everything).The answer lies between these two values.
We can check feasibility using a greedy approach:
If we assume a maximum time limit
mid, can we divide the boards into ≤ k painters such that no painter exceedsmid?If yes, try a smaller time.
If no, increase the time.
Greedy Check Function
boolean isPossible(int[] boards, int k, int mid) {
int painters = 1, time = 0;
for (int len : boards) {
if (time + len <= mid) {
time += len;
} else {
painters++;
time = len;
if (painters > k) return false;
}
}
return true;
}
public class PaintersPartition {
/**
* Main function to find minimum time to paint all boards
* Time Complexity: O(n * log(sum - max)) where n = boards.length
* Space Complexity: O(1) - uses constant extra space
*
* Problem: Given k painters and boards of different lengths, find the minimum time
* required to paint all boards where:
* 1. Each painter paints contiguous boards
* 2. Each painter paints at a rate of 1 unit time per unit board length
* 3. Minimize the maximum time taken by any painter
*
* @param boards array of board lengths
* @param k number of painters
* @return minimum time to paint all boards
*/
public static int minTime(int[] boards, int k) {
// Initialize search bounds:
int low = 0, high = 0;
for (int len : boards) {
low = Math.max(low, len); // Minimum possible time: longest board (one painter per board)
high += len; // Maximum possible time: sum of all boards (one painter does all)
}
int ans = high; // Initialize answer to worst case
// Binary search over possible time limits
while (low <= high) {
int mid = low + (high - low) / 2; // Prevent integer overflow
if (isPossible(boards, k, mid)) {
// mid time is feasible, try to find smaller time
ans = mid;
high = mid - 1;
} else {
// mid time is not enough, need larger time
low = mid + 1;
}
}
return ans;
}
/**
* Helper function to check if painting is possible within given time constraint
* Time Complexity: O(n) where n = boards.length
* Space Complexity: O(1) - uses constant extra space
*
* Greedy strategy: Assign boards to painters sequentially, ensuring no painter
* exceeds the time limit. If a board would exceed the limit, assign it to the next painter.
*
* @param boards array of board lengths
* @param k number of painters available
* @param maxTime maximum time allowed per painter
* @return true if all boards can be painted within maxTime using ≤ k painters
*/
private static boolean isPossible(int[] boards, int k, int maxTime) {
int painters = 1; // Start with first painter
int currentTime = 0; // Time used by current painter
for (int len : boards) {
// Check if adding this board would exceed the time limit
if (currentTime + len <= maxTime) {
// Add board to current painter's workload
currentTime += len;
} else {
// Start new painter
painters++;
currentTime = len; // Current board starts new painter's workload
// If we need more painters than available, allocation fails
if (painters > k) return false;
}
}
return true; // Allocation successful with given constraints
}
public static void main(String[] args) {
int[] boards = {10, 20, 30, 40};
int k = 2;
System.out.println("Minimum time: " + minTime(boards, k)); // Expected: 60
/* Explanation for boards = {10, 20, 30, 40}, k = 2:
* Optimal partition: Painter 1: [10, 20, 30] = 60 units
* Painter 2: [40] = 40 units
* Maximum time = max(60, 40) = 60
*/
}
}
Dry Run Example
Input: boards = [10, 20, 30, 40], k = 2
low = max(boards) = 40high = sum = 100
Binary Search:
mid = 70→ Possible with 2 paintersmid = 55→ Not possiblemid = 60→ Possiblemid = 59→ Not possible
Answer = 60.
Complexity Analysis
Time Complexity:
O(n * log(sum))log(sum)from binary search.Each check takes
O(n).
Space Complexity:
O(1)
- Minimise Maximum Distance between Gas Stations
Problem Statement:
We are given an array of positions of existing gas stations along a highway. We are also given an integer k = number of additional gas stations we can add.
We want to minimize the maximum distance between adjacent gas stations after adding k new stations.
Brute Force Approach (Greedy Simulation)
Idea
At every step, find the largest current gap between adjacent stations.
Place a new station in that gap (making it smaller).
Repeat this process
ktimes.
Steps
Create an array
count[]to track how many new stations are placed in each gap.At each iteration, find the gap with the maximum effective distance =
(stations[i+1] - stations[i]) / (count[i] + 1).Place a new station there → increment
count[i].After
kiterations, the answer = minimum of maximum effective gap.
Complexity
Time:
O(k * n)(each insertion scans all gaps).Space:
O(n).
Works for small inputs but too slow for largek(e.g.,10^6).
Optimal Approach (Binary Search on Answer)
This problem can be solved with Binary Search on Real Numbers.
Key Observations
The minimum possible distance =
0.The maximum possible distance =
max gap between existing stations.If we can place
kstations such that no gap exceedsmid, thenmidis feasible.Use binary search with precision (e.g., 1e-6).
Feasibility Check
For each gap
d = stations[i+1] - stations[i]:- The number of stations needed in that gap =
⌊d / mid⌋.
- The number of stations needed in that gap =
Sum over all gaps → if total ≤
k, thenmidis possible.
public class GasStations {
/**
* Main function to minimize the maximum distance between gas stations after adding k new stations
* Time Complexity: O(n * log(max_gap/epsilon)) where n = stations.length
* Space Complexity: O(1) - uses constant extra space
*
* Problem: Given existing gas stations on a line and k new stations to add,
* find the minimum possible maximum distance between adjacent stations
*
* @param stations array of existing gas station positions (sorted)
* @param k number of new stations to add
* @return minimum possible maximum distance between adjacent stations
*/
public static double minimiseMaxDistance(int[] stations, int k) {
int n = stations.length;
double low = 0.0, high = 0.0;
// Find initial maximum gap between existing stations
for (int i = 0; i < n - 1; i++) {
high = Math.max(high, stations[i+1] - stations[i]);
}
double eps = 1e-6; // Precision for binary search (0.000001)
// Binary search on the maximum distance
while (high - low > eps) {
double mid = (low + high) / 2.0;
if (isPossible(stations, k, mid)) {
// mid distance is achievable, try to minimize it further
high = mid;
} else {
// mid distance is too small, need larger distance
low = mid;
}
}
return high;
}
/**
* Helper function to check if it's possible to achieve maximum distance ≤ dist
* Time Complexity: O(n) where n = stations.length
* Space Complexity: O(1) - uses constant extra space
*
* Strategy: For each gap between existing stations, calculate how many new stations
* are needed to ensure no segment exceeds the target distance
*
* @param stations array of existing gas station positions (sorted)
* @param k number of new stations available
* @param dist target maximum distance between adjacent stations
* @return true if it's possible to achieve max distance ≤ dist with k new stations
*/
private static boolean isPossible(int[] stations, int k, double dist) {
int count = 0; // Count of new stations needed
for (int i = 0; i < stations.length - 1; i++) {
double gap = stations[i+1] - stations[i];
// Calculate how many stations needed in this gap to achieve max distance ≤ dist
// Formula: stations needed = ceil(gap / dist) - 1
// Example: gap = 10, dist = 3 → ceil(10/3) = 4 → need 3 new stations
count += (int)(gap / dist);
// Early termination: if we exceed available stations
if (count > k) return false;
}
return true;
}
public static void main(String[] args) {
int[] stations = {1, 13, 17, 23};
int k = 5;
System.out.printf("Minimum possible maximum distance: %.6f\n",
minimiseMaxDistance(stations, k));
/* Explanation:
* Existing gaps: [12, 4, 6]
* We need to add 5 new stations to minimize the maximum distance
* Optimal solution: Maximum distance ≈ 2.333...
*
* How it works:
* For gap 12: need ceil(12/2.333) - 1 = 5 - 1 = 4 stations
* For gap 4: need ceil(4/2.333) - 1 = 2 - 1 = 1 station
* For gap 6: need ceil(6/2.333) - 1 = 3 - 1 = 2 stations
* Total: 4 + 1 + 2 = 7 stations (but we only have 5)
*
* Actually, the calculation in isPossible uses (int)(gap/dist) which gives:
* gap/dist = 12/2.333 ≈ 5.14 → 5 stations needed for gap 12
* This is why we need careful binary search to find the exact minimum
*/
}
}
Dry Run Example
Input: stations = [1, 13, 17, 23], k = 5
Initial gaps:
[12, 4, 6].Binary search between
[0, 12].Check mid = 6:
gap=12 → needs 2 stations
gap=4 → needs 0
gap=6 → needs 1
total = 3 ≤ 5
Try smaller mid…
Converges to ≈ 2.0.
Complexity Analysis
Time Complexity:
O(n * log(maxGap / precision))n= number of gapsprecision = 1e-6→ ~60 iterations
Space Complexity:
O(1)
Very efficient for large constraints.
Median of Two Sorted Arrays of different sizes
Problem Statement
We are given two sorted arrays nums1 and nums2. The task is to find the median of the two arrays combined.
Brute Force (Merge Method)
Merge both arrays into one sorted array.
If total length is odd → return middle element.
If even → return average of two middle elements.
Time Complexity: O(n+m)
Space Complexity: O(n+m)
Optimal (Binary Search Partition Method)
Use binary search on the smaller array to partition both arrays.
Ensure:
l1 <= r2 && l2 <= r1(valid partition).
Median depends on total length:
Odd →
max(l1, l2)Even →
(max(l1, l2) + min(r1, r2)) / 2.0.
Time Complexity: O(log(min(n,m)))
Space Complexity: O(1)
Summary Table
| Approach | Time Complexity | Space Complexity | Explanation |
| Brute Force (Merge) | O(n+m) | O(n+m) | Merge both arrays, then pick middle element(s). |
| Optimal (Binary Search) | O(log(min(n,m))) | O(1) | Partition arrays with binary search to directly find median. |
import java.util.*;
public class MedianTwoArrays {
/**
* Brute Force Approach: Merge both arrays and find median
* Time Complexity: O(m + n) - linear time
* Space Complexity: O(m + n) - requires creating merged array
*
* Strategy:
* 1. Merge both sorted arrays into one sorted array
* 2. Find median of the merged array
*
* @param nums1 first sorted array
* @param nums2 second sorted array
* @return median of the two sorted arrays
*/
public static double findMedianBrute(int[] nums1, int[] nums2) {
int n1 = nums1.length, n2 = nums2.length;
int n = n1 + n2;
int[] merged = new int[n];
int i = 0, j = 0, k = 0;
// Merge the two sorted arrays using two-pointer technique
while (i < n1 && j < n2) {
if (nums1[i] < nums2[j]) {
merged[k++] = nums1[i++];
} else {
merged[k++] = nums2[j++];
}
}
// Add remaining elements from nums1 if any
while (i < n1) {
merged[k++] = nums1[i++];
}
// Add remaining elements from nums2 if any
while (j < n2) {
merged[k++] = nums2[j++];
}
// Calculate median based on merged array length
if (n % 2 == 1) {
// Odd length: middle element
return merged[n / 2];
} else {
// Even length: average of two middle elements
return (merged[n / 2 - 1] + merged[n / 2]) / 2.0;
}
}
/**
* Optimal Approach: Binary search on the smaller array
* Time Complexity: O(log(min(m, n))) - logarithmic time
* Space Complexity: O(1) - constant space
*
* Key Insight: The median divides the combined array into two equal halves.
* We can find the correct partition using binary search without merging.
*
* Strategy:
* 1. Ensure nums1 is the smaller array for binary search efficiency
* 2. Use binary search to find partition points in both arrays
* 3. Check if partition is valid (all left elements ≤ all right elements)
* 4. Adjust partition based on comparison results
*
* @param nums1 first sorted array
* @param nums2 second sorted array
* @return median of the two sorted arrays
*/
public static double findMedianOptimal(int[] nums1, int[] nums2) {
// Ensure nums1 is the smaller array for binary search efficiency
if (nums1.length > nums2.length) {
return findMedianOptimal(nums2, nums1);
}
int n1 = nums1.length, n2 = nums2.length;
int low = 0, high = n1; // Binary search range for nums1 partition
while (low <= high) {
// Partition position in nums1 (number of elements in left part)
int cut1 = (low + high) / 2;
// Partition position in nums2: (total + 1)/2 - cut1
// The +1 ensures left part has equal or one more element for odd total
int cut2 = (n1 + n2 + 1) / 2 - cut1;
// Handle edge cases for partition boundaries:
// Left part values (max of left halves)
int l1 = (cut1 == 0) ? Integer.MIN_VALUE : nums1[cut1 - 1];
int l2 = (cut2 == 0) ? Integer.MIN_VALUE : nums2[cut2 - 1];
// Right part values (min of right halves)
int r1 = (cut1 == n1) ? Integer.MAX_VALUE : nums1[cut1];
int r2 = (cut2 == n2) ? Integer.MAX_VALUE : nums2[cut2];
// Check if partition is valid (all left elements ≤ all right elements)
if (l1 <= r2 && l2 <= r1) {
// Valid partition found - calculate median
if ((n1 + n2) % 2 == 0) {
// Even total: average of max(left) and min(right)
return (Math.max(l1, l2) + Math.min(r1, r2)) / 2.0;
} else {
// Odd total: max(left) (left part has one more element)
return Math.max(l1, l2);
}
} else if (l1 > r2) {
// nums1's left element is too large - move partition left in nums1
high = cut1 - 1;
} else {
// nums2's left element is too large - move partition right in nums1
low = cut1 + 1;
}
}
return 0.0; // Should never reach here with valid input
}
public static void main(String[] args) {
int[] nums1 = {1, 3};
int[] nums2 = {2};
System.out.println("Brute Force Median: " + findMedianBrute(nums1, nums2));
System.out.println("Optimal Median: " + findMedianOptimal(nums1, nums2));
/* Example Walkthrough for nums1 = [1,3], nums2 = [2]:
*
* Brute Force:
* Merged array: [1,2,3]
* Median = 2.0
*
* Optimal Approach:
* n1=2, n2=1, total=3 (odd)
* Binary search on nums1 (smaller array):
*
* Iteration 1: low=0, high=2
* cut1 = (0+2)/2 = 1
* cut2 = (2+1+1)/2 - 1 = 2 - 1 = 1
*
* l1 = nums1[0] = 1, l2 = nums2[0] = 2
* r1 = nums1[1] = 3, r2 = nums2[1] = MAX_VALUE
*
* Check: 1 <= MAX_VALUE ✓, 2 <= 3 ✓
* Valid partition found!
* Median = max(l1,l2) = max(1,2) = 2.0
*/
}
}
K-th Element of two sorted arrays
Problem Statement
We are given two sorted arrays nums1 and nums2 and an integer k.
We need to find the k-th smallest element in the combined sorted array.
Brute Force (Merge Method)
Merge both arrays into one sorted array (like merge step of merge sort).
Simply return the (k-1)-th element (0-based indexing).
Time Complexity: O(n+m)
Space Complexity: O(n+m)
Optimal (Binary Search Partition Method)
Use binary search on the smaller array to partition both arrays.
Maintain the condition: all elements in left partition ≤ all elements in right partition.
Ensure left partition has exactly
kelements.The k-th element is
max(l1, l2)where:l1 = max element left of cut1l2 = max element left of cut2
Time Complexity: O(log(min(n, m)))
Space Complexity: O(1)
Summary Table
| Approach | Time Complexity | Space Complexity | Explanation |
| Brute Force (Merge) | O(n+m) | O(n+m) | Merge arrays fully, return k-1 element. |
| Optimal (Binary Search) | O(log(min(n,m))) | O(1) | Use partitioning logic to directly find k-th element. |
import java.util.*;
public class KthElementTwoArrays {
/**
* Brute Force Approach: Merge both arrays and find k-th element
* Time Complexity: O(m + n) - linear time
* Space Complexity: O(m + n) - requires creating merged array
*
* Strategy:
* 1. Merge both sorted arrays into one sorted array
* 2. Return the element at position k-1 (k is 1-based index)
*
* @param nums1 first sorted array
* @param nums2 second sorted array
* @param k position to find (1-based index)
* @return k-th smallest element in the combined sorted array
*/
public static int findKthBrute(int[] nums1, int[] nums2, int k) {
int n1 = nums1.length, n2 = nums2.length;
int[] merged = new int[n1 + n2];
int i = 0, j = 0, idx = 0;
// Merge the two sorted arrays using two-pointer technique
while (i < n1 && j < n2) {
if (nums1[i] < nums2[j]) {
merged[idx++] = nums1[i++];
} else {
merged[idx++] = nums2[j++];
}
}
// Add remaining elements from nums1 if any
while (i < n1) {
merged[idx++] = nums1[i++];
}
// Add remaining elements from nums2 if any
while (j < n2) {
merged[idx++] = nums2[j++];
}
// Return k-th element (k is 1-based, so index is k-1)
return merged[k - 1];
}
/**
* Optimal Approach: Binary search to find k-th element without merging
* Time Complexity: O(log(min(m, n))) - logarithmic time
* Space Complexity: O(1) - constant space
*
* Key Insight: The k-th element can be found by partitioning both arrays
* such that the left partition contains exactly k elements and all left
* elements are ≤ all right elements.
*
* Strategy:
* 1. Ensure nums1 is the smaller array for binary search efficiency
* 2. Use binary search to find how many elements to take from nums1
* 3. Calculate how many elements to take from nums2 (k - cut1)
* 4. Check if partition is valid (all left elements ≤ all right elements)
* 5. Adjust partition based on comparison results
*
* @param nums1 first sorted array
* @param nums2 second sorted array
* @param k position to find (1-based index)
* @return k-th smallest element in the combined sorted array
*/
public static int findKthOptimal(int[] nums1, int[] nums2, int k) {
// Ensure nums1 is the smaller array for binary search efficiency
if (nums1.length > nums2.length) {
return findKthOptimal(nums2, nums1, k);
}
int n1 = nums1.length, n2 = nums2.length;
// Set binary search bounds for number of elements to take from nums1
// Lower bound: max(0, k - n2) - must take at least this many from nums1
// Upper bound: min(k, n1) - cannot take more than this from nums1
int low = Math.max(0, k - n2);
int high = Math.min(k, n1);
while (low <= high) {
// Number of elements to take from nums1
int cut1 = (low + high) / 2;
// Number of elements to take from nums2 (total k elements in left partition)
int cut2 = k - cut1;
// Handle edge cases for partition boundaries:
// Maximum elements in left partitions
int l1 = (cut1 == 0) ? Integer.MIN_VALUE : nums1[cut1 - 1];
int l2 = (cut2 == 0) ? Integer.MIN_VALUE : nums2[cut2 - 1];
// Minimum elements in right partitions
int r1 = (cut1 == n1) ? Integer.MAX_VALUE : nums1[cut1];
int r2 = (cut2 == n2) ? Integer.MAX_VALUE : nums2[cut2];
// Check if partition is valid (all left elements ≤ all right elements)
if (l1 <= r2 && l2 <= r1) {
// Valid partition found - k-th element is max of left partitions
return Math.max(l1, l2);
} else if (l1 > r2) {
// nums1's left element is too large - take fewer elements from nums1
high = cut1 - 1;
} else {
// nums2's left element is too large - take more elements from nums1
low = cut1 + 1;
}
}
return -1; // Should never reach here with valid input
}
public static void main(String[] args) {
int[] nums1 = {2, 3, 6, 7, 9};
int[] nums2 = {1, 4, 8, 10};
int k = 5;
System.out.println("Brute Force Kth Element: " + findKthBrute(nums1, nums2, k));
System.out.println("Optimal Kth Element: " + findKthOptimal(nums1, nums2, k));
/* Example Walkthrough for nums1 = [2,3,6,7,9], nums2 = [1,4,8,10], k = 5:
*
* Brute Force:
* Merged array: [1,2,3,4,6,7,8,9,10]
* 5th element = 6
*
* Optimal Approach:
* n1=5, n2=4, k=5
* low = max(0, 5-4) = 1, high = min(5,5) = 5
*
* Iteration 1: low=1, high=5
* cut1 = (1+5)/2 = 3, cut2 = 5-3 = 2
* l1 = nums1[2] = 6, l2 = nums2[1] = 4
* r1 = nums1[3] = 7, r2 = nums2[2] = 8
*
* Check: 6 <= 8 ✓, 4 <= 7 ✓
* Valid partition found!
* Kth element = max(6,4) = 6
*
* The left partition has 3 elements from nums1: [2,3,6]
* and 2 elements from nums2: [1,4]
* Total left elements: [1,2,3,4,6] → 5th element is 6
*/
}
}
Find the row with maximum number of 1's
We are given a binary matrix (each row sorted in non-decreasing order, i.e., all 0s followed by all 1s).
We need to find the row index that has the maximum number of 1s.
Approaches
| Approach | Explanation | Time Complexity | Space Complexity |
| Brute Force | Count 1s in each row by scanning all elements. Track the row with the maximum count. | O(N×M) | O(1) |
| Binary Search per Row | Since each row is sorted (0’s then 1’s), use binary search to find the first occurrence of 1. Count of 1s = M - firstIndex. Repeat for all rows. | O(N log M) | O(1) |
| Optimized O(N+M) Approach | Start from top-right corner. If you see a 1, move left (since more 1s might exist). If you see a 0, move down. Keep track of row with max 1s. | O(N+M) | O(1) |
Optimized Intuition (Best O(N+M))
Matrix rows are sorted:
0000111form.Start at
(0, M-1)→ top-right.If it’s
1→ move left (because all elements to the left may still be 1s, so this row has more 1s).If it’s
0→ move down (because this row cannot have more 1s than the rows below).Track which row gives maximum count of 1s.
This avoids scanning everything → only N+M steps max.
/**
* Class to find the row with maximum number of 1's in a binary matrix
* where each row is sorted in non-decreasing order (all 0's followed by 1's)
*/
public class MaxOnesRow {
/**
* Finds the row with maximum number of 1's in a sorted binary matrix
* Time Complexity: O(n + m) where n = rows, m = columns
* Space Complexity: O(1)
*
* @param mat The binary matrix where each row is sorted
* @return The index of row with maximum 1's, or -1 if no row contains 1's
*/
public static int rowWithMax1s(int[][] mat) {
int n = mat.length; // Number of rows
int m = mat[0].length; // Number of columns
int maxRow = -1; // Initialize result to -1 (no row found yet)
int j = m - 1; // Start from top-right corner of matrix
/**
* Algorithm Strategy:
* 1. Since each row is sorted, we can traverse the matrix efficiently
* 2. Start from top-right corner (row 0, column m-1)
* 3. For each row, move left until we find a 0
* 4. The row that allows us to move leftmost has the most 1's
*/
// Iterate through each row from top to bottom
for (int i = 0; i < n; i++) {
/**
* Move left in the current row while:
* - We haven't gone out of bounds (j >= 0)
* - The current element is 1
*
* This while loop finds the first occurrence of 0 in the current row
* from right to left, effectively counting how many 1's we skip
*/
while (j >= 0 && mat[i][j] == 1) {
j--; // Move left to check previous column
maxRow = i; // Update the row with maximum 1's
/**
* Why update maxRow here?
* - Each time we move left, we're finding a row that has
* at least as many 1's as the previous best row
* - The row that makes us move leftmost (smallest j value)
* has the most 1's
*/
}
}
return maxRow;
}
/**
* Main method to test the function with sample input
*/
public static void main(String[] args) {
// Test matrix - each row is sorted (0's followed by 1's)
int[][] mat = {
{0, 0, 0, 1}, // Row 0: 1 one
{0, 1, 1, 1}, // Row 1: 3 ones ← should be the answer
{0, 0, 1, 1} // Row 2: 2 ones
};
System.out.println("Row with maximum 1s: " + rowWithMax1s(mat));
// Expected output: 1 (second row has 3 ones)
/**
* Step-by-step execution for the test case:
* Initial: j = 3, maxRow = -1
*
* Row 0: [0,0,0,1]
* - mat[0][3] = 1 → j-- to 2, maxRow = 0
* - mat[0][2] = 0 → break while loop
*
* Row 1: [0,1,1,1]
* - mat[1][2] = 1 → j-- to 1, maxRow = 1
* - mat[1][1] = 1 → j-- to 0, maxRow = 1
* - mat[1][0] = 0 → break while loop
*
* Row 2: [0,0,1,1]
* - mat[2][0] = 0 → skip (no while loop execution)
*
* Final: maxRow = 1
*/
}
}/**
* Class to find the row with maximum number of 1's in a binary matrix
* where each row is sorted in non-decreasing order (all 0's followed by 1's)
*/
public class MaxOnesRow {
/**
* Finds the row with maximum number of 1's in a sorted binary matrix
* Time Complexity: O(n + m) where n = rows, m = columns
* Space Complexity: O(1)
*
* @param mat The binary matrix where each row is sorted
* @return The index of row with maximum 1's, or -1 if no row contains 1's
*/
public static int rowWithMax1s(int[][] mat) {
int n = mat.length; // Number of rows
int m = mat[0].length; // Number of columns
int maxRow = -1; // Initialize result to -1 (no row found yet)
int j = m - 1; // Start from top-right corner of matrix
/**
* Algorithm Strategy:
* 1. Since each row is sorted, we can traverse the matrix efficiently
* 2. Start from top-right corner (row 0, column m-1)
* 3. For each row, move left until we find a 0
* 4. The row that allows us to move leftmost has the most 1's
*/
// Iterate through each row from top to bottom
for (int i = 0; i < n; i++) {
/**
* Move left in the current row while:
* - We haven't gone out of bounds (j >= 0)
* - The current element is 1
*
* This while loop finds the first occurrence of 0 in the current row
* from right to left, effectively counting how many 1's we skip
*/
while (j >= 0 && mat[i][j] == 1) {
j--; // Move left to check previous column
maxRow = i; // Update the row with maximum 1's
/**
* Why update maxRow here?
* - Each time we move left, we're finding a row that has
* at least as many 1's as the previous best row
* - The row that makes us move leftmost (smallest j value)
* has the most 1's
*/
}
}
return maxRow;
}
/**
* Main method to test the function with sample input
*/
public static void main(String[] args) {
// Test matrix - each row is sorted (0's followed by 1's)
int[][] mat = {
{0, 0, 0, 1}, // Row 0: 1 one
{0, 1, 1, 1}, // Row 1: 3 ones ← should be the answer
{0, 0, 1, 1} // Row 2: 2 ones
};
System.out.println("Row with maximum 1s: " + rowWithMax1s(mat));
// Expected output: 1 (second row has 3 ones)
/**
* Step-by-step execution for the test case:
* Initial: j = 3, maxRow = -1
*
* Row 0: [0,0,0,1]
* - mat[0][3] = 1 → j-- to 2, maxRow = 0
* - mat[0][2] = 0 → break while loop
*
* Row 1: [0,1,1,1]
* - mat[1][2] = 1 → j-- to 1, maxRow = 1
* - mat[1][1] = 1 → j-- to 0, maxRow = 1
* - mat[1][0] = 0 → break while loop
*
* Row 2: [0,0,1,1]
* - mat[2][0] = 0 → skip (no while loop execution)
*
* Final: maxRow = 1
*/
}
}
Search in a sorted 2D matrix
We are given an N x M matrix where:
Each row is sorted in ascending order.
The first element of each row is greater than the last element of the previous row.
We need to check if a target value exists in the matrix.
Approaches
| Approach | Explanation | Time Complexity | Space Complexity |
| Brute Force | Scan every element of the matrix. If found, return true. | O(N×M) | O(1) |
| Row-wise Binary Search | Perform binary search on each row separately. | O(N log M) | O(1) |
| Flattened Binary Search (Best) | Treat the matrix as a flattened sorted array of size N×M. Apply binary search directly by mapping index to (row, col). | O(log(N×M)) | O(1) |
Optimized Intuition (Flattened Binary Search)
Since rows are connected like a single sorted array, we can imagine:
matrix[row][col] ↔ array[row * M + col]
Use binary search on range
[0 … (N×M - 1)].Map
midindex to:row = mid / Mcol = mid % M
This reduces the problem to classic binary search.
/**
* Class to demonstrate different approaches for searching a target value
* in a 2D matrix where:
* - Each row is sorted in ascending order
* - The first element of each row is greater than the last element of previous row
* - Essentially, the entire matrix can be treated as one sorted 1D array
*/
public class SearchIn2DMatrix {
/**
* BRUTE FORCE APPROACH
* Time Complexity: O(N*M) where N = rows, M = columns
* Space Complexity: O(1)
*
* Simple linear search through every element in the matrix
* Not efficient for large matrices but guaranteed to work
*
* @param mat The sorted 2D matrix
* @param target The value to search for
* @return true if target is found, false otherwise
*/
public static boolean bruteForceSearch(int[][] mat, int target) {
int n = mat.length; // Number of rows
int m = mat[0].length; // Number of columns
// Iterate through every row
for (int i = 0; i < n; i++) {
// Iterate through every column in current row
for (int j = 0; j < m; j++) {
if (mat[i][j] == target) {
return true; // Target found
}
}
}
return false; // Target not found after checking all elements
}
/**
* ROW-WISE BINARY SEARCH APPROACH
* Time Complexity: O(N log M) - We do binary search on each of N rows
* Space Complexity: O(1)
*
* Leverages the fact that each row is sorted individually
* Better than brute force but not optimal for this specific matrix structure
*
* @param mat The sorted 2D matrix
* @param target The value to search for
* @return true if target is found, false otherwise
*/
public static boolean rowWiseBinarySearch(int[][] mat, int target) {
int n = mat.length; // Number of rows
int m = mat[0].length; // Number of columns
// Check each row individually
for (int i = 0; i < n; i++) {
int low = 0, high = m - 1; // Binary search bounds for current row
// Perform binary search on the current row
while (low <= high) {
int mid = (low + high) / 2; // Middle index of current row
if (mat[i][mid] == target) {
return true; // Target found in current row
} else if (mat[i][mid] < target) {
low = mid + 1; // Search right half
} else {
high = mid - 1; // Search left half
}
}
}
return false; // Target not found in any row
}
/**
* OPTIMIZED BINARY SEARCH APPROACH (BEST)
* Time Complexity: O(log(N*M)) - Single binary search over flattened matrix
* Space Complexity: O(1)
*
* Treats the 2D matrix as a flattened 1D sorted array
* Leverages the complete sorted nature of the entire matrix
* Most efficient approach for this problem
*
* @param mat The sorted 2D matrix
* @param target The value to search for
* @return true if target is found, false otherwise
*/
public static boolean optimizedSearch(int[][] mat, int target) {
int n = mat.length; // Number of rows
int m = mat[0].length; // Number of columns
// Treat the 2D matrix as a 1D array with indices 0 to (n*m - 1)
int low = 0;
int high = n * m - 1; // Last index in the flattened array
// Standard binary search algorithm
while (low <= high) {
int mid = (low + high) / 2; // Middle index in flattened array
/**
* Convert 1D index back to 2D coordinates:
* - row = mid / number_of_columns (integer division)
* - col = mid % number_of_columns (remainder)
*
* Example: For 4x4 matrix (m=4), index 7 becomes:
* - row = 7/4 = 1 (integer division truncates)
* - col = 7%4 = 3
* So element at matrix[1][3]
*/
int row = mid / m;
int col = mid % m;
if (mat[row][col] == target) {
return true; // Target found
} else if (mat[row][col] < target) {
low = mid + 1; // Search right half
} else {
high = mid - 1; // Search left half
}
}
return false; // Target not found
}
/**
* Main method to test all search approaches
*/
public static void main(String[] args) {
// Test matrix with the required properties:
// 1. Each row sorted in ascending order
// 2. First element of each row > last element of previous row
int[][] matrix = {
{1, 3, 5, 7}, // Row 0: 1-7
{10, 11, 16, 20}, // Row 1: 10-20 (10 > 7 ✓)
{23, 30, 34, 60} // Row 2: 23-60 (23 > 20 ✓)
};
int target = 16;
// Test all three approaches
System.out.println("Brute Force: " + bruteForceSearch(matrix, target));
System.out.println("Row-wise Binary Search: " + rowWiseBinarySearch(matrix, target));
System.out.println("Optimized Search: " + optimizedSearch(matrix, target));
/**
* Optimized Search Execution Example (target = 16):
*
* Initial: low = 0, high = 11 (3x4 matrix = 12 elements)
*
* Iteration 1:
* mid = (0+11)/2 = 5
* row = 5/4 = 1, col = 5%4 = 1
* matrix[1][1] = 11 < 16 → low = 5+1 = 6
*
* Iteration 2:
* mid = (6+11)/2 = 8
* row = 8/4 = 2, col = 8%4 = 0
* matrix[2][0] = 23 > 16 → high = 8-1 = 7
*
* Iteration 3:
* mid = (6+7)/2 = 6
* row = 6/4 = 1, col = 6%4 = 2
* matrix[1][2] = 16 == 16 → return true
*/
}
}
Search in a row and column-wise sorted matrix
We are given an N x M matrix where:
Each row is sorted in increasing order.
Each column is sorted in increasing order.
We need to check if a target value exists in the matrix.
Approaches
| Approach | Explanation | Time Complexity | Space Complexity |
| Brute Force | Traverse all elements and compare with the target. | O(N×M) | O(1) |
| Row-wise Binary Search | For each row, apply binary search. | O(N log M) | O(1) |
| Optimal (Staircase Search) | Start from top-right (or bottom-left). Eliminate one row/column each step: - If target < mat[i][j] → move left. - If target > mat[i][j] → move down. | O(N+M) | O(1) |
Intuition of Staircase Search
- Matrix looks like this:
1 4 7 11
2 5 8 12
3 6 9 16
10 13 14 17
Start at top-right (
mat[0][M-1]=11here).If target < 11 → move left (since everything below is larger).
If target > 11 → move down (since everything left is smaller).
Each step reduces search space → linear in rows + cols.
/**
* Class to demonstrate different approaches for searching a target value
* in a 2D matrix where:
* - Each row is sorted in ascending order from left to right
* - Each column is sorted in ascending order from top to bottom
* - The matrix is sorted but NOT necessarily globally sorted like previous problem
*/
public class SearchInRowColSortedMatrix {
/**
* BRUTE FORCE APPROACH
* Time Complexity: O(N*M) where N = rows, M = columns
* Space Complexity: O(1)
*
* Simple linear search through every element in the matrix
* Works for any matrix but highly inefficient for large matrices
*
* @param mat The row and column sorted 2D matrix
* @param target The value to search for
* @return true if target is found, false otherwise
*/
public static boolean bruteForceSearch(int[][] mat, int target) {
int n = mat.length; // Number of rows
int m = mat[0].length; // Number of columns
// Iterate through every row
for (int i = 0; i < n; i++) {
// Iterate through every column in current row
for (int j = 0; j < m; j++) {
if (mat[i][j] == target) {
return true; // Target found
}
}
}
return false; // Target not found after checking all elements
}
/**
* ROW-WISE BINARY SEARCH APPROACH
* Time Complexity: O(N log M) - We do binary search on each of N rows
* Space Complexity: O(1)
*
* Leverages the fact that each row is sorted individually
* Better than brute force but not optimal for this matrix structure
*
* @param mat The row and column sorted 2D matrix
* @param target The value to search for
* @return true if target is found, false otherwise
*/
public static boolean rowWiseBinarySearch(int[][] mat, int target) {
int n = mat.length; // Number of rows
int m = mat[0].length; // Number of columns
// Check each row individually using binary search
for (int i = 0; i < n; i++) {
int low = 0, high = m - 1; // Binary search bounds for current row
// Perform binary search on the current row
while (low <= high) {
int mid = (low + high) / 2; // Middle index of current row
if (mat[i][mid] == target) {
return true; // Target found in current row
} else if (mat[i][mid] < target) {
low = mid + 1; // Search right half (larger values)
} else {
high = mid - 1; // Search left half (smaller values)
}
}
}
return false; // Target not found in any row
}
/**
* OPTIMIZED STAIRCASE SEARCH APPROACH (BEST)
* Time Complexity: O(N + M) - At most N+M steps
* Space Complexity: O(1)
*
* Also known as "Step-wise Search" or "Saddleback Search"
* Leverages both row-wise and column-wise sorting properties
* Starts from top-right corner and moves intelligently
*
* @param mat The row and column sorted 2D matrix
* @param target The value to search for
* @return true if target is found, false otherwise
*/
public static boolean optimizedSearch(int[][] mat, int target) {
int n = mat.length; // Number of rows
int m = mat[0].length; // Number of columns
// Start from top-right corner (can also start from bottom-left)
int row = 0;
int col = m - 1;
/**
* Algorithm Strategy:
* 1. Start at top-right corner (row 0, column m-1)
* 2. Compare current element with target:
* - If equal: target found!
* - If current > target: move LEFT (all elements in current column below are larger)
* - If current < target: move DOWN (all elements in current row to left are smaller)
* 3. Continue until we find target or go out of bounds
*/
while (row < n && col >= 0) {
if (mat[row][col] == target) {
return true; // Target found!
} else if (mat[row][col] > target) {
col--; // Move LEFT - current element too large, so all below are larger too
} else {
row++; // Move DOWN - current element too small, so all to left are smaller too
}
}
return false; // Target not found
}
/**
* Main method to test all search approaches
*/
public static void main(String[] args) {
// Test matrix with the required properties:
// 1. Each row sorted in ascending order (left to right)
// 2. Each column sorted in ascending order (top to bottom)
// Note: This is NOT globally sorted like the previous problem
int[][] matrix = {
{1, 4, 7, 11}, // Row 0: sorted
{2, 5, 8, 12}, // Row 1: sorted, and 2>1, 5>4, 8>7, 12>11 ✓
{3, 6, 9, 16}, // Row 2: sorted, and 3>2, 6>5, 9>8, 16>12 ✓
{10,13,14,17} // Row 3: sorted, and 10>3, 13>6, 14>9, 17>16 ✓
};
int target = 9;
// Test all three approaches
System.out.println("Brute Force: " + bruteForceSearch(matrix, target));
System.out.println("Row-wise Binary Search: " + rowWiseBinarySearch(matrix, target));
System.out.println("Optimized Staircase Search: " + optimizedSearch(matrix, target));
/**
* Optimized Staircase Search Execution Example (target = 9):
*
* Start: row = 0, col = 3 (top-right: matrix[0][3] = 11)
*
* Step 1: 11 > 9 → move LEFT (col = 2)
* matrix[0][2] = 7 < 9 → move DOWN (row = 1)
*
* Step 2: matrix[1][2] = 8 < 9 → move DOWN (row = 2)
*
* Step 3: matrix[2][2] = 9 == 9 → return true
*
* Total steps: 3 (much better than checking all 16 elements!)
*/
}
}
Find Peak Element (2D Matrix)
We are given an N x M matrix. A peak element is one that is strictly greater than its neighbors (up, down, left, right if they exist).
We need to return the position (row, col) of any one peak element.
Approaches
| Approach | Explanation | Time Complexity | Space Complexity |
| Brute Force | Check every cell and compare with its valid neighbors. | O(N×M) | O(1) |
| Better Approach | For each row, find max element and check if it’s a peak. | O(N×M) worst-case | O(1) |
| Optimal (Binary Search on Columns) | Use binary search on columns: | ||
| - Pick middle column. | |||
| - Find the global max element in this column. | |||
| - Compare it with left & right neighbors. | |||
| - If it’s a peak → return. | |||
| - Else, move search space towards the larger neighbor’s column. | O(N log M) | O(1) |
Intuition of Optimal Approach
Instead of scanning the whole matrix, we treat columns like a 1D binary search space.
At each step:
Find the maximum element in the middle column → candidate.
If it’s greater than its left and right neighbors → it’s a peak.
Otherwise → move towards the side with the larger neighbor (because a peak must exist there).
This reduces complexity to O(N log M).
/**
* Class to demonstrate different approaches for finding a peak element
* in a 2D matrix where:
* - A peak element is greater than or equal to all its adjacent neighbors
* - Adjacent neighbors: up, down, left, right (not diagonal)
* - Multiple peaks may exist, we need to find any one peak
*/
public class PeakElement2DMatrix {
/**
* BRUTE FORCE APPROACH
* Time Complexity: O(N*M) where N = rows, M = columns
* Space Complexity: O(1)
*
* Checks every element to see if it's a peak
* Guaranteed to find a peak but inefficient for large matrices
*
* @param mat The 2D matrix
* @return Coordinates [row, col] of a peak element, or [-1,-1] if not found
*/
public static int[] bruteForcePeak(int[][] mat) {
int n = mat.length; // Number of rows
int m = mat[0].length; // Number of columns
// Iterate through every element in the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Check all four neighbors (handle edge cases)
boolean up = (i == 0 || mat[i][j] > mat[i - 1][j]);
boolean down = (i == n - 1 || mat[i][j] > mat[i + 1][j]);
boolean left = (j == 0 || mat[i][j] > mat[i][j - 1]);
boolean right = (j == m - 1 || mat[i][j] > mat[i][j + 1]);
// If current element is greater than all neighbors, it's a peak
if (up && down && left && right) {
return new int[]{i, j};
}
}
}
return new int[]{-1, -1}; // no peak found (shouldn't happen in valid matrices)
}
/**
* ROW-WISE MAX APPROACH
* Time Complexity: O(N*M) worst case, but often better than brute force
* Space Complexity: O(1)
*
* For each row, find the maximum element and check if it's a peak vertically
* Leverages the fact that row maximum is greater than left/right neighbors
* Only needs to check up/down neighbors for potential peaks
*
* @param mat The 2D matrix
* @return Coordinates [row, col] of a peak element
*/
public static int[] rowWiseMaxPeak(int[][] mat) {
int n = mat.length; // Number of rows
int m = mat[0].length; // Number of columns
for (int i = 0; i < n; i++) {
// Find column index of maximum element in current row
int col = 0;
for (int j = 1; j < m; j++) {
if (mat[i][j] > mat[i][col]) {
col = j; // update max column index
}
}
int val = mat[i][col]; // value of row maximum
// Check only vertical neighbors (up and down)
// Since this is row maximum, it's already > left/right neighbors
boolean up = (i == 0 || val > mat[i - 1][col]);
boolean down = (i == n - 1 || val > mat[i + 1][col]);
if (up && down) {
return new int[]{i, col}; // Found peak
}
}
return new int[]{-1, -1};
}
/**
* OPTIMAL BINARY SEARCH APPROACH
* Time Complexity: O(N log M) - Binary search on columns + linear row scan
* Space Complexity: O(1)
*
* Uses binary search on columns to efficiently find a peak
* For each middle column, finds the maximum element in that column
* Then compares with left and right neighbors to decide search direction
*
* @param mat The 2D matrix
* @return Coordinates [row, col] of a peak element
*/
public static int[] findPeakGrid(int[][] mat) {
int n = mat.length; // Number of rows
int m = mat[0].length; // Number of columns
int low = 0, high = m - 1; // Binary search bounds on columns
while (low <= high) {
int midCol = (low + high) / 2; // Middle column to examine
// Find row index with maximum value in the middle column
int maxRow = 0;
for (int i = 1; i < n; i++) {
if (mat[i][midCol] > mat[maxRow][midCol]) {
maxRow = i; // update max row index
}
}
// Get left and right neighbors (handle edge cases)
int left = (midCol - 1 >= 0) ? mat[maxRow][midCol - 1] : -1;
int right = (midCol + 1 < m) ? mat[maxRow][midCol + 1] : -1;
int curr = mat[maxRow][midCol]; // Current element being examined
/**
* Decision Logic:
* - If current > both left and right: PEAK FOUND!
* - If right > current: Peak must be in right half
* - Else: Peak must be in left half
*
* Why this works:
* - The max element in column is already > up/down neighbors
* - We only need to check left/right to confirm it's a peak
* - If right is larger, there must be a peak in right half
*/
if (curr > left && curr > right) {
return new int[]{maxRow, midCol}; // Peak found
} else if (right > curr) {
low = midCol + 1; // Move to right half
} else {
high = midCol - 1; // Move to left half
}
}
return new int[]{-1, -1};
}
/**
* Main method to test all peak finding approaches
*/
public static void main(String[] args) {
// Test matrix - note that multiple peaks may exist
int[][] matrix = {
{10, 8, 10, 10}, // Possible peaks: 10 (0,0), 10 (0,2), 10 (0,3)
{14, 13, 12, 11}, // Possible peak: 14 (1,0)
{15, 9, 11, 21}, // Possible peak: 15 (2,0), 21 (2,3)
{16, 17, 19, 20} // Possible peaks: 17 (3,1), 19 (3,2), 20 (3,3)
};
int[] ans1 = bruteForcePeak(matrix);
System.out.println("Brute Force Peak at: (" + ans1[0] + "," + ans1[1] + ")");
int[] ans2 = rowWiseMaxPeak(matrix);
System.out.println("Row-wise Max Peak at: (" + ans2[0] + "," + ans2[1] + ")");
int[] ans3 = findPeakGrid(matrix);
System.out.println("Optimal Peak at: (" + ans3[0] + "," + ans3[1] + ")");
/**
* Optimal Algorithm Execution Example:
*
* Initial: low = 0, high = 3
*
* Iteration 1:
* midCol = (0+3)/2 = 1
* Find max in column 1: maxRow = 3 (value 17)
* Compare: left = 16, right = 19, current = 17
* 17 > 16 but 19 > 17 → move RIGHT (low = 2)
*
* Iteration 2:
* midCol = (2+3)/2 = 2
* Find max in column 2: maxRow = 3 (value 19)
* Compare: left = 17, right = 20, current = 19
* 19 > 17 but 20 > 19 → move RIGHT (low = 3)
*
* Iteration 3:
* midCol = (3+3)/2 = 3
* Find max in column 3: maxRow = 2 (value 21)
* Compare: left = 11, right = -1, current = 21
* 21 > 11 and 21 > -1 → PEAK FOUND at (2,3)
*/
}
}
Median of Row Wise Sorted Matrix
We are given an N x M matrix. A peak element is one that is strictly greater than its neighbors (up, down, left, right if they exist).
We need to return the position (row, col) of any one peak element.
Approaches
| Approach | Explanation | Time Complexity | Space Complexity |
| Brute Force | Check every cell and compare with its valid neighbors. | O(N×M) | O(1) |
| Better Approach | For each row, find max element and check if it’s a peak. | O(N×M) worst-case | O(1) |
| Optimal (Binary Search on Columns) | Use binary search on columns: - Pick middle column. - Find the global max element in this column. - Compare it with left & right neighbors. - If it’s a peak → return. - Else, move search space towards the larger neighbor’s column. | O(N log M) | O(1) |
Intuition of Optimal Approach
Instead of scanning the whole matrix, we treat columns like a 1D binary search space.
At each step:
Find the maximum element in the middle column → candidate.
If it’s greater than its left and right neighbors → it’s a peak.
Otherwise → move towards the side with the larger neighbor (because a peak must exist there).
This reduces complexity to O(N log M).
/**
* Class to demonstrate different approaches for finding a peak element
* in a 2D matrix where:
* - A peak element is greater than all its adjacent neighbors (up, down, left, right)
* - Multiple peaks may exist, we need to find any one peak
* - The matrix may not be sorted, but we leverage efficient search techniques
*/
public class PeakElement2DMatrix {
/**
* BRUTE FORCE APPROACH
* Time Complexity: O(N*M) where N = rows, M = columns
* Space Complexity: O(1)
*
* Checks every element to see if it's a peak by comparing with all neighbors
* Guaranteed to find a peak but inefficient for large matrices
*
* @param mat The 2D matrix
* @return Coordinates [row, col] of a peak element, or [-1,-1] if not found
*/
public static int[] bruteForcePeak(int[][] mat) {
int n = mat.length; // Number of rows
int m = mat[0].length; // Number of columns
// Iterate through every element in the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Check all four directional neighbors, handling edge cases
boolean up = (i == 0 || mat[i][j] > mat[i - 1][j]); // Check above
boolean down = (i == n - 1 || mat[i][j] > mat[i + 1][j]); // Check below
boolean left = (j == 0 || mat[i][j] > mat[i][j - 1]); // Check left
boolean right = (j == m - 1 || mat[i][j] > mat[i][j + 1]);// Check right
// If current element is greater than all adjacent neighbors, it's a peak
if (up && down && left && right) {
return new int[]{i, j}; // Return coordinates of peak
}
}
}
return new int[]{-1, -1}; // No peak found (shouldn't happen for valid matrices)
}
/**
* ROW-WISE MAXIMUM APPROACH
* Time Complexity: O(N*M) worst case, but often better than brute force
* Space Complexity: O(1)
*
* For each row, find the maximum element (which is automatically greater than left/right neighbors)
* Then check only the vertical neighbors (up/down) to see if it's a peak
* More efficient than checking all neighbors for every element
*
* @param mat The 2D matrix
* @return Coordinates [row, col] of a peak element
*/
public static int[] rowWiseMaxPeak(int[][] mat) {
int n = mat.length; // Number of rows
int m = mat[0].length; // Number of columns
// Check each row individually
for (int i = 0; i < n; i++) {
// Find column index of maximum element in current row
int col = 0; // Start with first column as maximum
for (int j = 1; j < m; j++) {
if (mat[i][j] > mat[i][col]) {
col = j; // Update maximum column index
}
}
int val = mat[i][col]; // Value of the row maximum
// Check only vertical neighbors since this element is already > left/right neighbors
boolean up = (i == 0 || val > mat[i - 1][col]); // Check element above
boolean down = (i == n - 1 || val > mat[i + 1][col]);// Check element below
// If greater than both vertical neighbors, we found a peak
if (up && down) {
return new int[]{i, col};
}
}
return new int[]{-1, -1}; // No peak found
}
/**
* OPTIMAL BINARY SEARCH APPROACH ON COLUMNS
* Time Complexity: O(N log M) - Binary search on columns + linear row scan
* Space Complexity: O(1)
*
* Uses binary search on columns to efficiently narrow down the search space
* For each middle column, finds the maximum element in that column
* Compares with left and right neighbors to decide search direction
* Leverages the fact that a column maximum is automatically greater than up/down neighbors
*
* @param mat The 2D matrix
* @return Coordinates [row, col] of a peak element
*/
public static int[] findPeakGrid(int[][] mat) {
int n = mat.length; // Number of rows
int m = mat[0].length; // Number of columns
// Binary search bounds on columns
int low = 0;
int high = m - 1;
// Binary search on columns
while (low <= high) {
int midCol = (low + high) / 2; // Middle column to examine
// Find the row with maximum value in the middle column
int maxRow = 0; // Start with first row as maximum
for (int i = 1; i < n; i++) {
if (mat[i][midCol] > mat[maxRow][midCol]) {
maxRow = i; // Update maximum row index
}
}
// Get left and right neighbors, handling edge cases
int left = (midCol - 1 >= 0) ? mat[maxRow][midCol - 1] : Integer.MIN_VALUE;
int right = (midCol + 1 < m) ? mat[maxRow][midCol + 1] : Integer.MIN_VALUE;
int curr = mat[maxRow][midCol]; // Current element being examined
/**
* Decision Logic:
* 1. If current > both left and right: PEAK FOUND!
* - Current is already > up/down (since it's column max)
* - And it's > left/right, so it's a peak
*
* 2. If right > current: There must be a peak in the right half
* - The right neighbor is larger, so we move right
*
* 3. Else (left > current): There must be a peak in the left half
* - The left neighbor is larger, so we move left
*/
if (curr > left && curr > right) {
return new int[]{maxRow, midCol}; // Peak found!
} else if (right > curr) {
low = midCol + 1; // Move to right half of columns
} else {
high = midCol - 1; // Move to left half of columns
}
}
return new int[]{-1, -1}; // No peak found (shouldn't happen)
}
/**
* Main method to test all peak finding approaches
*/
public static void main(String[] args) {
// Test matrix with multiple potential peaks
int[][] matrix = {
{10, 8, 10, 10}, // Possible peaks: (0,0)=10, (0,2)=10, (0,3)=10
{14, 13, 12, 11}, // Possible peak: (1,0)=14
{15, 9, 11, 21}, // Possible peaks: (2,0)=15, (2,3)=21
{16, 17, 19, 20} // Possible peaks: (3,1)=17, (3,2)=19, (3,3)=20
};
// Test all three approaches
int[] ans1 = bruteForcePeak(matrix);
System.out.println("Brute Force Peak at: (" + ans1[0] + "," + ans1[1] + ")");
int[] ans2 = rowWiseMaxPeak(matrix);
System.out.println("Row-wise Max Peak at: (" + ans2[0] + "," + ans2[1] + ")");
int[] ans3 = findPeakGrid(matrix);
System.out.println("Optimal Peak at: (" + ans3[0] + "," + ans3[1] + ")");
/**
* Optimal Algorithm Execution Example:
*
* Matrix: 4x4 as above
* Initial: low = 0, high = 3
*
* Iteration 1:
* midCol = (0+3)/2 = 1
* Find max in column 1: maxRow = 3 (value 17 at [3,1])
* Compare: left = 16, right = 19, current = 17
* 17 > 16 but 19 > 17 → move RIGHT (low = 2)
*
* Iteration 2:
* midCol = (2+3)/2 = 2
* Find max in column 2: maxRow = 3 (value 19 at [3,2])
* Compare: left = 17, right = 20, current = 19
* 19 > 17 but 20 > 19 → move RIGHT (low = 3)
*
* Iteration 3:
* midCol = (3+3)/2 = 3
* Find max in column 3: maxRow = 2 (value 21 at [2,3])
* Compare: left = 11, right = MIN_VALUE, current = 21
* 21 > 11 and 21 > MIN_VALUE → PEAK FOUND at (2,3)
*
* Total comparisons: 3 iterations × 4 rows = 12 comparisons
* vs Brute Force: 16 elements × 4 neighbors = 64 comparisons
*/
}
}
Binary search isn’t just about finding an element in an array—it’s about learning to approach problems with efficiency. By breaking the search space in half each time, it shows us how smart choices can save time and effort. As we move forward in this DSA journey, this algorithm is game-changing but more interestingly we will see more of this.
Do share your views!!
