64 articles
Solve the bottleneck shortest path problem: find a route from source to destination that minimises the maximum edge weight on the path. Combines binary search on the answer with BFS connectivity checks in O((V+E) log W) — a FAANG interview pattern asked at Google and Amazon, and the foundation behind LeetCode 1102 Path With Maximum Minimum Value.
Master LeetCode 778 Swim in Rising Water by reducing a grid puzzle to a minimax shortest-path problem. Solve it three ways — Dijkstra with max-relax, binary search plus BFS, and Kruskal-style union-find — and learn when each approach wins. A FAANG hard interview classic at Google, Amazon, and Meta.
LeetCode 33 is a rite of passage in FAANG interviews. Learn the one invariant that makes O(log n) possible on a rotated array, trace through a dry run, avoid the 4 most common bugs, and master the full family of follow-up problems (LC 81, LC 153, LC 154).
LeetCode 153 is one of the cleanest illustrations of binary search on a non-standard search space. Learn the rotation insight that unlocks O(log n), trace through a full visual dry run, avoid the three mistakes that most often break this one, and walk away ready for the duplicates variant (LC 154) and the full search-in-rotated problem (LC 33).
LeetCode 287 eliminates every naive approach through three hard constraints: no array modification, O(1) space, O(n) time. The solution — treating the array as an implicit linked list and running Floyd's tortoise-and-hare cycle detection — is one of the most elegant algorithm mappings in all of DSA. Full proof, visual dry run, Python and JavaScript solutions.
Master LeetCode 209 from first principles: understand why a variable-size shrinkable sliding window is the insight that cracks this problem in O(n), trace through every pointer movement on a real example, learn the three common interview mistakes, and be ready for the O(n log n) binary search follow-up that Amazon and Microsoft love to ask.
LeetCode 162 — asked at Google, Meta, and Amazon. Find any peak element in O(log n) using binary search on slope direction. If nums[mid] < nums[mid+1], a peak must exist in the right half — guaranteed by virtual negative infinity at both boundaries.
LeetCode 4 is one of the most feared Hard problems in FAANG interviews. Learn exactly why the partition insight works, trace through a full binary search dry run, understand the five common bugs that cause silent wrong answers, and walk away with production-quality Python and JavaScript solutions.
Master LeetCode 410: learn why binary searching on the answer (not the array) is the key insight, walk through a full greedy feasibility check, and see both the DP and binary search solutions with line-by-line commentary.
Master every binary search pattern used at FAANG interviews — classic exact match, left and right boundary, rotated array, binary search on answer, parity, and 2D matrix — with copy-pasteable templates and a 23-problem index.
LeetCode 704 — the foundational FAANG binary search problem solved in O(log n) using the classic three-way exact-match template with overflow-safe midpoint.
LeetCode 278 — find the first bad version among n versions in O(log n) API calls using left-boundary binary search, the canonical FAANG predicate-search problem.
LeetCode 35 — find the index where a target exists or should be inserted in a sorted array. The canonical FAANG left-boundary binary search and the from-scratch implementation of bisect_left.
Compute the integer square root (floor) of x using right-boundary binary search. Find the largest k where k*k <= x, understand the upper-mid trick, and learn why this is the mirror image of the left-boundary template.
LC 34 asks for the start and end index of a target in a sorted array. Solve it in O(log n) by running two separate binary searches — one for the left boundary and one for the right boundary. A top FAANG pattern.
Search a rotated sorted array in O(log n) by identifying which half is always sorted at each step and checking whether the target falls inside it. A top FAANG interview problem.
Find the minimum element in a rotated sorted array in O(log n) by comparing mid to hi to decide which side of the rotation pivot you are on. A classic FAANG pivot-search pattern.
LC 74 asks you to search a globally sorted 2D matrix in O(log(m*n)). The key insight: treat the entire matrix as a 1D sorted array using flat-index mapping (row = mid // n, col = mid % n) and run standard binary search.
Find the minimum eating speed that lets Koko finish all bananas in h hours by binary searching over the answer space and using a feasibility check. The canonical binary-search-on-answer problem.
LC 1011 asks for the minimum ship capacity to deliver all packages within D days. Binary search on the capacity range [max(weights), sum(weights)] and greedily simulate loading to check feasibility. A classic binary-search-on-answer pattern.
Find any peak element in O(log n) by always moving toward the uphill neighbor. Understand the slope-chasing invariant that guarantees a peak exists in every search window.
Find the k closest elements to x in a sorted array in O(log(n-k) + k) by binary searching for the optimal left boundary of the result window rather than searching for x itself.
Find the one non-duplicate element in O(log n) time by observing how pair indices shift after the singleton — a parity-based binary search that requires no XOR or extra space.
Find the length of the longest strictly increasing subsequence in O(n log n) using patience sorting — a binary search on a maintained tails array that is simpler and faster than classic DP.
LC 410 asks you to split an array into k non-empty subarrays to minimize the largest subarray sum. Binary search on the answer range [max(nums), sum(nums)] and greedily count splits to check feasibility. O(n log(sum - max)) total time.
Search a rotated sorted array that may contain duplicates in O(log n) average time by handling the ambiguous duplicate case with a safe lo++ shrink. Deep FAANG interview breakdown with visual dry runs and all edge cases.
Find the minimum number of days to make m bouquets of k adjacent flowers by binary searching on the day value and checking feasibility greedily. Full FAANG-level breakdown with visual dry run and all edge cases.
Find the h-index from a sorted citations array in O(log n) time using left-boundary binary search. Full FAANG interview breakdown with visual dry run, all edge cases, and intuition behind the search condition.
Count spell-potion pairs where spell * potion >= success by sorting potions and binary searching for each spell threshold. Full FAANG-level breakdown with visual dry run, all edge cases, and ceiling division intuition.
LC 378 asks for the kth smallest element in an n x n matrix sorted row-by-row and column-by-column. Binary search on the value range [min, max] and count elements <= mid using a staircase walk. O(n log(max-min)) total.
LC 1552 asks you to place m balls in sorted basket positions to maximize the minimum distance between any two balls. Binary search on the minimum distance and greedily place balls to check feasibility. A classic maximize-minimum binary search pattern.
LC 154 extends the rotated minimum search to arrays with duplicates. When nums[mid] == nums[hi], neither half can be ruled out — safely shrink by decrementing hi. Worst case degrades to O(n). A hard variant that tests invariant reasoning.
LeetCode 4 is the most famous FAANG hard problem. Solve the median of two sorted arrays in O(log(min(m,n))) by binary searching for the correct partition position.
LeetCode 315 is a Google and Amazon classic. Count how many elements to the right are smaller than each element using merge sort with index tracking or a Fenwick Tree, both running in O(n log n).
LeetCode 354 reduces a 2D nesting problem to 1D Longest Increasing Subsequence with patience sorting, giving an O(n log n) FAANG-friendly solution.
LeetCode 2439 minimizes the array maximum by transferring values right-to-left. Solve it with binary search on the answer or, more elegantly, with the prefix-average closed form.
LeetCode 1891 finds the maximum ribbon length such that we can cut at least k pieces. A clean O(n log max) binary-search-on-answer template every interviewer expects.
LeetCode 1802 maximizes the value at a given index given a sum cap and adjacent-difference constraint. A textbook O(log maxSum) binary-search-on-answer with arithmetic series math.
LC 1060 asks for the kth missing number in a sorted array. Binary search on the missing-count function: at index i, exactly nums[i] - nums[0] - i numbers are missing. Find the first index where this count >= k, then recover the answer. O(log n).
Search a row-and-column sorted 2D matrix in O(m+n) using the staircase technique from the top-right corner. Understand why binary search alone fails and why the corner is the unique elimination point.
Place C cows in N stalls to maximise the minimum distance between any two cows. Learn the canonical binary-search-on-answer pattern — the template behind Magnetic Force Between Two Balls, Split Array, and dozens of other hard problems.
Count subarrays whose sum lies in [lower, upper] using merge sort on prefix sums in O(n log n). Understand the divide-and-conquer counting trick that makes an O(n^2) brute-force drop to linearithmic time.
Find the secret number between 1 and n using the guess() API in O(log n) calls. Master the exact binary search template used in all interactive/guessing problems and understand why the API return values map directly to the lo/hi update rules.
LC 1351 asks you to count negatives in a matrix sorted both row-wise and column-wise. The O(m+n) staircase approach is optimal; an O(m log n) binary-search-per-row alternative is also acceptable. Both demonstrate how sorted structure eliminates naive O(mn) scanning.
LC 367 asks if a positive integer is a perfect square without using built-in sqrt. Binary search on [1, num] for a value k where k*k == num. Also learn the elegant O(sqrt(n)) odd-number identity. A classic easy binary search problem at Google and Apple.
LC 744 finds the smallest letter in a circular sorted array that is strictly greater than the target. Left-boundary binary search with modular wrap-around handles the circular case elegantly. A clean variant that extends the standard left-boundary template.
LC 911 requires answering repeated queries "who is leading at time t?" in O(log n) per query. Precompute the leader at each vote event, then use right-boundary binary search on the times array to answer each query. Classic precompute-and-query design.
LC 287 has n+1 integers in [1,n] with exactly one duplicate. The binary search approach counts elements <= mid: if count > mid, the duplicate is in [1,mid]. O(n log n) time, O(1) space. Also understand the O(n) Floyd cycle detection approach.
LC 786 asks for the kth smallest fraction a[i]/a[j] from a sorted prime array. Binary search on the fraction value [0.0, 1.0] and count fractions below mid using two pointers. O(n log(1/epsilon)) total. A hard binary search on value problem.
LC 1346 asks if any element and its double both appear in an array. The optimal O(n) hash set approach processes elements one by one. An O(n log n) sort-and-binary-search alternative demonstrates the binary search pattern. A good warm-up for two-sum variants.
LC 981 implements a key-value store where each key can have values at different timestamps. set() in O(1), get(key, timestamp) in O(log n) using right-boundary binary search on the sorted timestamp list. A classic design + binary search interview problem.
LC 1353 asks for the maximum number of events you can attend given start and end days. Greedy approach: each day, attend the event with the earliest end date using a min-heap. Sort events by start day and use a pointer to add available events. O(n log n).
Find the kth smallest element from two sorted arrays in O(log(m+n)) without merging. Binary elimination: compare the k/2-th element of each array; the smaller one cannot contain the kth element, so eliminate k/2 candidates. Builds directly to LC 4 (Median of Two Sorted Arrays).
LC 1870 asks for the minimum integer train speed to complete all rides within a given time limit. Binary search on speed [1, 10^7]: all rides except the last use ceiling division (must wait for the next hour), the last uses exact division. Classic binary-search-on-answer pattern.
The complete Binary Search interview cheatsheet covering all 7 patterns, the universal template, Binary Search on Answer playbook, complexity reference, and MAANG priority order. Bookmark this for the day before any FAANG interview.
LeetCode 240 Search a 2D Matrix II is a Google favourite that tests staircase elimination. We solve it in O(m + n) by walking from the top-right corner — beating the naive O(m * n) scan and the O(m * log n) per-row binary search.
LC 300 Longest Increasing Subsequence finds the length of the longest strictly increasing subsequence. The O(n²) DP is the expected starting point; the O(n log n) patience sorting binary search optimization is what FAANG interviewers look for. This problem is asked at Amazon, Google, and Microsoft and is the foundation for Russian Doll Envelopes.
Find the path from top-left to bottom-right that minimizes the maximum absolute difference between consecutive cells. Dijkstra treats effort as edge weight; binary search + BFS checks feasibility for each candidate effort.
LC 981 Time Based Key-Value Store pairs a hash map with binary search to retrieve the value associated with the largest timestamp not exceeding a query — a foundational design problem tested at Google, Amazon, and Facebook.
LeetCode 378 (Medium) — a Google and Amazon staple. Solve k-th smallest in a row-and-column-sorted matrix with a min-heap k-way merge or binary search on the value range.
For each interval, find the one with the smallest start point greater than or equal to its end — a clean binary search problem that teaches index-preserving sort patterns.
Design a time-stamped key-value store that retrieves the latest value at or before a given time using binary search on sorted timestamp lists. Google and Amazon test this to evaluate versioned data design and binary search mastery.
Count nodes in a complete binary tree in O(log^2 n) by comparing left and right spine heights to detect perfect subtrees and skip counting them entirely.
LC 222 Count Complete Tree Nodes has an O(log^2 n) solution that exploits perfect subtree detection — a FAANG interview problem where the naive O(n) answer is wrong. Learn the left/right spine height comparison trick tested at Amazon and Google.