Binary Search + Monotonic Stack Cheat Sheet
(Java)
22. Binary Search
Problem Statement
Given a sorted array of integers nums and a target value, return the index if
the target is found. Otherwise, return -1.
Example
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
High-Level Approach
Since the array is sorted, use Binary Search.
Compare the middle element with the target.
Eliminate half of the search space in every iteration.
Java Solution
public int search(int[] nums, int target) {
int left = 0;
int right = [Link] - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
23. Search in Rotated Sorted Array
Problem Statement
There is a sorted array rotated at some pivot. Search for the target element
and return its index. If not found, return -1.
Example
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
High-Level Approach
Use modified Binary Search.
One half of the array will always remain sorted.
Decide whether the target lies in the sorted half.
public int search(int[] nums, int target) {
int left = 0;
int right = [Link] - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
24. Daily Temperatures
Problem Statement
Given an array of daily temperatures, return an array where each element
tells how many days you have to wait for a warmer temperature. If no
warmer day exists, return 0.
Example
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
High-Level Approach
Use a Monotonic Stack to keep track of unresolved temperatures.
When a warmer temperature is found, calculate the waiting days.
Stack stores indices instead of values.
Java Solution
public int[] dailyTemperatures(int[] temperatures) {
int[] result = new int[[Link]];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < [Link]; i++) {
while (![Link]() &&
temperatures[i] > temperatures[[Link]()]) {
int index = [Link]();
result[index] = i - index;
}
[Link](i);
}
return result;
}
25. Largest Rectangle in Histogram
Problem Statement
Given an array representing histogram bar heights, return the area of the
largest rectangle.
Example
Input: heights = [2,1,5,6,2,3]
Output: 10
High-Level Approach
Use a Monotonic Increasing Stack.
When a smaller height is found, calculate areas for taller bars.
Width is determined using stack boundaries.
Java Solution
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
for (int i = 0; i <= [Link]; i++) {
int currentHeight = (i == [Link]) ? 0 : heights[i];
while (![Link]() &&
currentHeight < heights[[Link]()]) {
int height = heights[[Link]()];
int width;
if ([Link]()) {
width = i;
} else {
width = i - [Link]() - 1;
}
maxArea = [Link](maxArea, height * width);
}
[Link](i);
}
return maxArea;
}
Quick Recognition Tips
Signal in Problem Likely Pattern
Sorted array search Binary Search
Rotated sorted array Modified Binary
Search
Next greater element Monotonic Stack
Histogram / rectangle Stack
area
Need O(log n) search Binary Search
Binary Search vs Stack Quick Rule
Binary Search:
- Search space is sorted or partially sorted.
- Eliminate half each step.
Monotonic Stack:
- Need nearest greater/smaller element.
- Solve range problems efficiently.