binary-search-problems.md

Binary Search

Basic

Problem	Difficulty
704. Binary Search	Easy
374. Guess Number Higher or Lower	Easy
2300. Successful Pairs of Spells and Potions	Medium (1476)
@@2779. Maximum Beauty of an Array After Applying Operation	Medium (1638)
@@826. Most Profit Assigning Work	Medium (1708)

• 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
278. First Bad Version	Easy
35. Search Insert Position	Easy
34. Find First and Last Position of Element in Sorted Array	Medium
@@475. Heaters	Medium
@@611. Valid Triangle Number	Medium
1855. Maximum Distance Between a Pair of Values	Medium (1514)
2563. Count the Number of Fair Pairs	Medium (1720)

Search on Value

Minimum Value

• "Search the First/Last Position" is the prerequisite of "Search on Value".
• This also includes "minimize the maximum value". I order these problems by similarity, not by difficulty.

Problem	Difficulty
875. Koko Eating Bananas	Medium (1766)
@@1011. Capacity To Ship Packages Within D Days	Medium (1725)
@@410. Split Array Largest Sum	Hard
1760. Minimum Limit of Balls in a Bag	Medium (1940)
@@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

Problem	Difficulty
378. Kth Smallest Element in a Sorted Matrix	Medium
@@373. Find K Pairs with Smallest Sums	Medium

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

• https://leetcode.com/problems/kth-missing-positive-number/description/ e
• 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
74. Search a 2D Matrix	Medium
1351. Count Negative Numbers in a Sorted Matrix	Easy
240. Search a 2D Matrix II	Medium

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

Design

Problem	Difficulty
729. My Calendar I	Medium
981. Time Based Key-Value Store	Medium
@@1146. Snapshot Array	Medium (1770)

Rotated Array

Problem	Difficulty
33. Search in Rotated Sorted Array	Medium
153. Find Minimum in Rotated Sorted Array	Medium

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

Other

Problem	Difficulty
69. Sqrt(x)	Easy
@@633. Sum of Square Numbers	Medium
162. Find Peak Element	Medium
1095. Find in Mountain Array	Hard (1827)
287. Find the Duplicate Number	Medium
540. Single Element in a Sorted Array	Medium

• 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
• 475. Heaters
• 875. Koko Eating Bananas
• 1011. Capacity To Ship Packages Within D Days
• 1482. Minimum Number of Days to Make m Bouquets
• 1631. Path With Minimum Effort
• 2560. House Robber IV
• 2226. Maximum Candies Allocated to K Children
• 410. Split Array Largest Sum
• 2064. Minimized Maximum of Products Distributed to Any Store
• 1552. Magnetic Force Between Two Balls
• 240. Search a 2D Matrix II
• 378. Kth Smallest Element in a Sorted Matrix
• 729. My Calendar I
• 1146. Snapshot Array
• 162. Find Peak Element
• 287. Find the Duplicate Number
• 33. Search in Rotated Sorted Array
• 153. Find Minimum in Rotated Sorted Array