binary-search-problems.md

Binary Search

Basic

Problem	Difficulty
704. Binary Search	Easy
374. Guess Number Higher or Lower	Easy

• https://leetcode.com/problems/longest-subsequence-with-limited-sum/description/ 1387
• https://leetcode.com/problems/range-frequency-queries/description/ 1702
• https://leetcode.com/problems/most-beautiful-item-for-each-query/description/ 1724
• https://leetcode.com/problems/minimum-absolute-sum-difference/description/ 1934
• [SOLVED] https://leetcode.com/problems/maximum-count-of-positive-integer-and-negative-integer/description/ 1195

Search the First/Last Position

Or find the lower/upper bound of a target.

Problem	Difficulty	Note
278. First Bad Version	Easy
35. Search Insert Position	Easy	Why returningleft?
34. Find First and Last Position of Element in Sorted Array	Medium	Lower and upper bound.
2779. Maximum Beauty of an Array After Applying Operation	Medium (1638)	Distance is 2 * k.
611. Valid Triangle Number	Medium	How to iterate the 3 pointers and update count correctly? Sort + fix i, search with two pointers or binary search.
2563. Count the Number of Fair Pairs	Medium (1720)	count(<=R) - count(<=L-1). Two pointers.

Two Pointers on Two Sorted Sequences

See Two Pointers on Two Sorted Sequences.

Search on Value

Minimum Value

• "Search the First/Last Position" is the prerequisite of "Search on Value".
• This also includes "minimize the maximum value". Order these problems by similarity, not by difficulty.
• Review Notes: Please review the lower, upper bound, monotonicity, feasibility check for all problems.

Problem	Difficulty	Note
875. Koko Eating Bananas	Medium (1766)	Eat more, shorter total time.
1011. Capacity To Ship Packages Within D Days	Medium (1725)	Larger capacity, less ship days. Split logic.
410. Split Array Largest Sum	Hard	Key intuition and split logic.
1760. Minimum Limit of Balls in a Bag	Medium (1940)	How to calculate operations count?
2187. Minimum Time to Complete Trips	Medium (1640)
2594. Minimum Time to Repair Cars	Medium (1915)
1283. Find the Smallest Divisor Given a Threshold	Medium (1542)
2064. Minimized Maximum of Products Distributed to Any Store	Medium (1886)
1870. Minimum Speed to Arrive on Time	Medium (1676)
1482. Minimum Number of Days to Make m Bouquets	Medium (1945)
2439. Minimize Maximum of Array	Medium (1965)
2560. House Robber IV	Medium (2081)
1631. Path With Minimum Effort	Medium (1947)

• https://leetcode.com/problems/swim-in-rising-water/description/ 2096, similar to 1631. Path With Minimum Effort
• https://leetcode.com/problems/minimize-the-maximum-difference-of-pairs/description/ 2155

Maximum Value

This also includes maximize the minimum value.

Problem	Difficulty
2226. Maximum Candies Allocated to K Children	Medium (1646)
1552. Magnetic Force Between Two Balls	Medium (1919)

• My contest https://leetcode.com/problems/maximize-score-of-numbers-in-ranges/description/ 1768
• https://leetcode.com/problems/find-longest-special-substring-that-occurs-thrice-ii/description/ 1773
• https://leetcode.com/problems/find-the-maximum-number-of-marked-indices/description/ 1843
• https://leetcode.com/problems/maximum-number-of-removable-characters/description/ 1912
• https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/description/ 1929
• https://leetcode.com/problems/maximum-number-of-alloys/description/ 1981
• https://leetcode.com/problems/find-the-safest-path-in-a-grid/description/ 2153

Kth Smallest/Largest Element

Some can be solved by heap. Consider to merge this section with heap problems.

Problem	Difficulty	Note
1539. Kth Missing Positive Number	Easy	Key intuition: Counting missing = arr[i] - (i + 1).
378. Kth Smallest Element in a Sorted Matrix	Medium	First element that has count(≤ x) == k.
373. Find K Pairs with Smallest Sums	Medium

• https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/description/ h
• https://leetcode.com/problems/find-k-th-smallest-pair-distance/description/
• https://leetcode.com/problems/nth-magical-number/description/ 1897
• https://leetcode.com/problems/ugly-number-iii/description/ 2039

Search in Matrix

Problem	Difficulty	Note
74. Search a 2D Matrix	Medium	Key difference between 240.
1351. Count Negative Numbers in a Sorted Matrix	Easy	count(≤ x).
240. Search a 2D Matrix II	Medium	Start from top-right or bottom-left + count(≤ x).

• https://leetcode.com/problems/find-a-peak-element-ii/

Design

Problem	Difficulty	Note
729. My Calendar I	Medium	Maintain a sorted container and binary search the insert position. (TreeMap, Sorted List, Line Sweep, BST)
981. Time Based Key-Value Store	Medium	Last previous timestamp <= timestamp.
1146. Snapshot Array	Medium (1770)	Record the change log and binary search on it.

Rotated Array

Problem	Difficulty	Note
33. Search in Rotated Sorted Array	Medium	One part is sorted.
81. Search in Rotated Sorted Array II	Medium	Key difference between 33.. Handle duplicates.
153. Find Minimum in Rotated Sorted Array	Medium	List all combinations of rotation and observe the pattern.

• https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/description/ h

Other

Problem	Difficulty	Note
69. Sqrt(x)	Easy	Last number <= x.
162. Find Peak Element	Medium
1095. Find in Mountain Array	Hard (1827)
287. Find the Duplicate Number	Medium	count(≤ x) <= x.
540. Single Element in a Sorted Array	Medium	Relation between index and number.

• https://leetcode.com/problems/peak-index-in-a-mountain-array/description/ m
• https://leetcode.com/problems/median-of-two-sorted-arrays/description/

Explanation

• 34. Find First and Last Position of Element in Sorted Array
• 2563. Count the Number of Fair Pairs
• 475. Heaters
• 875. Koko Eating Bananas
• 1011. Capacity To Ship Packages Within D Days
• 410. Split Array Largest Sum
• 1283. Find the Smallest Divisor Given a Threshold
• 2064. Minimized Maximum of Products Distributed to Any Store
• 1870. Minimum Speed to Arrive on Time
• 1482. Minimum Number of Days to Make m Bouquets
• 2439. Minimize Maximum of Array
• 2560. House Robber IV
• 1631. Path With Minimum Effort
• 2226. Maximum Candies Allocated to K Children
• 1552. Magnetic Force Between Two Balls
• 378. Kth Smallest Element in a Sorted Matrix
• 729. My Calendar I
• 162. Find Peak Element
• 287. Find the Duplicate Number
• 33. Search in Rotated Sorted Array
• 153. Find Minimum in Rotated Sorted Array
• 240. Search a 2D Matrix II
• 1146. Snapshot Array

The following problems are not covered in the problem listing.

• 3449. Maximize the Minimum Game Score
• 3399. Smallest Substring With Identical Characters II
• 3600. Maximize Spanning Tree Stability with Upgrades
• 3534. Path Existence Queries in a Graph II
• 3464. Maximize the Distance Between Points on a Square
• 2223. Sum of Scores of Built Strings
• 1923. Longest Common Subpath
• 1044. Longest Duplicate Substring
• 1062. Longest Repeating Substring
• 2302. Count Subarrays With Score Less Than K
• 3097. Shortest Subarray With OR at Least K II
• 3134. Find the Median of the Uniqueness Array
• 3116. Kth Smallest Amount With Single Denomination Combination
• 1201. Ugly Number III