Modified Binary Search

Problem: A sorted array of distinct numbers was rotated at an unknown pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Find the index of target in O(log n), or return -1.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 5000 · -10⁴ ≤ nums[i] ≤ 10⁴ · All values of nums are unique. · nums is an ascending array that is possibly rotated. · -10⁴ ≤ target ≤ 10⁴

From brute force to the pattern: A linear scan is O(n), but the problem asks for O(log n). Even after rotation, one half around mid is always sorted, so each step can still discard half the array: O(log n).

Spot it: "sorted" + "rotated" + "O(log n)" → modified binary search.

Key insight: Cut a rotated array anywhere and at least one half is perfectly sorted. Check which one (nums[lo] ≤ nums[mid] means the left half is sorted). In a sorted half you can tell instantly whether the target is inside by comparing with its two ends. If it is, go there. If not, go to the other half.

Approach:

1. Use a closed window low = 0, high = n − 1 and loop while low ≤ high.
2. If nums[middle] == target, return middle.
3. If nums[low] ≤ nums[middle], the left half is sorted. If the target lies in [nums[low], nums[middle]), go left; otherwise go right.
4. Otherwise the right half is sorted. If the target lies in (nums[middle], nums[high]], go right; otherwise go left.
5. If the window becomes empty, return -1.

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # Closed window [low, high]: both ends are still candidates.
        low = 0
        high = len(nums) - 1

        while low <= high:
            # Look at the middle element.
            middle = (low + high) // 2

            # Lucky case: the middle element IS the target.
            if nums[middle] == target:
                return middle

            if nums[low] <= nums[middle]:
                # The LEFT half nums[low..middle] is sorted (no drop inside it).
                # In a sorted piece we can check "is target inside?" with its ends.
                if nums[low] <= target and target < nums[middle]:
                    # Target is inside the sorted left half: go left.
                    high = middle - 1
                else:
                    # Target is not there, so it must be in the right half.
                    low = middle + 1
            else:
                # Otherwise the RIGHT half nums[middle..high] is sorted.
                if nums[middle] < target and target <= nums[high]:
                    # Target is inside the sorted right half: go right.
                    low = middle + 1
                else:
                    # Target is not there, so it must be in the left half.
                    high = middle - 1

        # The window became empty: the target is not in the array.
        return -1

What the code is doing, line by line:

1. low = 0, high = len(nums) - 1: a closed window, both ends are still possible answers. The loop runs while the window is not empty (low <= high).
2. Compute middle. If it holds the target, return it straight away.
3. if nums[low] <= nums[middle]: the left part has no drop in it, so it is sorted. Its smallest value is nums[low] and its biggest is nums[middle]. If the target is between them, it can only be on the left (high = middle - 1); otherwise it can only be on the right (low = middle + 1).
4. else: the drop is in the left part, so the right part middle..high is sorted. If the target is between nums[middle] (exclusive) and nums[high], go right (low = middle + 1); otherwise go left (high = middle - 1).
5. If the loop ends without finding the target, return -1.

Dry run on the example nums = [4, 5, 6, 7, 0, 1, 2], target = 0:

Edge cases to test:

• No rotation at all.
• Two elements, e.g. [3, 1].
• The target is the first or last element, or is missing.

Complexity: O(log n) time, O(1) space.

Problem: In a sorted array (with duplicates), return [first, last] index of target, or [-1, -1]. Must be O(log n).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 0 ≤ nums.length ≤ 10⁵ · -10⁹ ≤ nums[i] ≤ 10⁹ · nums is a non-decreasing array. · -10⁹ ≤ target ≤ 10⁹

From brute force to the pattern: Finding the target and then walking left and right is O(n) when the target repeats many times. Two lower-bound searches find both ends in O(log n).

Spot it: "first and last position" in a sorted array: two boundary searches.

Key insight: The first position is lower_bound(target), the first index with value ≥ target. The last position is one before lower_bound(target + 1). Same template, called twice.

Approach:

1. Write first_index_at_least(goal): the first index with nums[i] ≥ goal (half-open template).
2. first = first_index_at_least(target). If it's out of range or nums[first] != target, return [-1, -1].
3. last = first_index_at_least(target + 1) − 1, the last index whose value is < target + 1.
4. Return [first, last].

from typing import List

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # Helper: the first index whose value is >= goal (the lower bound).
        def first_index_at_least(goal):
            low = 0
            high = len(nums)
            while low < high:
                middle = (low + high) // 2
                if nums[middle] < goal:
                    # Too small: the answer is to the right of middle.
                    low = middle + 1
                else:
                    # Big enough: middle might be the answer, keep it.
                    high = middle
            return low

        # Step 1: where does target start?
        first = first_index_at_least(target)

        # If that index is past the end, or holds a different number,
        # the target does not appear at all.
        if first == len(nums):
            return [-1, -1]
        if nums[first] != target:
            return [-1, -1]

        # Step 2: the first index holding something >= target + 1 is just
        # after the last copy of target, so step back by one.
        last = first_index_at_least(target + 1) - 1
        return [first, last]

What the code is doing, line by line:

1. first_index_at_least(goal) is the lower-bound template from section 5: a half-open window [low, high) that keeps middle when nums[middle] >= goal and skips past it otherwise. It returns the first index whose value is at least goal (or len(nums) if none).
2. first = first_index_at_least(target): if target is in the list, this is its first copy.
3. Two safety checks: if first is len(nums) (everything was smaller) or nums[first] is some bigger number, the target is missing, so return [-1, -1].
4. Because the numbers are whole numbers, "the first value ≥ target + 1" is the first value bigger than target. One step before it is the last copy of target: last = first_index_at_least(target + 1) - 1.
5. Return both positions.

Dry run on the example nums = [5, 7, 7, 8, 8, 10], target = 8 (two calls to the helper):

nums[3] == 8, so the checks pass and the answer is [3, 4].

Edge cases to test:

• Target missing → [-1, -1].
• An empty array.
• Every element equals the target.

Complexity: O(log n) time, O(1) space.

Problem: Return the minimum of a rotated sorted array of distinct numbers in O(log n).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: n == nums.length · 1 ≤ n ≤ 5000 · -5000 ≤ nums[i] ≤ 5000 · All the integers of nums are unique. · nums is sorted and rotated between 1 and n times.

From brute force to the pattern: min(nums) is O(n). The rotation point (the minimum) splits the array into two sorted runs, and comparing with the right end tells you which run mid is in: O(log n).

Spot it: The minimum is the "rotation point". Compared with the last element, the array looks like bigger, bigger, …, smaller, smaller: a yes/no boundary.

Key insight: If nums[mid] > nums[hi], mid is in the left (rotated-up) part and the minimum is strictly to its right. Otherwise mid..hi is sorted and the minimum is at mid or to its left. Compare with hi, not lo: comparing with lo fails on arrays that aren't rotated at all.

Approach:

1. Window low = 0, high = n − 1, loop while low < high.
2. If nums[middle] > nums[high], the drop (the minimum) is strictly to the right: low = middle + 1.
3. Otherwise middle..high is sorted, so the minimum is at middle or to its left: high = middle.
4. When low == high, return nums[low].

from typing import List

class Solution:
    def findMin(self, nums: List[int]) -> int:
        low = 0
        high = len(nums) - 1

        # Stop when one candidate is left (low == high).
        while low < high:
            middle = (low + high) // 2

            if nums[middle] > nums[high]:
                # middle is bigger than the right end, so the "drop" (the
                # minimum) is somewhere strictly to the right of middle.
                low = middle + 1
            else:
                # nums[middle..high] is sorted, so the minimum is middle
                # itself or something to its left.
                high = middle

        # Only one candidate is left: that is the minimum.
        return nums[low]

What the code is doing, line by line:

1. low = 0, high = len(nums) - 1: the minimum could be anywhere.
2. The loop runs while more than one candidate is left.
3. If nums[middle] > nums[high], the numbers go down somewhere between middle and high (in a sorted stretch the left end is never bigger than the right end). That drop is where the minimum sits, so it is strictly right of middle: low = middle + 1.
4. Otherwise nums[middle] <= nums[high], so middle..high is sorted and its smallest number is nums[middle]. The minimum is middle or somewhere to its left: high = middle.
5. When one candidate is left, return its value.

Dry run on the example nums = [3, 4, 5, 1, 2]:

Now low == high == 3, so the answer is nums[3] = 1.

Edge cases to test:

• No rotation → the first element.
• A single element.
• Two elements in either order.

Complexity: O(log n) time, O(1) space.

Problem: Koko eats at speed k bananas per hour, finishing at most one pile per hour (a pile of p takes ceil(p / k) hours). Find the minimum k that lets her finish all piles within h hours.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ piles.length ≤ 10⁴ · piles.length ≤ h ≤ 10⁹ · 1 ≤ piles[i] ≤ 10⁹

From brute force to the pattern: Trying every speed from 1 upward is O(max(piles) · n). "Can finish at speed k?" flips from no to yes exactly once, so binary search over speeds needs only O(n log(max pile)).

Spot it: "minimum speed such that…". If speed k works, every faster speed works too. That's monotonic, so binary search on the answer over [1, max(piles)]. (See the second visualization above.)

Key insight: ok(k) = total hours at speed k ≤ h. Each check costs O(n), and we need only log(max pile) checks.

Approach:

1. Search space: speeds [1, max(piles)]. The top speed always works.
2. hours_needed(speed) = Σ ceil(pile / speed), computed with integers as (pile + speed − 1) // speed.
3. If hours_needed(middle) ≤ h, middle is fast enough and the answer is ≤ middle: high = middle. Otherwise low = middle + 1.
4. Return low, the slowest speed that still finishes on time.

from typing import List

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # Helper: how many hours does Koko need at this speed?
        def hours_needed(speed):
            total_hours = 0
            for pile in piles:
                # ceil(pile / speed) using only integers:
                # (pile + speed - 1) // speed rounds the division UP.
                hours_for_pile = (pile + speed - 1) // speed
                total_hours = total_hours + hours_for_pile
            return total_hours

        # The slowest useful speed is 1. The fastest we ever need is the
        # biggest pile (then every pile takes exactly 1 hour).
        low = 1
        high = max(piles)

        while low < high:
            middle = (low + high) // 2

            if hours_needed(middle) <= h:
                # Fast enough. Maybe a slower speed works too: keep middle.
                high = middle
            else:
                # Too slow, so every slower speed is too slow as well.
                low = middle + 1

        # low is the slowest speed that still finishes within h hours.
        return low

What the code is doing, line by line:

1. hours_needed(speed) adds up, pile by pile, how many hours each pile takes. A pile of 7 at speed 3 takes 3 hours (3 + 3 + 1), which is 7 ÷ 3 rounded up. (pile + speed - 1) // speed does that rounding up with whole numbers only.
2. low = 1 is the slowest possible speed. high = max(piles) always works: every pile then takes exactly 1 hour, and h is at least the number of piles.
3. In the loop, try speed middle. If it finishes within h hours, it works, and maybe a slower speed works too: high = middle.
4. If it needs more than h hours, it is too slow, and so is every slower speed: low = middle + 1.
5. When low == high, that is the slowest speed that still finishes on time.

Dry run on the example piles = [3, 6, 7, 11], h = 8 (start: low = 1, high = 11):

Now low == high == 4, so the answer is 4.

Edge cases to test:

• h equals the number of piles → the answer is max(piles).
• A single pile.
• Huge piles (use integer ceiling division: (p + k − 1) // k).

Complexity: O(n log M) time where M = max(piles), O(1) space.

Problem: Split nums (non-negative) into k non-empty contiguous pieces so that the largest piece-sum is as small as possible. Return that value.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 1000 · 0 ≤ nums[i] ≤ 10⁶ · 1 ≤ k ≤ min(50, nums.length)

From brute force to the pattern: Trying every way to cut into k pieces is exponential; DP is O(k · n²). The answer lies in [max(nums), sum(nums)], and feasibility is monotonic in the cap, so binary search with a greedy check is O(n log(sum)).

Spot it: "minimize the largest sum" means "minimize the maximum", the classic binary-search-on-the-answer phrase. If a cap of X per piece is achievable with ≤ k pieces, any bigger cap is too.

Key insight: The answer lies between max(nums) (no piece can be smaller than the biggest element) and sum(nums) (one piece). For a guess cap, greedily pack elements left to right and start a new piece only when the next element would overflow. If that uses ≤ k pieces, cap is feasible.

Approach:

1. Search space for the answer: [max(nums), sum(nums)].
2. pieces_needed(cap): walk left to right and start a new piece whenever adding the next number would exceed cap.
3. If pieces_needed(middle) ≤ k, the cap is feasible (you can always split further to use exactly k pieces): high = middle. Otherwise low = middle + 1.
4. Return low, the smallest feasible cap.

from typing import List

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        # Helper: if no piece may sum to more than cap, how many pieces do we
        # need? Fill each piece greedily from left to right.
        def pieces_needed(cap):
            pieces = 1
            current_sum = 0
            for number in nums:
                if current_sum + number > cap:
                    # This number does not fit: close the piece, start a new one.
                    pieces = pieces + 1
                    current_sum = 0
                current_sum = current_sum + number
            return pieces

        # The answer is at least the biggest single number (it has to go in
        # some piece) and at most the total (everything in one piece).
        low = max(nums)
        high = sum(nums)

        while low < high:
            middle = (low + high) // 2

            if pieces_needed(middle) <= k:
                # This cap is achievable with k or fewer pieces: try smaller.
                high = middle
            else:
                # Needs too many pieces: the cap must be bigger.
                low = middle + 1

        # low is the smallest cap that works.
        return low

What the code is doing, line by line:

1. pieces_needed(cap) starts with one piece whose running total current_sum is 0. For each number: if adding it would go over cap, close this piece (count one more piece, reset the total to 0). Then add the number to the current piece. It returns how many pieces were used.
2. low = max(nums) because some piece must contain the biggest number. high = sum(nums) because one piece holding everything always works.
3. In the loop, try the cap middle. If it needs k or fewer pieces, it is achievable (you could split pieces further to reach exactly k), so try smaller: high = middle.
4. If it needs more than k pieces, the cap is too small: low = middle + 1.
5. When low == high, that is the smallest achievable "largest piece sum".

Dry run on the example nums = [7, 2, 5, 10, 8], k = 2 (start: low = 10, high = 32):

Now low == high == 18: the best split is [7, 2, 5] | [10, 8] with sums 14 and 18.

Edge cases to test:

• k = 1 → the total sum.
• k = n → the largest element.
• Zeros in the array.

Complexity: O(n log S) time where S = sum(nums), O(1) space. (A DP solution is O(k·n²).)

Problem: Given a sorted array of distinct numbers, return the index of target, or the index where it would be inserted to keep the array sorted.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 10⁴ · -10⁴ ≤ nums[i] ≤ 10⁴ · nums contains distinct values sorted in ascending order. · -10⁴ ≤ target ≤ 10⁴

From brute force to the pattern: A linear scan for the first element ≥ target is O(n). Lower-bound binary search finds the same index in O(log n).

Spot it: "Where would it go" is the first index with nums[i] ≥ target. That's exactly lower bound.

Approach:

1. Half-open window [0, n).
2. If nums[middle] < target, set low = middle + 1; else high = middle.
3. Return low.

from typing import List

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # Half-open window [low, high). high starts at len(nums) because
        # the answer can be "insert at the very end".
        low = 0
        high = len(nums)

        while low < high:
            middle = (low + high) // 2

            if nums[middle] < target:
                # Too small: target belongs to the right of middle.
                low = middle + 1
            else:
                # nums[middle] >= target: middle is a valid spot,
                # but an earlier spot might be valid too.
                high = middle

        # low is the first index whose value is >= target.
        return low

What the code is doing, line by line:

1. low = 0, high = len(nums): the answer is somewhere from 0 to len(nums). len(nums) means "after the last element".
2. Each loop looks at middle. If nums[middle] is smaller than the target, the target must go after it: low = middle + 1.
3. If nums[middle] is at least the target, putting the target at middle keeps the list sorted, but maybe an earlier spot also works. Keep middle and drop the right side: high = middle.
4. When low == high, that index is the first value ≥ target: the target's position if present, or where it would be inserted.

Dry run on the example nums = [1, 3, 5, 6], target = 5:

Now low == high == 2, so the answer is 2.

Edge cases to test:

• The target is smaller than everything → 0.
• The target is larger than everything → n.
• The target is present.

Complexity: O(log n) time, O(1) space.

Problem: Return the index of any element strictly greater than its neighbors. Treat nums[−1] and nums[n] as −∞. Adjacent values are never equal. Required: O(log n).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 1000 · -2³¹ ≤ nums[i] ≤ 2³¹ - 1 · nums[i] != nums[i + 1] for all valid i.

From brute force to the pattern: Scanning for any element bigger than both neighbours is O(n). Walking toward the higher neighbour always keeps a peak inside the window, so binary search finds one in O(log n).

Spot it: The array isn't sorted, but comparing nums[mid] with nums[mid + 1] tells you which way is "uphill". Walking uphill always reaches a peak, because the edge is −∞.

Approach:

1. Window low = 0, high = n − 1, loop while low < high.
2. If nums[middle] < nums[middle + 1], you're on an upward slope, so a peak exists to the right: low = middle + 1.
3. Otherwise you're on a downward slope (or at a peak), so a peak exists at middle or to its left: high = middle.
4. Return low.

from typing import List

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        low = 0
        high = len(nums) - 1

        while low < high:
            # Because middle < high, middle + 1 is always a valid index.
            middle = (low + high) // 2

            if nums[middle] < nums[middle + 1]:
                # Going uphill to the right: a peak must exist on the right.
                low = middle + 1
            else:
                # Going downhill: middle or something to its left is a peak.
                high = middle

        # One candidate left: it is a peak.
        return low

What the code is doing, line by line:

1. low = 0, high = len(nums) - 1: every index might be a peak.
2. The loop runs while more than one candidate remains (low < high). Since middle rounds down, it is always less than high, so nums[middle + 1] never goes off the end.
3. If the next number is bigger, we are walking uphill. Keep walking right and we must reach a peak (at worst the last element, since past the end counts as −∞). So drop middle and everything left of it: low = middle + 1.
4. Otherwise the next number is smaller, so we are going downhill. Either middle is a peak or there is one to its left: high = middle.
5. When one index is left, it is a peak.

Dry run on the example nums = [1, 2, 1, 3, 5, 6, 4]:

Now low == high == 5: nums[5] = 6 is a peak (index 1 would also be accepted).

Edge cases to test:

• A single element → index 0.
• Strictly increasing → the last index.
• Several peaks: any one is accepted.

Complexity: O(log n) time, O(1) space.

Problem: Each row is sorted, and each row's first value is bigger than the previous row's last value. Return whether target is in the matrix.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: m == matrix.length · n == matrix[i].length · 1 ≤ m, n ≤ 100 · -10⁴ ≤ matrix[i][j], target ≤ 10⁴

From brute force to the pattern: Checking every cell is O(r · c); searching each row is O(r log c). Treating the matrix as one sorted array gives O(log(r · c)).

Spot it: Read row by row, the matrix is one long sorted array. Binary search over flat indices 0 … R·C − 1 and convert each one to (row, col).

Approach:

1. Closed window over flat indices [0, R·C − 1].
2. Convert middle to a cell: row = middle // column_count, column = middle % column_count.
3. Compare with the target and halve the window, as in classic binary search.
4. Return False if the window empties.

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row_count = len(matrix)
        column_count = len(matrix[0])

        # Pretend the matrix is one long sorted list with
        # row_count * column_count cells, numbered 0, 1, 2, ...
        low = 0
        high = row_count * column_count - 1

        while low <= high:
            middle = (low + high) // 2

            # Turn the flat position back into (row, column).
            row = middle // column_count
            column = middle % column_count
            value = matrix[row][column]

            if value == target:
                return True
            if value < target:
                # Too small: look in the later cells.
                low = middle + 1
            else:
                # Too big: look in the earlier cells.
                high = middle - 1

        # Window empty: the target is not in the matrix.
        return False

What the code is doing, line by line:

1. row_count and column_count record the matrix size.
2. Reading the rows one after another gives one long sorted list. Its positions are 0 to row_count * column_count - 1, so that is our closed window [low, high].
3. For each middle position, middle // column_count says how many full rows come before it (the row), and middle % column_count is what is left over (the column). That is the cell we read.
4. If the cell equals the target, we are done. If it is smaller, the target can only be in later positions (low = middle + 1); if bigger, only in earlier ones (high = middle - 1).
5. If the window becomes empty, the target is not there: return False.

Dry run on the example matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 (12 cells, start low = 0, high = 11):

Edge cases to test:

• A single row or a single column.
• The target smaller than the first or larger than the last element.
• A 1 × 1 matrix.

Complexity: O(log(R·C)) time, O(1) space.

Problem: Packages must ship in their given order. Each day you load packages onto a ship until the next one would exceed its capacity. Find the smallest capacity that ships everything within days days.

Solve it on LeetCode ↗

Constraints: 1 ≤ days ≤ weights.length ≤ 5 * 10⁴ · 1 ≤ weights[i] ≤ 500

From brute force to the pattern: Trying every capacity from max(weights) to sum(weights) is O(n · sum). Feasibility is monotonic in the capacity, so binary search with a greedy O(n) check is O(n log(sum)).

Spot it: "Minimum capacity such that…", and a bigger ship never needs more days. That's monotonic, so binary search on the answer (the same shape as 410 and Koko).

Approach:

1. Answer range: [max(weights), sum(weights)]. The ship must carry the heaviest package, and the full sum ships in one day.
2. days_needed(cap): load greedily, and start a new day when the next package doesn't fit.
3. If days_needed(middle) ≤ days, set high = middle; else low = middle + 1.
4. Return low.

from typing import List

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        # Helper: how many days does a ship of this capacity need?
        # Load packages in order; when the next one does not fit, sail
        # and start loading tomorrow's ship.
        def days_needed(capacity):
            day_count = 1
            current_load = 0
            for weight in weights:
                if current_load + weight > capacity:
                    # Does not fit today: it goes on tomorrow's ship.
                    day_count = day_count + 1
                    current_load = 0
                current_load = current_load + weight
            return day_count

        # The ship must carry the heaviest package, and a ship that holds
        # everything finishes in one day.
        low = max(weights)
        high = sum(weights)

        while low < high:
            middle = (low + high) // 2

            if days_needed(middle) <= days:
                # Big enough: maybe a smaller ship works too.
                high = middle
            else:
                # Too small: we need a bigger ship.
                low = middle + 1

        # low is the smallest capacity that ships on time.
        return low

What the code is doing, line by line:

1. days_needed(capacity) simulates the shipping: start on day 1 with an empty ship. For each package, if it would push the load over capacity, the ship sails, the day count goes up by one, and the load resets to 0. Then the package is loaded.
2. low = max(weights): a smaller ship could never carry the heaviest package. high = sum(weights): this ship carries everything in one day, so it surely works.
3. In the loop, try capacity middle. If it finishes within days, it works, and maybe a smaller ship works too: high = middle.
4. If it needs too many days, every smaller ship fails too: low = middle + 1.
5. When low == high, that is the smallest capacity that works.

Dry run on the example weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5 (start: low = 10, high = 55):

Now low == high == 15, so the answer is 15.

Edge cases to test:

• days = 1 → the total weight.
• days ≥ the number of packages → the heaviest package.
• Packages must keep their order (no rearranging).

Complexity: O(n log(sum)) time, O(1) space.

Problem: Implement set(key, value, timestamp) and get(key, timestamp). get returns the value set with the largest timestamp ≤ the given one, or "". Timestamps for set arrive strictly increasing.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ key.length, value.length ≤ 100 · key and value consist of lowercase English letters and digits. · 1 ≤ timestamp ≤ 10⁷ · All the timestamps timestamp of set are strictly increasing. · At most 2 * 10⁵ calls will be made to set and get.

From brute force to the pattern: Scanning a key's whole history on each get is O(n) per call. The timestamps of set calls are strictly increasing, so each list is already sorted and bisect finds the answer in O(log n).

Spot it: Each key's timestamps form a sorted list for free (they arrive in increasing order). "Largest timestamp ≤ t" is a boundary search: bisect_right(t) − 1.

Approach:

1. For each key, keep a list of timestamps and a parallel list of values.
2. set: append to both lists. They stay sorted.
3. get: binary search for the first timestamp > t (what bisect.bisect_right(times, t) would return; here we write it out by hand). Call that index low. The answer is at low − 1, or "" if low == 0.

class TimeMap:
    def __init__(self):
        # key -> list of timestamps (always increasing)
        self.times = {}
        # key -> list of values, in the same order as self.times[key]
        self.values = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        # First time we see this key: create its two empty lists.
        if key not in self.times:
            self.times[key] = []
            self.values[key] = []
        # Timestamps arrive in increasing order, so appending keeps the
        # list sorted. That is what makes binary search possible.
        self.times[key].append(timestamp)
        self.values[key].append(value)

    def get(self, key: str, timestamp: int) -> str:
        # Never stored anything for this key.
        if key not in self.times:
            return ""
        times = self.times[key]

        # Find the first index whose time is BIGGER than timestamp
        # (this is what bisect.bisect_right would return).
        low = 0
        high = len(times)
        while low < high:
            middle = (low + high) // 2
            if times[middle] <= timestamp:
                # Still allowed (<= timestamp): the answer is to the right.
                low = middle + 1
            else:
                # Too new: middle might be the first "too new" index.
                high = middle

        # Every time before index low is <= timestamp. If low is 0,
        # nothing was set early enough.
        if low == 0:
            return ""
        # The entry just before low has the largest time <= timestamp.
        return self.values[key][low - 1]

What the code is doing, line by line:

1. __init__ creates two plain dictionaries. For each key, self.times[key] is a list of timestamps and self.values[key] is the list of values stored at those timestamps (same positions).
2. set: if the key is new, give it two empty lists. Then append the timestamp and the value. Because timestamps always arrive in increasing order, the times list stays sorted without any extra work.
3. get: if the key was never set, return "". Otherwise grab its sorted times list.
4. The while loop is the half-open "find the first True" template, where the question is "is times[middle] > timestamp?". If times[middle] <= timestamp the answer is to the right (low = middle + 1); otherwise middle may be the first too-new time (high = middle).
5. After the loop, low is the first position with a time bigger than timestamp. Everything before it is allowed, and the last allowed one (low - 1) is the newest. If low == 0, there is no allowed time, so return "".

Dry run on the example: set("foo","bar",1), get("foo",1), get("foo",3), set("foo","bar2",4), get("foo",4), get("foo",5):

Edge cases to test:

• A query earlier than every timestamp → "".
• A key that was never set → "".
• A query exactly equal to a stored timestamp.

Complexity: set O(1), get O(log n), O(n) space.

Problem: Return the median of two sorted arrays combined, in O(log(min(m, n))) time.

Solve it on LeetCode ↗

Constraints: nums1.length == m · nums2.length == n · 0 ≤ m ≤ 1000 · 0 ≤ n ≤ 1000 · 1 ≤ m + n ≤ 2000 · -10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶

From brute force to the pattern: Concatenating and sorting is O((m + n) log(m + n)); a two-pointer merge to the middle is O(m + n). The intended solution binary-searches where to cut the shorter array so both halves balance: O(log(min(m, n))).

Spot it: Merging would be O(m + n). Instead, binary search for a partition: take i items from the shorter array A and j = half − i from B so that together they form the smaller half. The partition is valid when everything on the left is ≤ everything on the right.

Approach:

1. Make A the shorter array. Let half = (m + n + 1) // 2.
2. Binary search i in [0, m], with j = half − i. Read the four border values, using ±∞ past the ends.
3. Valid when A[i−1] ≤ B[j] and B[j−1] ≤ A[i]. Then median = max(left borders) if the total is odd, else the average of max(left borders) and min(right borders).
4. If A[i−1] > B[j], you took too many from A: high = i − 1. Otherwise low = i + 1. (In the code, A is shorter, B is longer, i is take_short and j is take_long.)

from typing import List

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # Always binary search the SHORTER array (fewer steps, and it
        # guarantees take_long below never goes negative).
        if len(nums1) <= len(nums2):
            shorter = nums1
            longer = nums2
        else:
            shorter = nums2
            longer = nums1

        short_length = len(shorter)
        long_length = len(longer)
        # How many numbers belong in the left (smaller) half overall.
        half = (short_length + long_length + 1) // 2

        # take_short = how many numbers we take from the shorter array.
        # It can be anything from 0 to short_length.
        low = 0
        high = short_length

        while low <= high:
            take_short = (low + high) // 2
            # The rest of the left half comes from the longer array.
            take_long = half - take_short

            # The four border values. Past an end we use -inf / +inf so
            # the comparisons below still work.
            if take_short > 0:
                short_left = shorter[take_short - 1]
            else:
                short_left = float("-inf")
            if take_short < short_length:
                short_right = shorter[take_short]
            else:
                short_right = float("inf")
            if take_long > 0:
                long_left = longer[take_long - 1]
            else:
                long_left = float("-inf")
            if take_long < long_length:
                long_right = longer[take_long]
            else:
                long_right = float("inf")

            if short_left <= long_right and long_left <= short_right:
                # Valid split: everything on the left <= everything on the right.
                biggest_left = max(short_left, long_left)
                if (short_length + long_length) % 2 == 1:
                    # Odd total: the median is the biggest left value.
                    return float(biggest_left)
                # Even total: average the two middle values.
                smallest_right = min(short_right, long_right)
                return (biggest_left + smallest_right) / 2

            if short_left > long_right:
                # Took too many from the shorter array: take fewer.
                high = take_short - 1
            else:
                # Took too few from the shorter array: take more.
                low = take_short + 1

What the code is doing, line by line:

1. The first if/else names the shorter list shorter and the other one longer. We only binary search the shorter one.
2. half is how many numbers the left half of the combined list must hold. The + 1 makes the left half one bigger when the total is odd, so the median is then simply the biggest left value.
3. low = 0, high = short_length: we may take anywhere from 0 to all of the shorter list into the left half.
4. Each loop tries take_short (the middle choice) and fills the rest of the left half from the longer list: take_long = half - take_short.
5. The four if/else blocks read the numbers on each side of both cuts. If a cut is at the very start or end, there is no number there, so we use -inf (left side) or inf (right side), which never break a comparison.
6. The split is correct when short_left <= long_right and long_left <= short_right: nothing on the left is bigger than anything on the right. Then the median is the biggest left value (odd total), or the average of the biggest left value and the smallest right value (even total).
7. If short_left > long_right, we took a number from the shorter list that is too big: move the cut left (high = take_short - 1). Otherwise we took too few: move it right (low = take_short + 1).

Dry run on the example nums1 = [1, 2], nums2 = [3, 4] (both length 2, so shorter = [1, 2], longer = [3, 4], half = 2):

For the other example [1, 3], [2]: shorter = [2], half = 2. Try take_short = 0 → short_left = -inf, short_right = 2, long_left = 3: 3 > 2, so low = 1. Try take_short = 1 → short_left = 2, long_left = 1, long_right = 3, short_right = inf: valid, odd total, answer max(2, 1) = 2.0.

Edge cases to test:

• One array empty.
• Total length even → the average of the two middle values.
• All of one array smaller than all of the other.

Complexity: O(log min(m, n)) time, O(1) space.

Problem: In an m × n multiplication table (cell (i, j) = i·j, 1-indexed), return the k-th smallest number.

Solve it on LeetCode ↗

Constraints: 1 ≤ m, n ≤ 3 * 10⁴ · 1 ≤ k ≤ m * n

From brute force to the pattern: Generating all m · n products and sorting is O(mn log(mn)). Counting entries ≤ x row by row costs O(m), and the count grows with x, so binary search over values is O(m log(mn)).

Spot it: The table has up to 9·10⁸ cells, far too many to list. But "how many cells are ≤ x?" is quick to count, and that count only grows as x grows. Binary search on the answer value.

Approach:

1. Answer range: [1, m·n].
2. count_at_most(x): row i has min(x // i, n) values ≤ x. Sum over all rows.
3. Find the first x with count_at_most(x) ≥ k: if true, set high = middle; else low = middle + 1.
4. That first x is always a real table value, because the count only changes at table values.

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        # Helper: how many cells of the m x n table hold a number <= value?
        def count_at_most(value):
            count = 0
            for row in range(1, m + 1):
                # Row `row` holds row*1, row*2, ..., row*n.
                # value // row of them are <= value, but never more than n.
                in_this_row = value // row
                if in_this_row > n:
                    in_this_row = n
                count = count + in_this_row
            return count

        # The answer is a table value, so it lies between 1 and m * n.
        low = 1
        high = m * n

        while low < high:
            middle = (low + high) // 2

            if count_at_most(middle) >= k:
                # At least k numbers are <= middle: answer is middle or smaller.
                high = middle
            else:
                # Fewer than k: the answer must be bigger.
                low = middle + 1

        # low is the smallest value with at least k table numbers <= it.
        return low

What the code is doing, line by line:

1. count_at_most(value) walks the rows 1 to m. Row row is row, 2·row, 3·row, …, n·row, so exactly value // row of them are ≤ value, capped at n because the row only has n cells. Adding these up gives how many table cells are ≤ value.
2. low = 1, high = m * n: the smallest and largest numbers in the table, so the answer is surely in between.
3. Inside the loop we try middle. If at least k cells are ≤ middle, the k-th smallest is middle or smaller, so high = middle (keep it).
4. Otherwise fewer than k cells are ≤ middle, so the k-th smallest is bigger: low = middle + 1.
5. When low == high we have the first value whose count reaches k. That value is always a real table number, because the count only increases at table numbers.

Dry run on the example m = 3, n = 3, k = 5 (table values 1, 2, 2, 3, 3, 4, 6, 6, 9):

Now low == high == 3, so the answer is 3.

Edge cases to test:

• k = 1 → 1.
• k = m · n → m · n.
• Duplicated products (e.g. 6 appears as 2·3 and 3·2).

Complexity: O(m log(m·n)) time, O(1) space.

Problem: Versions 1..n were released in order and every version after a bad one is also bad. Using the API isBadVersion(v), find the first bad version while calling the API as few times as possible.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ bad ≤ n ≤ 2³¹ - 1

From brute force to the pattern: Calling the API on every version is O(n) calls. The condition is monotonic, so binary search needs only O(log n) API calls.

Spot it: The answers look like False False … False True True … True, a monotonic condition. Finding the first True is the lower-bound form of binary search.

Approach:

1. lo = 1, hi = n. The first bad version is always inside [lo, hi].
2. While lo < hi: check mid.
3. If mid is bad, it might be the first one, so keep it: hi = mid.
4. If mid is good, the first bad is strictly after it: lo = mid + 1.
5. When lo == hi, that is the answer.

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        lo = 1
        hi = n
        # invariant: the first bad version is inside [lo, hi]
        while lo < hi:
            mid = (lo + hi) // 2
            if isBadVersion(mid):
                hi = mid        # mid is bad: it may be the first, keep it
            else:
                lo = mid + 1    # mid is good: the first bad is after it
        return lo

What the code is doing, line by line:

1. lo = 1, hi = n: versions are numbered from 1.
2. while lo < hi: stop when one candidate is left. (Not <=, because hi = mid could then loop forever.)
3. if isBadVersion(mid): hi = mid: a bad mid stays in the window; it may be the first.
4. else: lo = mid + 1: a good mid and everything before it are ruled out.
5. return lo: lo == hi, the first bad version.

Dry run on the example:

n = 5, first bad version 4 (LeetCode Example 1). Returns 4.

Edge cases to test:

• The first version is bad.
• Only the last version is bad.
• n = 1.

Complexity: O(log n) API calls and time, O(1) space.

Problem: Return True if num is a perfect square (some integer squared), without using a square-root function.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ num ≤ 2³¹ - 1

From brute force to the pattern: Trying x = 1, 2, 3, … until x² reaches num is O(√num). Binary search over candidate roots is O(log num) without any square-root function.

Spot it: x * x grows as x grows, so the candidate roots 1..num are "sorted" by their squares. Binary-search for an x with x * x == num.

Approach:

1. lo = 1, hi = num.
2. While lo ≤ hi: mid, square = mid * mid.
3. Equal → True. Too small → lo = mid + 1. Too big → hi = mid − 1.
4. If the window empties, no integer root exists: False.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        lo = 1
        hi = num
        while lo <= hi:
            mid = (lo + hi) // 2
            square = mid * mid
            if square == num:
                return True
            if square < num:
                lo = mid + 1     # the root (if any) is bigger than mid
            else:
                hi = mid - 1     # the root (if any) is smaller than mid
        return False

What the code is doing, line by line:

1. lo = 1, hi = num: the root of num is somewhere in 1..num.
2. square = mid * mid: squares increase with mid, which is what makes binary search valid.
3. if square == num: return True: found an exact root.
4. if square < num: lo = mid + 1, else hi = mid - 1: discard the half that can't contain the root.
5. return False: the window closed, so num lies strictly between two consecutive squares.

Dry run on the example:

num = 16 (LeetCode Example 1). Returns True.

Edge cases to test:

• num = 1 → True.
• Large non-squares like 2147483647.
• Numbers just above a square, e.g. 17.

Complexity: O(log num) time, O(1) space.

Problem: nums is sorted ascending. Return the index of target, or -1 if it isn't there, in O(log n) time.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 10⁴ · -10⁴ < nums[i], target < 10⁴ · All the integers in nums are unique. · nums is sorted in ascending order.

From brute force to the pattern: A linear scan is O(n). Each comparison with the middle element discards half the remaining candidates: O(log n).

Spot it: Sorted array + "find" + O(log n) → classic binary search on a closed window [lo, hi].

Approach:

1. lo = 0, hi = n − 1: the target, if present, is somewhere in nums[lo..hi].
2. While lo ≤ hi: look at the middle mid.
3. If nums[mid] == target, return mid. If it's smaller, the target must be to the right: lo = mid + 1. If larger: hi = mid − 1.
4. If the window becomes empty, the target is not present: return -1.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo = 0
        hi = len(nums) - 1
        # the answer, if it exists, is always inside nums[lo..hi]
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                # everything at or left of mid is too small
                lo = mid + 1
            else:
                # everything at or right of mid is too big
                hi = mid - 1
        return -1

What the code is doing, line by line:

1. lo, hi: both ends are included in the search window.
2. while lo <= hi: the window is non-empty while lo ≤ hi.
3. mid = (lo + hi) // 2: the middle index (// rounds down).
4. if nums[mid] == target: return mid: found it.
5. if nums[mid] < target: lo = mid + 1: mid and everything left of it are too small, so discard that half (including mid).
6. else: hi = mid - 1: mid and everything right of it are too big.
7. return -1: the window emptied without a match.

Dry run on the example:

nums = [-1, 0, 3, 5, 9, 12], target = 9 (LeetCode Example 1). Returns 4.

Edge cases to test:

• A single element.
• The target missing.
• The target at index 0 or at the end.

Complexity: O(log n) time, O(1) space.

Problem: A sorted array with duplicates was rotated. Return whether target is in it.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 5000 · -10⁴ ≤ nums[i] ≤ 10⁴ · nums is guaranteed to be rotated at some pivot. · -10⁴ ≤ target ≤ 10⁴

From brute force to the pattern: A linear scan is O(n). Binary search keeps halving whenever one side is clearly sorted, and only falls back to one-step shrinking when duplicates hide the structure.

Spot it: Same as Search in Rotated Sorted Array: one half around mid is sorted, so check whether the target lies inside it. Duplicates add one ambiguous case, nums[lo] == nums[mid], where you can't tell which half is sorted; then just move lo forward by one.

Why not another pattern? A linear scan is O(n), which is also the worst case here (e.g. [1, 1, 1, 1, 0, 1, 1]), but binary search is usually much faster.

Approach:

1. Closed window lo..hi; return True if nums[mid] == target.
2. If nums[lo] == nums[mid], the sorted half is unknown: lo += 1 and continue.
3. If nums[lo] < nums[mid], the left half is sorted: search it if nums[lo] ≤ target < nums[mid], else the right.
4. Otherwise the right half is sorted: search it if nums[mid] < target ≤ nums[hi], else the left.

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        lo = 0
        hi = len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return True
            if nums[lo] == nums[mid]:
                lo = lo + 1  # duplicates hide which half is sorted: drop one element
            elif nums[lo] < nums[mid]:
                # the left half nums[lo..mid] is sorted
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                # the right half nums[mid..hi] is sorted
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return False

What the code is doing, line by line:

1. The structure is LeetCode 33's: find the sorted half, range-check the target, discard half.
2. nums[lo] == nums[mid]: e.g. [1, 3, 1, 1, 1]; we can't tell where the drop is, but nums[lo] isn't the target (it equals nums[mid]), so it's safe to discard it.
3. This is why the worst case degrades to O(n) when there are many duplicates.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All elements equal.
• Duplicates on both sides of the rotation point, e.g. [1, 0, 1, 1, 1].
• No rotation.

Complexity: O(log n) on average, O(n) in the worst case (many duplicates); O(1) space.

Problem: Each row and each column of matrix is sorted ascending. Return whether target is in it.

Solve it on LeetCode ↗

Constraints: m == matrix.length · n == matrix[i].length · 1 ≤ n, m ≤ 300 · -10⁹ ≤ matrix[i][j] ≤ 10⁹ · All the integers in each row are sorted in ascending order. · All the integers in each column are sorted in ascending order. · -10⁹ ≤ target ≤ 10⁹

From brute force to the pattern: Scanning all cells is O(m · n); binary search per row is O(m log n). The staircase walk is O(m + n).

Spot it: Start at the top-right corner: moving left decreases the value, moving down increases it. Each comparison eliminates a whole row or column, a binary-search-like elimination in 2-D.

Why not another pattern? Binary-searching every row is O(m log n). Treating the matrix as one sorted list (LeetCode 74) doesn't work: rows aren't continuations of each other.

Approach:

1. Start at (0, n − 1).
2. Too big → move left (this column below is even bigger). Too small → move down (this row to the left is even smaller).
3. Return True on a match, False when you leave the matrix.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        r = 0
        c = len(matrix[0]) - 1  # top-right corner
        while r < len(matrix) and c >= 0:
            value = matrix[r][c]
            if value == target:
                return True
            if value > target:
                c = c - 1  # everything below in this column is even larger
            else:
                r = r + 1  # everything to the left in this row is even smaller
        return False

What the code is doing, line by line:

1. At the top-right, values to the left are smaller and values below are larger.
2. If the value is too big, the whole column (from here down) is too big: discard it.
3. If it's too small, the whole row (from here left) is too small: discard it.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Target smaller than everything or larger than everything.
• A single row or column.
• Target in a corner.

Complexity: O(m + n) time, O(1) space.

Problem: Return the n-th digit of the infinite sequence 123456789101112….

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 2³¹ - 1

From brute force to the pattern: Concatenating numbers until n digits is O(n) with n up to 2·10⁹. Skipping blocks needs at most 10 steps.

Spot it: Numbers with d digits form a block of 9 · 10^(d−1) numbers and d · 9 · 10^(d−1) digits. Skipping whole blocks finds the digit length, then integer division finds the exact number and digit, a search over block boundaries (like a coarse binary search).

Why not another pattern? Building the string up to n characters needs O(n) time and memory, with n up to 2³¹.

Approach:

1. digits = 1, count = 9, start = 1.
2. While n > digits · count: subtract that block and move to the next (digits += 1, count *= 10, start *= 10).
3. The number is start + (n − 1) // digits; the digit index inside it is (n − 1) % digits.

class Solution:
    def findNthDigit(self, n: int) -> int:
        digits = 1  # numbers in this block have this many digits
        count = 9  # how many numbers are in the block
        start = 1  # the first number of the block
        while n > digits * count:
            n = n - digits * count  # skip the whole block
            digits = digits + 1
            count = count * 10
            start = start * 10
        number = start + (n - 1) // digits  # the number containing the n-th digit
        return int(str(number)[(n - 1) % digits])  # the digit inside that number

What the code is doing, line by line:

1. Block d holds 9·10^(d−1) numbers of d digits each.
2. The while subtracts complete blocks until n falls inside the current one.
3. Inside the block, every number takes digits characters, so (n − 1) // digits counts whole numbers to skip.
4. (n − 1) % digits is the position of the digit within that number.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n ≤ 9 → n itself.
• The boundary between blocks, e.g. n = 10 → 1 (the 1 of 10), n = 11 → 0.
• Very large n near 2³¹.

Complexity: O(log n) time (one step per digit length), O(1) space.

Problem: Every element appears exactly twice except one. The array is sorted. Find the single element in O(log n).

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 0 ≤ nums[i] ≤ 10⁵

From brute force to the pattern: XOR-ing everything or scanning pairs is O(n). The parity of pair positions gives a monotone condition for binary search.

Spot it: A yes/no condition flips at the answer: "does the pair start at an even index?" is true before the single element and false after it. Binary search for the flip.

Why not another pattern? XOR of everything is O(n), which doesn't meet the O(log n) requirement.

Approach:

1. Search over even indices only: mid is adjusted to be even.
2. If nums[mid] == nums[mid + 1], the pairs are still aligned: the single element is to the right (lo = mid + 2).
3. Otherwise it's at mid or to the left (hi = mid).

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        lo = 0
        hi = len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if mid % 2 == 1:
                mid = mid - 1  # look at the start of a would-be pair (even index)
            if nums[mid] == nums[mid + 1]:
                lo = mid + 2  # pairs still aligned: the single one is further right
            else:
                hi = mid  # alignment broken at or before mid
        return nums[lo]

What the code is doing, line by line:

1. Before the single element, each pair occupies indices (2k, 2k + 1).
2. Moving mid to an even index lets us check whether the pair starting there is intact.
3. Intact → everything up to mid + 1 is paired: search right of it. Broken → the single element is at mid or before.
4. lo and hi stay even, and they meet at the single element.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• The single element first or last.
• Length 1.
• Negative numbers.

Complexity: O(log n) time, O(1) space.

Problem: arr strictly increases and then strictly decreases. Return the index of the peak in O(log n).

Solve it on LeetCode ↗

Constraints: 3 ≤ arr.length ≤ 10⁵ · 0 ≤ arr[i] ≤ 10⁶ · arr is guaranteed to be a mountain array.

From brute force to the pattern: Scanning for the first descent is O(n). The slope at mid tells you which half holds the peak: O(log n).

Spot it: "Is arr[mid] < arr[mid + 1]?" is true before the peak and false from the peak on: binary search for the first false.

Why not another pattern? A linear scan for the first decrease is O(n).

Approach:

1. lo = 0, hi = n − 1.
2. If arr[mid] < arr[mid + 1], we're going uphill: lo = mid + 1.
3. Otherwise the peak is at mid or to the left: hi = mid.

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        lo = 0
        hi = len(arr) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if arr[mid] < arr[mid + 1]:
                lo = mid + 1  # still climbing: the peak is to the right
            else:
                hi = mid  # descending: the peak is here or to the left
        return lo

What the code is doing, line by line:

1. Comparing mid with its right neighbour tells you which side of the peak you're on.
2. lo < hi guarantees mid + 1 exists.
3. When the window shrinks to one index, that's the peak.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Peak at index 1 (the smallest mountain).
• Peak at the second-to-last index.
• Length 3.

Complexity: O(log n) time, O(1) space.

Problem: Implement an array with set(index, val), snap() (returns a snapshot id) and get(index, snap_id) (the value at that index when the snapshot was taken).

Solve it on LeetCode ↗

Constraints: 1 ≤ length ≤ 5 * 10⁴ · 0 ≤ index < length · 0 ≤ val ≤ 10⁹ · 0 ≤ snap_id < (the total number of times we call snap()) · At most 5 * 10⁴ calls will be made to set, snap, and get.

From brute force to the pattern: Copying the array per snapshot is O(n) time and memory each time. Storing only changes and binary-searching them makes everything O(1) or O(log).

Spot it: Copying the whole array on every snap is too expensive. Store only changes: per index, a list of (snap_id, value) appended in increasing snap order. get is then "the last change at or before snap_id": a binary search, like Time Based Key-Value Store.

Why not another pattern? Copying the array per snapshot is O(n) per snap and O(n · snaps) memory.

Approach:

1. history[i] starts as [(-1, 0)] (value 0 before any snapshot).
2. set: if the last change at i has the current snap id, overwrite it; else append (snap_id, val).
3. snap: return the current id and increment it.
4. get: binary-search history[index] for the last entry with id ≤ snap_id.

from bisect import bisect_right

class SnapshotArray:
    def __init__(self, length: int):
        self.snap_id = 0
        self.history = [[(-1, 0)] for _ in range(length)]  # per index: (snap id, value) changes

    def set(self, index: int, val: int) -> None:
        changes = self.history[index]
        if changes[-1][0] == self.snap_id:
            changes[-1] = (self.snap_id, val)  # several sets before one snap: keep the latest
        else:
            changes.append((self.snap_id, val))

    def snap(self) -> int:
        self.snap_id = self.snap_id + 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        changes = self.history[index]
        pos = bisect_right(changes, (snap_id, float("inf"))) - 1  # last change with id <= snap_id
        return changes[pos][1]

What the code is doing, line by line:

1. Each index keeps only its changes; untouched indices cost one entry.
2. Changes are appended with non-decreasing snap ids, so each list is sorted.
3. A set before the next snap overwrites the pending change instead of adding another.
4. bisect_right(changes, (snap_id, inf)) finds the position after every entry with id ≤ snap_id; minus one gives the last such entry.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• get on an index never set → 0.
• Several sets between two snaps.
• Snaps with no changes in between.

Complexity: set/snap O(1), get O(log s); memory proportional to the number of set calls.

Problem: Flower i blooms on day bloomDay[i]. A bouquet needs k adjacent bloomed flowers. Return the earliest day to make m bouquets, or −1.

Solve it on LeetCode ↗

Constraints: bloomDay.length == n · 1 ≤ n ≤ 10⁵ · 1 ≤ bloomDay[i] ≤ 10⁹ · 1 ≤ m ≤ 10⁶ · 1 ≤ k ≤ n

From brute force to the pattern: Checking every day is O(n · max day) with days up to 10⁹. Binary search needs about 30 checks.

Spot it: If m bouquets are possible by day d, they're possible on every later day: a monotone yes/no condition, so binary search on the day.

Why not another pattern? Simulating every day from 1 to max(bloomDay) is O(n · max).

Approach:

1. If m · k > n, return −1.
2. Binary-search day in [min(bloomDay), max(bloomDay)].
3. Check a day by scanning: count consecutive bloomed flowers; each time the run reaches k, make a bouquet and reset.

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1  # not enough flowers in total

        def bouquets_by(day):
            made = 0
            run = 0  # consecutive bloomed flowers
            for d in bloomDay:
                if d <= day:
                    run = run + 1
                    if run == k:
                        made = made + 1  # use these k flowers
                        run = 0
                else:
                    run = 0  # a gap breaks adjacency
            return made

        lo = min(bloomDay)
        hi = max(bloomDay)
        while lo < hi:
            mid = (lo + hi) // 2
            if bouquets_by(mid) >= m:
                hi = mid  # mid works: try earlier
            else:
                lo = mid + 1
        return lo

What the code is doing, line by line:

1. m * k > n: impossible no matter how long you wait.
2. bouquets_by(day) greedily forms bouquets from left to right; taking the first k adjacent flowers is optimal.
3. The count only grows with the day, so the smallest day with enough bouquets is found by binary search.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Not enough flowers → −1.
• k = 1 (adjacency doesn't matter).
• All flowers bloom on the same day.

Complexity: O(n log(max day)) time, O(1) space.

Problem: Place m balls in baskets at the given positions to maximise the minimum distance between any two balls.

Solve it on LeetCode ↗

Constraints: n == position.length · 2 ≤ n ≤ 10⁵ · 1 ≤ position[i] ≤ 10⁹ · All integers in position are distinct. · 2 ≤ m ≤ position.length

From brute force to the pattern: Trying combinations of m baskets is exponential. Binary search on the gap with an O(n) greedy check is O(n log range).

Spot it: "Maximise the minimum" + "if gap g is achievable, so is any smaller gap" → binary search on the answer with a greedy check.

Why not another pattern? Trying all placements is combinatorial. DP over positions is O(n² m).

Approach:

1. Sort positions.
2. Check a gap g: place the first ball at the first basket, then each next ball at the first basket at least g further. Success if m balls fit.
3. Binary-search the largest feasible g between 1 and max − min.

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position = sorted(position)

        def fits(gap):
            placed = 1
            last = position[0]  # first ball in the first basket
            for p in position[1:]:
                if p - last >= gap:
                    placed = placed + 1  # far enough: place the next ball here
                    last = p
            return placed >= m

        lo = 1
        hi = position[-1] - position[0]
        while lo < hi:
            mid = (lo + hi + 1) // 2  # round up so the loop always moves
            if fits(mid):
                lo = mid  # mid works: try bigger
            else:
                hi = mid - 1
        return lo

What the code is doing, line by line:

1. Greedy placement (as early as possible) leaves the most room for later balls, so if any placement works for gap, this one does.
2. Feasibility is monotonic: a smaller gap is always at least as easy.
3. Searching for the largest feasible value uses mid = (lo + hi + 1) // 2 and lo = mid to avoid an infinite loop.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• m = 2 → the distance between the extremes.
• m = n → the smallest adjacent gap.
• Unsorted input.

Complexity: O(n log n + n log(range)) time, O(n) space.

Problem: With at most maxOperations splits (divide a bag into two positive bags), minimise the largest bag size.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ maxOperations, nums[i] ≤ 10⁹

From brute force to the pattern: Simulating splits greedily is both slow and wrong; binary search on the answer with an O(n) count is exact.

Spot it: "Minimise the maximum" with a monotone check ("can every bag end up ≤ p?") → binary search on p.

Why not another pattern? Greedily splitting the largest bag in half doesn't give optimal results (splitting 9 into 3+3+3 beats 5+4).

Approach:

1. For a candidate penalty p, bag x needs (x − 1) // p operations to break into pieces of size ≤ p.
2. p is feasible if the total operations ≤ maxOperations.
3. Binary-search the smallest feasible p in 1..max(nums).

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        lo = 1
        hi = max(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            ops = sum((x - 1) // mid for x in nums)  # splits needed so every bag is <= mid
            if ops <= maxOperations:
                hi = mid  # feasible: try a smaller penalty
            else:
                lo = mid + 1
        return lo

What the code is doing, line by line:

1. Cutting a bag of x into pieces of size ≤ p needs ceil(x / p) pieces, i.e. ceil(x / p) − 1 = (x − 1) // p splits.
2. Fewer operations are needed for larger p, so feasibility is monotonic.
3. The smallest feasible p is the answer.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• maxOperations = 0 → max(nums).
• Enough operations to make every bag size 1.
• One huge bag.

Complexity: O(n log(max)) time, O(1) space.

Problem: Bus i takes time[i] per trip and buses run in parallel. Return the minimum time for all buses together to finish at least totalTrips trips.

Solve it on LeetCode ↗

Constraints: 1 ≤ time.length ≤ 10⁵ · 1 ≤ time[i], totalTrips ≤ 10⁷

From brute force to the pattern: Stepping time forward one unit at a time can take 10¹⁴ steps; binary search needs about 47 checks.

Spot it: Trips completed only grow with time: binary search on time, checking Σ t // time[i] ≥ totalTrips.

Why not another pattern? Simulating time unit by unit takes up to 10¹⁴ steps. A heap of next finish times needs totalTrips (up to 10⁷) pops.

Approach:

1. lo = 1, hi = min(time) · totalTrips (the fastest bus alone gets there).
2. Check t: sum(t // x for x in time) ≥ totalTrips.
3. Binary-search the smallest feasible t.

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        lo = 1
        hi = min(time) * totalTrips  # the fastest bus alone finishes by then
        while lo < hi:
            mid = (lo + hi) // 2
            trips = sum(mid // t for t in time)  # trips every bus completes by time mid
            if trips >= totalTrips:
                hi = mid  # enough: try earlier
            else:
                lo = mid + 1
        return lo

What the code is doing, line by line:

1. Each bus completes mid // t whole trips by time mid.
2. The upper bound is safe: the fastest bus alone completes totalTrips trips in min(time) · totalTrips.
3. The smallest time whose trip count reaches the goal is found with the standard lower-bound binary search.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• One bus.
• totalTrips = 1 → min(time).
• Very large answers (beyond 32-bit).

Complexity: O(n log(min(time) · totalTrips)) time, O(1) space.

Problem: Piles can be split but not merged. Give each of k children one pile of the same size x; return the largest x (0 if impossible).

Solve it on LeetCode ↗

Constraints: 1 ≤ candies.length ≤ 10⁵ · 1 ≤ candies[i] ≤ 10⁷ · 1 ≤ k ≤ 10¹²

From brute force to the pattern: Testing every x from the top is O(n · max). Binary search tests about 24 values.

Spot it: If every child can get x, every child can get less: binary search the largest x with Σ c // x ≥ k.

Why not another pattern? Trying each x from max(candies) down is up to 10⁷ checks of O(n).

Approach:

1. lo = 0 (always feasible), hi = max(candies).
2. Check x: sum(c // x) ≥ k.
3. Binary-search the largest feasible x (round mid up).

class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        lo = 0  # giving 0 candies always works
        hi = max(candies)
        while lo < hi:
            mid = (lo + hi + 1) // 2  # round up: mid >= 1 and the loop always moves
            children = sum(c // mid for c in candies)  # piles of size mid we can cut
            if children >= k:
                lo = mid  # feasible: try bigger piles
            else:
                hi = mid - 1
        return lo

What the code is doing, line by line:

1. A pile of c candies yields c // x sub-piles of size x; leftovers are wasted.
2. Feasibility is monotone in x, so search for the last feasible value.
3. lo = 0 means the answer is 0 when even x = 1 fails (fewer total candies than children).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Total candies < k → 0.
• k = 1 → max(candies).
• Very large k (up to 10¹²).

Complexity: O(n log(max)) time, O(1) space.

Problem: A frog goes from the first stone to the last and back, landing on each stone at most once. Minimise the longest jump.

Solve it on LeetCode ↗

Constraints: 2 ≤ stones.length ≤ 10⁵ · 0 ≤ stones[i] ≤ 10⁹ · stones[0] == 0 · stones is sorted in a strictly increasing order.

From brute force to the pattern: Binary search on the cost with a greedy check is O(n log range); the alternating-route observation makes it O(n).

Spot it: It's a "minimise the maximum" problem, so binary search on the cost is the natural first idea. Looking at what the check does leads to a shortcut: the best route uses every other stone going out and the remaining stones coming back, so the cost is the largest gap between stones two apart.

Why not another pattern? A binary search on the cost works (check: can the frog go out and back skipping stones?), but the check itself proves the alternating route is always best, which gives an O(n) formula.

Key insight: Any route visits stones i and i + 2 on different trips only if stone i + 1 is on one of them, so some jump spans at least stones[i + 2] − stones[i]. Alternating stones achieves exactly that bound.

Approach:

1. Start with stones[1] − stones[0] (needed when there are only two stones).
2. Take the maximum of stones[i + 2] − stones[i] over all i.

class Solution:
    def maxJump(self, stones: List[int]) -> int:
        best = stones[1] - stones[0]  # two stones: jump there and back
        for i in range(len(stones) - 2):
            best = max(best, stones[i + 2] - stones[i])  # alternating route jumps over one stone
        return best

What the code is doing, line by line:

1. Going out on even-indexed stones and back on odd-indexed ones (or vice versa) uses every stone exactly once.
2. Every jump on that route spans two consecutive gaps, stones[i + 2] − stones[i].
3. No route can do better: stones i and i + 2 with i + 1 taken by the other trip force a jump at least that long.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Exactly two stones → their distance (both jumps).
• Three stones → stones[2] − stones[0].
• One huge gap dominates.

Complexity: O(n) time, O(1) space.

Problem: For each query index q in a circular array, return the minimum circular distance to another index with the same value, or −1.

Solve it on LeetCode ↗

Constraints: 1 ≤ queries.length ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁶ · 0 ≤ queries[i] < nums.length

From brute force to the pattern: Walking left and right from each query is O(n) per query. Grouping plus binary search answers each in O(log n).

Spot it: Group indices by value; each group is sorted. The nearest equal element of q is one of its two neighbours in its group, where the group also wraps around. Find q's place in its group by binary search.

Why not another pattern? Scanning outward from each query is O(n) per query, O(n · q) overall.

Approach:

1. where[value] = sorted list of indices holding that value.
2. For a query q: if its group has one index → −1.
3. Otherwise find q's position with binary search; check the previous and next index in the group (wrapping), using circular distance min(d, n − d).

from bisect import bisect_left
from collections import defaultdict

class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        n = len(nums)
        where = defaultdict(list)  # value -> its indices, in increasing order
        for i, x in enumerate(nums):
            where[x].append(i)
        answer = []
        for q in queries:
            group = where[nums[q]]
            if len(group) == 1:
                answer.append(-1)  # no other index has this value
                continue
            p = bisect_left(group, q)  # q's position inside its group
            best = n
            for other in (group[p - 1], group[(p + 1) % len(group)]):  # neighbours, wrapping around
                d = abs(other - q)
                best = min(best, d, n - d)  # circular distance
            answer.append(best)
        return answer

What the code is doing, line by line:

1. Indices are appended in increasing order, so each group is already sorted.
2. group[p − 1] with p = 0 is Python's last element: the wrap-around neighbour on the left comes for free.
3. (p + 1) % len(group) wraps the right neighbour to the first index.
4. The circular distance between i and j is min(|i − j|, n − |i − j|).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A value that appears once → −1.
• The closest copy is reached by wrapping around the end.
• Exactly two copies (both neighbours are the same index).

Complexity: O(n + q log n) time, O(n) space.

Problem: Count integers y in [l, r] that are perfect k-th powers (y = xᵏ for some integer x ≥ 0).

Solve it on LeetCode ↗

Constraints: 0 ≤ l ≤ r ≤ 10⁹ · 1 ≤ k ≤ 30

From brute force to the pattern: Checking every y in [l, r] is up to 10⁹ checks. Two binary searches take about 60 steps.

Spot it: Perfect powers 0ᵏ, 1ᵏ, 2ᵏ, … are increasing, so "how many are ≤ v" is the largest x with xᵏ ≤ v (plus one for 0): a binary search on x. A range count is the difference of two prefix counts.

Why not another pattern? Floating-point v ** (1/k) can be off by one for large values; integer binary search is exact.

Approach:

1. count(v) = number of x ≥ 0 with xᵏ ≤ v (0 when v < 0).
2. Binary-search the largest such x in [0, v]; count(v) = x + 1.
3. Answer: count(r) − count(l − 1).

class Solution:
    def countKthRoots(self, l: int, r: int, k: int) -> int:
        def count(v):  # how many x >= 0 have x**k <= v
            if v < 0:
                return 0
            lo = 0
            hi = v
            while lo < hi:
                mid = (lo + hi + 1) // 2
                if mid ** k <= v:
                    lo = mid  # mid fits: try bigger
                else:
                    hi = mid - 1
            return lo + 1  # x = 0, 1, ..., lo

        return count(r) - count(l - 1)

What the code is doing, line by line:

1. xᵏ increases with x, so the largest x with xᵏ ≤ v is a last-true binary search.
2. Python's big integers make mid ** k exact, so there are no rounding errors.
3. Perfect powers in [l, r] = those ≤ r minus those ≤ l − 1; count(−1) = 0 handles l = 0.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• l = 0 (0 is a perfect power).
• k = 1 → every integer counts.
• l = r that is or isn't a perfect power.

Complexity: O(k · log r) time (each power is O(k) multiplications at most), O(1) space.

Problem: Find the minimum of a rotated sorted array that may contain duplicates.

Solve it on LeetCode ↗

Constraints: n == nums.length · 1 ≤ n ≤ 5000 · -5000 ≤ nums[i] ≤ 5000 · nums is sorted and rotated between 1 and n times.

From brute force to the pattern: A linear min is O(n). Binary search halves the window in every unambiguous case.

Spot it: Like LeetCode 153: compare nums[mid] with nums[hi] to see which side holds the drop. With duplicates, equality is ambiguous, but dropping nums[hi] is safe because nums[mid] has the same value.

Why not another pattern? min(nums) is O(n); that's also the worst case here, but binary search is O(log n) when duplicates don't interfere.

Approach:

1. lo = 0, hi = n − 1; while lo < hi:
2. If nums[mid] > nums[hi], the minimum is right of mid: lo = mid + 1.
3. If nums[mid] < nums[hi], the minimum is at mid or left: hi = mid.
4. If equal, hi −= 1 (the value at hi still exists at mid).

class Solution:
    def findMin(self, nums: List[int]) -> int:
        lo = 0
        hi = len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > nums[hi]:
                lo = mid + 1  # the drop is to the right of mid
            elif nums[mid] < nums[hi]:
                hi = mid  # mid..hi is sorted, so the minimum is at mid or to its left
            else:
                hi = hi - 1  # equal: drop hi, its value survives at mid
        return nums[lo]

What the code is doing, line by line:

1. nums[mid] > nums[hi]: there's a drop between them, so the minimum is after mid.
2. nums[mid] < nums[hi]: mid..hi is increasing, so nothing right of mid is smaller than nums[mid].
3. Equal values: we can't decide, but removing hi never loses the minimum's value.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All equal.
• [2, 2, 2, 0, 1].
• No rotation.

Complexity: O(log n) on average, O(n) worst case; O(1) space.

Problem: Envelope a fits in b if both its width and height are strictly smaller. Return the maximum number of nested envelopes.

Solve it on LeetCode ↗

Constraints: 1 ≤ envelopes.length ≤ 10⁵ · envelopes[i].length == 2 · 1 ≤ wi, hi ≤ 10⁵

From brute force to the pattern: The DP best[i] = 1 + max(best[j]) over smaller envelopes is O(n²). With the right sort it becomes LIS, solvable in O(n log n) with binary search.

Spot it: A 2-D chain problem. Sorting by width turns it into a Longest Increasing Subsequence on heights. LIS in O(n log n) keeps the smallest tail for each length and places each height with binary search.

Why not another pattern? The O(n²) LIS DP times out for n = 10⁵. Sorting heights descending for equal widths is the trick that prevents two equal-width envelopes from chaining.

Approach:

1. Sort by width ascending and, for equal widths, height descending.
2. Run LIS on the heights: tails[k] = smallest possible last height of an increasing chain of length k + 1.
3. For each height, binary-search the first tail ≥ it and replace it (or append if none).
4. The answer is len(tails).

from bisect import bisect_left

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        # width ascending; equal widths by height descending so they can't nest in each other
        envelopes = sorted(envelopes, key=lambda e: (e[0], -e[1]))
        tails = []  # tails[k] = smallest last height of an increasing chain of length k+1
        for _, h in envelopes:
            pos = bisect_left(tails, h)  # first tail >= h
            if pos == len(tails):
                tails.append(h)  # h extends the longest chain
            else:
                tails[pos] = h  # a chain of this length can now end lower
        return len(tails)

What the code is doing, line by line:

1. After sorting by width, any increasing run of heights is a valid nesting, except for equal widths, which the descending tie-break blocks.
2. tails stays sorted, so bisect_left finds where h belongs in O(log n).
3. Replacing a tail with a smaller height keeps more room for future envelopes; appending extends the best chain.
4. len(tails) is the length of the longest increasing subsequence.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Equal widths (can't nest).
• Equal heights (can't nest).
• A single envelope → 1.

Complexity: O(n log n) time, O(n) space.

Problem: A positive integer is magical if it's divisible by a or b. Return the n-th magical number modulo 10⁹ + 7.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10⁹ · 2 ≤ a, b ≤ 4 * 10⁴

From brute force to the pattern: Listing magical numbers in order is O(n) with n up to 10⁹. Counting with inclusion–exclusion makes each guess O(1), so binary search is enough.

Spot it: "The n-th smallest value" where counting values ≤ x is easy: binary search on x. The count of magical numbers ≤ x is x // a + x // b − x // lcm(a, b) (numbers divisible by both are counted twice).

Why not another pattern? Generating magical numbers one by one (two pointers on multiples of a and b) is O(n), with n up to 10⁹.

Approach:

1. lcm = a · b // gcd(a, b).
2. Binary-search the smallest x with count(x) ≥ n, between 1 and n · min(a, b).
3. Return x % (10⁹ + 7).

from math import gcd

class Solution:
    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
        lcm = a * b // gcd(a, b)
        lo = 1
        hi = n * min(a, b)  # the n-th multiple of the smaller number is always magical
        while lo < hi:
            mid = (lo + hi) // 2
            count = mid // a + mid // b - mid // lcm  # magical numbers <= mid
            if count >= n:
                hi = mid  # mid is large enough
            else:
                lo = mid + 1
        return lo % (10 ** 9 + 7)

What the code is doing, line by line:

1. Multiples of both a and b are multiples of lcm(a, b); subtracting them fixes the double count.
2. count(x) never decreases as x grows, so binary search finds the smallest x with at least n magical numbers below it, which is the n-th one.
3. n · min(a, b) is a safe upper bound.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• a == b.
• a divides b (the LCM is b).
• Large n (take the result modulo 10⁹ + 7).

Complexity: O(log(n · min(a, b))) time, O(1) space.

Problem: Return any longest substring of s that occurs at least twice (occurrences may overlap), or "".

Solve it on LeetCode ↗

Constraints: 2 ≤ s.length ≤ 3 * 10⁴ · s consists of lowercase English letters.

From brute force to the pattern: Checking every substring against every other is O(n³). Binary search over length with an O(n) rolling-hash check is O(n log n).

Spot it: If a repeated substring of length L exists, its prefixes give a repeat of every shorter length: monotone in L, so binary search the length. Checking one length is "is any window of size L seen twice?" — a rolling hash over all windows.

Why not another pattern? Comparing all pairs of substrings is O(n³). A suffix array solves it too, but binary search + rolling hash is far easier to write in an interview.

Approach:

1. Binary-search L in 1..n − 1.
2. Check L: compute the hash of every window of length L in O(n) with a rolling hash; if a hash repeats (and the strings really match), return the start.
3. Keep the start of the last successful L and return that substring.

class Solution:
    def longestDupSubstring(self, s: str) -> str:
        n = len(s)
        MOD = (1 << 61) - 1
        BASE = 131

        def repeat_start(length):
            power = pow(BASE, length, MOD)  # weight of the character leaving the window
            h = 0
            seen = {}  # hash -> start positions with that hash
            for i, ch in enumerate(s):
                h = (h * BASE + ord(ch)) % MOD
                if i >= length:
                    h = (h - ord(s[i - length]) * power) % MOD  # drop the leftmost character
                if i >= length - 1:
                    start = i - length + 1
                    for other in seen.get(h, []):
                        if s[other:other + length] == s[start:start + length]:
                            return start  # same hash and same text: a real repeat
                    seen.setdefault(h, []).append(start)
            return -1

        lo = 1
        hi = n - 1
        best_start = 0
        best_len = 0
        while lo <= hi:
            mid = (lo + hi) // 2
            start = repeat_start(mid)
            if start >= 0:
                best_start = start  # a repeat of length mid exists: try longer
                best_len = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return s[best_start:best_start + best_len]

What the code is doing, line by line:

1. The rolling hash treats each window as a number in base 131 modulo a large prime: add the new character, subtract the one leaving.
2. power = BASE^length is the weight of the leftmost character, so removing it is h − ord(c) · power.
3. Equal hashes are confirmed by comparing the text, so a hash collision can never produce a wrong answer.
4. Binary search keeps the last length that had a repeat; s[best_start:best_start + best_len] is the answer (empty if none).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No repeated character → "".
• Overlapping occurrences ("banana" → "ana").
• All characters the same ("aaaa" → "aaa").

Complexity: O(n log n) expected time, O(n) space.

Problem: Through the MountainArray interface (get(k), length()), find the minimum index whose value is target, or −1, using at most 100 get calls.

Solve it on LeetCode ↗

Constraints: 3 ≤ mountainArr.length() ≤ 10⁴ · 0 ≤ target ≤ 10⁹ · 0 ≤ mountainArr.get(index) ≤ 10⁹

From brute force to the pattern: Scanning with get is up to 10⁴ calls. Three binary searches use about 50.

Spot it: A mountain is two sorted runs glued at the peak. Find the peak by binary search on the slope, then binary-search the ascending side (its match has the smaller index), and only if that fails, the descending side.

Why not another pattern? A linear scan uses up to 10⁴ calls, far over the 100-call limit.

Approach:

1. Binary-search the peak: if get(mid) < get(mid + 1), go right; else left.
2. Binary-search 0..peak (ascending) for target; return the index if found.
3. Binary-search peak + 1..n − 1 (descending, so the comparisons flip).

class Solution:
    def findInMountainArray(self, target: int, mountainArr: "MountainArray") -> int:
        n = mountainArr.length()
        lo = 0
        hi = n - 1
        while lo < hi:  # 1) find the peak
            mid = (lo + hi) // 2
            if mountainArr.get(mid) < mountainArr.get(mid + 1):
                lo = mid + 1
            else:
                hi = mid
        peak = lo
        lo = 0
        hi = peak
        while lo <= hi:  # 2) the ascending side (smaller indices first)
            mid = (lo + hi) // 2
            value = mountainArr.get(mid)
            if value == target:
                return mid
            if value < target:
                lo = mid + 1
            else:
                hi = mid - 1
        lo = peak + 1
        hi = n - 1
        while lo <= hi:  # 3) the descending side (comparisons reversed)
            mid = (lo + hi) // 2
            value = mountainArr.get(mid)
            if value == target:
                return mid
            if value > target:
                lo = mid + 1
            else:
                hi = mid - 1
        return -1

What the code is doing, line by line:

1. The first loop is Peak Index in a Mountain Array: about 2·log₂ n calls.
2. The ascending side is searched first because the problem wants the minimum index.
3. On the descending side, larger values are to the left, so the direction of each move is reversed.
4. Total calls are about 4·log₂(10⁴) ≈ 56, under the limit.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• The target equals the peak.
• The target appears on both sides (return the left one).
• The target is missing → −1.

Complexity: O(log n) time and API calls, O(1) space.

Problem: Jobs [start, end, profit] can't overlap (a job may start exactly when another ends). Return the maximum total profit.

Solve it on LeetCode ↗

Constraints: 1 ≤ startTime.length == endTime.length == profit.length ≤ 5 * 10⁴ · 1 ≤ startTime[i] < endTime[i] ≤ 10⁹ · 1 ≤ profit[i] ≤ 10⁴

From brute force to the pattern: Trying all subsets of jobs is O(2ⁿ); scanning backwards for compatible jobs is O(n²). Binary search makes each DP step O(log n).

Spot it: Weighted interval scheduling: sort by end time; for each job, either skip it or take it plus the best answer among jobs that end by its start. Finding that last compatible job is a binary search over end times.

Why not another pattern? Greedy by end time (unweighted scheduling) ignores profits. A DP that scans backwards for the compatible job is O(n²).

Approach:

1. Sort jobs by end time.
2. best[i] = max profit using the first i jobs (in end order); best[0] = 0.
3. For job i: binary-search k = number of jobs with end ≤ start_i. best[i + 1] = max(best[i], best[k] + profit_i).

from bisect import bisect_right

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        jobs = sorted(zip(endTime, startTime, profit))  # by end time
        ends = [e for e, _, _ in jobs]
        best = [0] * (len(jobs) + 1)  # best[i] = max profit using the first i jobs
        for i, (end, start, gain) in enumerate(jobs):
            k = bisect_right(ends, start)  # jobs 0..k-1 end no later than this one starts
            best[i + 1] = max(best[i], best[k] + gain)  # skip it, or take it after job k-1
        return best[-1]

What the code is doing, line by line:

1. Sorting by end time means every job compatible with job i comes before it.
2. bisect_right(ends, start) counts jobs ending at or before start (equal is allowed).
3. Either job i is skipped (best[i]) or taken on top of the best schedule among compatible jobs (best[k] + gain).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A job starting exactly when another ends (allowed).
• One very profitable long job vs many short ones.
• Identical intervals.

Complexity: O(n log n) time, O(n) space.

Problem: Split 2n numbers into two arrays of n each to minimise |sum1 − sum2|.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 15 · nums.length == 2 * n · -10⁷ ≤ nums[i] ≤ 10⁷

From brute force to the pattern: Trying all C(2n, n) splits is about 1.5·10⁸ for n = 15. Meet in the middle checks 2¹⁵ sums per side with binary search.

Spot it: 2n ≤ 30 makes C(30, 15) choices too many, but each half alone has only 2¹⁵ subsets. Pick k from the left half and n − k from the right: for each left sum, binary-search the right sums (of size n − k, sorted) for the one bringing the total closest to half.

Why not another pattern? Subset-sum DP over values fails: values go up to ±10⁷, and the exact count of n elements must also be tracked.

Approach:

1. Split into left and right (n each). For each, list the subset sums grouped by the number of elements chosen.
2. Choosing sum a (k elements) from the left and b (n − k elements) from the right gives a difference |total − 2(a + b)|.
3. For each a, binary-search the sorted sums of size n − k for b near (total − 2a) / 2; check the two neighbours.

from bisect import bisect_left

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n = len(nums) // 2
        total = sum(nums)

        def sums_by_size(half):
            groups = [[] for _ in range(n + 1)]
            for mask in range(1 << n):
                picked = [half[i] for i in range(n) if mask >> i & 1]
                groups[len(picked)].append(sum(picked))  # subset sum, grouped by how many were picked
            return groups

        left = sums_by_size(nums[:n])
        right = [sorted(g) for g in sums_by_size(nums[n:])]
        best = float("inf")
        for k in range(n + 1):
            candidates = right[n - k]  # the right half must supply the other n - k elements
            for a in left[k]:
                need = total - 2 * a  # minimise |need - 2b|
                idx = bisect_left(candidates, (need + 1) // 2)
                for j in (idx - 1, idx):
                    if 0 <= j < len(candidates):
                        best = min(best, abs(need - 2 * candidates[j]))
        return best

What the code is doing, line by line:

1. If the first array has sum s, the difference is |total − 2s|; the goal is s as close to total / 2 as possible.
2. sums_by_size enumerates every subset of one half (2ⁿ with n ≤ 15) and files its sum under its size.
3. With k elements from the left, exactly n − k must come from the right, so only right[n − k] is searched.
4. bisect_left at ceil(need / 2) lands between the two values of b closest to need / 2; checking both is enough.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Negative numbers.
• n = 1 (just |a − b|).
• A perfect split exists → 0.

Complexity: O(2ⁿ · n) time (enumerating, sorting and binary-searching), O(2ⁿ) space.

Problem: Points lie on the boundary of a side × side square. Choose k of them to maximise the minimum Manhattan distance between chosen points.

Solve it on LeetCode ↗

Constraints: 1 ≤ side ≤ 10⁹ · 4 ≤ points.length ≤ min(4 * side, 15 * 10³) · points[i] == [xi, yi] · The input is generated such that: points[i] lies on the boundary of the square. · All points[i] are unique.

From brute force to the pattern: Choosing k of up to 15,000 points is hopeless. Binary search plus a greedy circle check is polynomial.

Spot it: "Maximise the minimum" → binary search on d. Since k ≥ 4, the answer is at most side, and for distances ≤ side the Manhattan distance between boundary points equals their distance along the boundary. So unroll the boundary into a circle of length 4·side and greedily place points d apart.

Why not another pattern? Trying subsets of size k is combinatorial. Plain 2D reasoning is hard; the perimeter unrolling makes it one-dimensional.

Approach:

1. Map each point to its position along the boundary, walking (0,0) → (0,side) → (side,side) → (side,0) → back. Sort.
2. Check d: for each starting point, jump with binary search to the first point at least d further, k − 1 times; it works if the last pick is at most 4·side − d after the start (the gap that wraps around).
3. Binary-search the largest d in 1..side that passes.

from bisect import bisect_left

class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        def boundary_pos(x, y):  # distance walked along the boundary from (0, 0)
            if x == 0:
                return y
            if y == side:
                return side + x
            if x == side:
                return 3 * side - y
            return 4 * side - x

        pos = sorted(boundary_pos(x, y) for x, y in points)
        perimeter = 4 * side

        def can_pick(d):
            for start in pos:
                last = start
                for _ in range(k - 1):
                    j = bisect_left(pos, last + d)  # next point at least d further along
                    if j == len(pos):
                        break
                    last = pos[j]
                else:
                    if last - start <= perimeter - d:
                        return True  # the wrap-around gap back to start is also >= d
            return False

        lo = 1
        hi = side
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if can_pick(mid):
                lo = mid  # feasible: try a bigger distance
            else:
                hi = mid - 1
        return lo

What the code is doing, line by line:

1. boundary_pos turns the square's edge into a number line of length 4·side (a circle when it wraps).
2. Two boundary points at boundary distance ≤ side have the same Manhattan distance, and the answer never exceeds side with 4+ points, so 1D distances are enough.
3. can_pick tries every start; from it, each next point is the first one at least d further (binary search). The for … else runs only when all k − 1 jumps succeeded.
4. The last point must also be at least d before the start going around the circle: last − start ≤ perimeter − d.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All four corners with k = 4 → side.
• Points clustered on one edge.
• The wrap-around gap between the last and first pick.

Complexity: O(n · k · log n · log side) time, O(n) space.

Problem: Find the smallest positive divisor d such that the sum of ceil(nums[i] / d) is at most threshold.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 5 * 10⁴ · 1 ≤ nums[i] ≤ 10⁶ · nums.length ≤ threshold ≤ 10⁶

From brute force to the pattern: Linear search over divisors is O(n · max); binary search is O(n log max).

Spot it: A larger divisor never increases the sum → a monotone yes/no condition → binary search on the answer (like Koko Eating Bananas).

Why not another pattern? Trying every divisor up to max(nums) (10⁶) with an O(n) check is too slow.

Approach:

1. lo = 1, hi = max(nums) (then every term is 1).
2. Check d: sum((x + d − 1) // d) ≤ threshold.
3. Find the smallest d that passes.

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        lo, hi = 1, max(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            total = sum((x + mid - 1) // mid for x in nums)  # each term rounded up
            if total <= threshold:
                hi = mid  # works: try a smaller divisor
            else:
                lo = mid + 1
        return lo

What the code is doing, line by line:

1. (x + d − 1) // d is integer ceiling division.
2. With d = max(nums) the sum is n ≤ threshold (guaranteed), so the search space always contains an answer.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• threshold == len(nums) → max(nums).
• Single element.
• Large values.

Complexity: O(n log(max)) time, O(1) space.

Problem: Find any cell strictly greater than its 4 neighbours (outside the grid counts as −1), in O(m log n) or O(n log m).

Solve it on LeetCode ↗

Constraints: m == mat.length · n == mat[i].length · 1 ≤ m, n ≤ 500 · 1 ≤ mat[i][j] ≤ 10⁵ · No two adjacent cells are equal.

From brute force to the pattern: Checking every cell is O(mn); row binary search is O(n log m).

Spot it: Like Find Peak Element in 1D: binary search on the middle row. Its maximum is bigger than its left/right neighbours; if the cell below is bigger, a peak exists in the lower half (climbing up from there can't come back), else in the upper half.

Why not another pattern? Scanning every cell is O(mn); greedy hill climbing can take long winding paths.

Approach:

1. lo = 0, hi = m − 1.
2. mid row; c = column of its maximum.
3. If mat[mid + 1][c] > mat[mid][c]: lo = mid + 1; else hi = mid.
4. Return [lo, column of max in row lo].

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        lo, hi = 0, len(mat) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            c = mat[mid].index(max(mat[mid]))  # biggest in this row beats its left and right
            if mat[mid + 1][c] > mat[mid][c]:
                lo = mid + 1  # a peak lies below
            else:
                hi = mid  # mid's max is >= the cell below: a peak lies at or above
        c = mat[lo].index(max(mat[lo]))
        return [lo, c]

What the code is doing, line by line:

1. The row maximum is larger than its horizontal neighbours.
2. Moving toward a strictly larger vertical neighbour keeps a peak inside the remaining rows (values can't increase forever).
3. When one row is left, its maximum is larger than the rows around it by the invariant.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• One row (its maximum).
• One column.
• Several peaks (any is fine).

Complexity: O(n log m) time, O(1) space.

Problem: Distribute all products to n stores (one type per store) to minimise the largest amount any store gets.

Solve it on LeetCode ↗

Constraints: m == quantities.length · 1 ≤ m ≤ n ≤ 10⁵ · 1 ≤ quantities[i] ≤ 10⁵

From brute force to the pattern: Linear search over x is O(m · max); binary search is O(m log max).

Spot it: "Minimise the maximum" with a monotone check → binary search on the answer x: feasible iff Σ ceil(q / x) ≤ n.

Why not another pattern? Trying every x up to 10⁵ with an O(m) check is O(m · max).

Approach:

1. lo = 1, hi = max(quantities).
2. Feasible(x): stores needed Σ (q + x − 1) // x ≤ n.
3. Find the smallest feasible x.

class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        lo, hi = 1, max(quantities)
        while lo < hi:
            mid = (lo + hi) // 2
            stores = sum((q + mid - 1) // mid for q in quantities)  # each type split into chunks of <= mid
            if stores <= n:
                hi = mid  # fits: try a smaller maximum
            else:
                lo = mid + 1
        return lo

What the code is doing, line by line:

1. Splitting a type of q items into chunks of at most x needs ceil(q / x) stores.
2. A larger x needs fewer stores, so feasibility is monotone.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n equal to the number of types → max(quantities).
• Many stores.
• One type.

Complexity: O(m log(max)) time, O(1) space.

Problem: Design query(left, right, value): how many times value occurs in arr[left..right].

Solve it on LeetCode ↗

Constraints: 1 ≤ arr.length ≤ 10⁵ · 1 ≤ arr[i], value ≤ 10⁴ · 0 ≤ left ≤ right < arr.length · At most 10⁵ calls will be made to query

From brute force to the pattern: Scanning per query is O(n); index lists + bisect are O(log n).

Spot it: Group indices by value in a hash map (they're collected in sorted order); a range count is two binary searches.

Why not another pattern? Scanning the range per query is O(n) each; a prefix count per value is O(n · distinct) memory.

Approach:

1. Constructor: where[v] = list of indices with value v.
2. query: bisect_right(where[v], right) − bisect_left(where[v], left).

from bisect import bisect_left, bisect_right
from collections import defaultdict

class RangeFreqQuery:
    def __init__(self, arr: List[int]):
        self.where = defaultdict(list)  # value -> indices, ascending
        for i, v in enumerate(arr):
            self.where[v].append(i)

    def query(self, left: int, right: int, value: int) -> int:
        idx = self.where.get(value, [])
        return bisect_right(idx, right) - bisect_left(idx, left)  # indices inside [left, right]

What the code is doing, line by line:

1. Indices are appended in increasing order, so each list is sorted.
2. The two binary searches bracket exactly the indices in the range.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Value not in the array → 0.
• left == right.
• Whole-array query.

Complexity: O(n) to build, O(log n) per query, O(n) space.

Problem: Changing nums[i] by 1 costs cost[i]. Return the minimum total cost to make all elements equal.

Solve it on LeetCode ↗

Constraints: n == nums.length == cost.length · 1 ≤ n ≤ 10⁵ · 1 ≤ nums[i], cost[i] ≤ 10⁶ · Test cases are generated in a way that the output doesn't exceed 2⁵³-1

From brute force to the pattern: Every target value: O(n · range); binary search on the slope: O(n log range); weighted median: O(n log n).

Spot it: f(x) = Σ cost[i] · |nums[i] − x| is a sum of V-shapes, so it's convex: it decreases, then increases. Binary search for the first x where f(x + 1) ≥ f(x). (The optimum is the weighted median.)

Why not another pattern? Evaluating every x up to 10⁶ is O(n · range).

Approach:

1. lo = min(nums), hi = max(nums).
2. If f(mid) ≤ f(mid + 1), the minimum is at or left of mid; else right.
3. Return f(lo).

class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:
        def total(x):
            return sum(c * abs(v - x) for v, c in zip(nums, cost))

        lo, hi = min(nums), max(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if total(mid) <= total(mid + 1):
                hi = mid  # not decreasing any more: the minimum is at or before mid
            else:
                lo = mid + 1  # still going down
        return total(lo)

What the code is doing, line by line:

1. Each term c · |v − x| is convex, and sums of convex functions are convex.
2. Comparing neighbours tells which side of the minimum mid is on.
3. The optimum always lies between the smallest and largest value.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already equal → 0.
• One heavy cost dominates.
• Large values (64-bit cost).

Complexity: O(n log(range)) time, O(1) space.

Problem: Each robot fires once, left or right, up to its distance; bullets stop at other robots. Maximise the number of distinct walls destroyed.

Solve it on LeetCode ↗

Constraints: 1 ≤ robots.length == distance.length ≤ 10⁵ · 1 ≤ walls.length ≤ 10⁵ · 1 ≤ robots[i], walls[j] ≤ 10⁹ · 1 ≤ distance[i] ≤ 10⁵ · All values in robots are unique · All values in walls are unique

From brute force to the pattern: All 2ⁿ direction choices is exponential; the 2-state DP is O(n log w).

Spot it: Sorted by position, a robot's bullet stays between its neighbours, so only adjacent robots interact (robot i − 1 firing right and robot i firing left can hit the same walls). That's a DP over robots with 2 states, and wall counts in a range come from binary search on the sorted walls.

Why not another pattern? Trying all 2ⁿ direction choices is exponential.

Approach:

1. Sort robots by position, walls ascending; walls_in(a, b) = count of walls in [a, b] via bisect.
2. L_i = [max(p_i − d_i, p_{i−1} + 1), p_i], R_i = [p_i, min(p_i + d_i, p_{i+1} − 1)].
3. dpR[i] = |R_i| + max(dpL[i−1], dpR[i−1]); dpL[i] = |L_i| + max(dpL[i−1], dpR[i−1] − |R_{i−1} ∩ L_i|).

from bisect import bisect_left, bisect_right

class Solution:
    def maxWalls(self, robots: List[int], distance: List[int], walls: List[int]) -> int:
        bots = sorted(zip(robots, distance))
        walls = sorted(walls)
        n = len(bots)

        def walls_in(a, b):  # walls with a <= position <= b
            return bisect_right(walls, b) - bisect_left(walls, a) if a <= b else 0

        left_range, right_range = [], []
        for i, (p, d) in enumerate(bots):
            lo = max(p - d, bots[i - 1][0] + 1 if i else p - d)  # stops before the previous robot
            hi = min(p + d, bots[i + 1][0] - 1 if i + 1 < n else p + d)  # and before the next one
            left_range.append((lo, p))
            right_range.append((p, hi))
        dp_l = walls_in(*left_range[0])  # best so far if robot i fires left
        dp_r = walls_in(*right_range[0])  # ... or right
        for i in range(1, n):
            (a1, b1), (a2, b2) = right_range[i - 1], left_range[i]
            shared = walls_in(max(a1, a2), min(b1, b2))  # walls both bullets would hit
            new_l = walls_in(*left_range[i]) + max(dp_l, dp_r - shared)
            new_r = walls_in(*right_range[i]) + max(dp_l, dp_r)
            dp_l, dp_r = new_l, new_r
        return max(dp_l, dp_r)

What the code is doing, line by line:

1. A bullet can't pass a robot, so robot i only covers walls between its neighbours, including walls at its own position.
2. Only robot i − 1 firing right and robot i firing left can overlap; the DP subtracts that overlap once.
3. Each range count is two binary searches on the sorted walls.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Walls at robot positions.
• A robot right next to another (range cut off).
• No walls in range.

Complexity: O((n + w) log(n + w)) time, O(n) space.

Problem: Delete any elements; positions shift left. Maximise the number of positions i with nums[i] == i afterwards.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 0 ≤ nums[i] ≤ 10⁵

From brute force to the pattern: Enumerating deletions is exponential; the LIS view is O(n log n).

Spot it: Keeping nums[i] = v as a fixed point needs exactly i − v ≥ 0 deletions before it. Two kept points (i₁, v₁), (i₂, v₂) need v₁ < v₂ and i₁ − v₁ ≤ i₂ − v₂ (deletions only accumulate). Sort by d = i − v, then it's a strictly increasing LIS on v, solved with binary search.

Why not another pattern? Trying deletion sets is exponential; an O(n²) LIS is too slow for 10⁵.

Approach:

1. Candidates (d, v) with d = i − nums[i] ≥ 0.
2. Sort by (d, v).
3. Patience-sorting LIS (strict) on v with bisect_left.

from bisect import bisect_left

class Solution:
    def maxFixedPoints(self, nums: List[int]) -> int:
        cands = sorted((i - v, v) for i, v in enumerate(nums) if v <= i)  # (deletions needed before it, value)
        tails = []  # tails[t]: smallest last value of a chain of length t + 1
        for _, v in cands:
            pos = bisect_left(tails, v)  # strictly increasing values
            if pos == len(tails):
                tails.append(v)
            else:
                tails[pos] = v
        return len(tails)

What the code is doing, line by line:

1. If v₁ < v₂ and d₁ ≤ d₂, then i₁ = v₁ + d₁ < i₂, so the order in the array is right too.
2. Sorting by d (ties by v) makes any increasing subsequence of v a valid set of fixed points.
3. The tails array gives the LIS length in O(n log n).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already fixed points (d = 0).
• Values larger than their index (never usable).
• Equal values (only one can be kept).

Complexity: O(n log n) time, O(n) space.

Problem: Return the minimum radius so that every house is within that distance of some heater.

Solve it on LeetCode ↗

Constraints: 1 ≤ houses.length, heaters.length ≤ 3 * 10⁴ · 1 ≤ houses[i], heaters[i] ≤ 10⁹

From brute force to the pattern: All pairs: O(nm); binary search: O(n log m).

Spot it: Each house needs its nearest heater: sort heaters and binary search each house's position; the radius is the worst nearest distance.

Why not another pattern? Checking every house against every heater is O(n · m).

Approach:

1. Sort heaters.
2. For each house: i = bisect_left(heaters, h); nearest = min distance to heaters[i − 1] and heaters[i].
3. Answer = max over houses.

from bisect import bisect_left

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        heaters = sorted(heaters)
        radius = 0
        for h in houses:
            i = bisect_left(heaters, h)  # first heater at or right of the house
            right = heaters[i] - h if i < len(heaters) else float("inf")
            left = h - heaters[i - 1] if i > 0 else float("inf")
            radius = max(radius, min(left, right))  # this house's nearest heater
        return radius

What the code is doing, line by line:

1. The nearest heater is one of the two neighbours in sorted order.
2. The radius must cover the house whose nearest heater is farthest.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Houses outside all heaters.
• A heater on a house.
• One heater.

Complexity: O((n + m) log m) time, O(1) extra space.