Greedy

Problem: You start at index 0; nums[i] is the maximum jump length from index i. Return True if you can reach the last index.

Solve it on LeetCode ↗ · Video walkthrough ↗

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

From brute force to the pattern: DFS over all jump choices is exponential; a DP over "can I reach i?" is O(n²). Tracking only the farthest reach is O(n).

Spot it: A DP over "can I reach i?" works in O(n²), but the greedy view is O(n): everything up to the farthest index reached so far is reachable, so only that one number matters.

Approach:

1. farthest = 0.
2. Scan the indices left to right. If i > farthest, index i is unreachable and so is everything after it: return False.
3. Otherwise extend farthest = max(farthest, i + nums[i]).
4. If farthest reaches the last index, return True.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0          # every index up to here can be reached
        last = len(nums) - 1
        for i in range(len(nums)):
            if i > farthest:
                return False  # a gap: we can never get to i
            farthest = max(farthest, i + nums[i])
            if farthest >= last:
                return True
        return True

What the code is doing, line by line:

1. farthest: the reachable region is always one contiguous stretch 0..farthest. If you can jump up to 3, you can also jump 1 or 2.
2. if i > farthest: return False: we walked past the reachable stretch, which means we are stuck on a zero.
3. farthest = max(farthest, i + nums[i]): from i we can reach as far as i + nums[i].
4. if farthest >= last: return True: stop as soon as the end is within reach.

Dry run on the example:

nums = [3, 2, 1, 0, 4] (LeetCode Example 2). Returns False.

Edge cases to test:

• A single element → True.
• A zero you can't jump over → False.
• A zero you can jump over.

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

Problem: A circular route has stations; gas[i] is fuel available at i and cost[i] is fuel to drive from i to i + 1. Return the starting index that lets you drive one full lap with an initially empty tank, or -1. The answer is unique if it exists.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: n == gas.length == cost.length · 1 ≤ n ≤ 10⁵ · 0 ≤ gas[i], cost[i] ≤ 10⁴ · The input is generated such that the answer is unique.

From brute force to the pattern: Trying every start and simulating a lap is O(n²). The reset rule rules out whole stretches of starts at once: O(n).

Spot it: Trying every start is O(n²). Two greedy facts make it O(n): (1) a lap is possible only if total gas ≥ total cost; (2) if starting at s you run dry before reaching j, then no start between s and j works either.

Approach:

1. If sum(gas) < sum(cost), return -1.
2. Drive once around from start = 0, keeping tank += gas[i] − cost[i].
3. If tank drops below 0 at station i, restart: start = i + 1, tank = 0.
4. The start left at the end is the answer.

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1             # not enough fuel in total for any start
        start = 0
        tank = 0
        for i in range(len(gas)):
            tank = tank + gas[i] - cost[i]
            if tank < 0:
                # we can't get past i from start, nor from any station in between
                start = i + 1
                tank = 0
        return start

What the code is doing, line by line:

1. if sum(gas) < sum(cost): return -1: driving all the way around needs at least as much gas as the trip costs.
2. tank = tank + gas[i] - cost[i]: fill up at i, then drive to i + 1.
3. if tank < 0: we got stuck before i + 1. Any station between start and i would have arrived there with less fuel (it skips the non-negative stretch before it), so it would also get stuck. Jump to i + 1.
4. return start: totals were enough, and this is the only start that never ran dry for the rest of the array. The part before it is covered by the surplus.

Dry run on the example:

gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2] (LeetCode Example 1). Total gas 15 ≥ total cost 15. Returns 3.

Edge cases to test:

• Total gas < total cost → −1.
• A single station.
• The answer is the last station.

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

Problem: Children stand in a line with ratings. Give each at least one candy, and give a child with a higher rating than an adjacent child more candies than that neighbour. Return the minimum total.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ n == ratings.length ≤ 5 * 10⁴ · 0 ≤ ratings[i] ≤ 5 * 10⁴

From brute force to the pattern: Repeatedly fixing violations until none are left can take O(n²). Two directional passes satisfy both constraints minimally: O(n).

Spot it: Each child has two constraints (left and right). Satisfy them one direction at a time: a left-to-right pass fixes "more than my left neighbour", and a right-to-left pass fixes "more than my right neighbour" without breaking the first.

Approach:

1. Start everyone at 1 candy.
2. Left to right: if ratings[i] > ratings[i − 1], set candy[i] = candy[i − 1] + 1.
3. Right to left: if ratings[i] > ratings[i + 1], set candy[i] = max(candy[i], candy[i + 1] + 1). Use max so the left rule stays satisfied.
4. Return the sum.

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candy = [1] * n
        # pass 1: beat the LEFT neighbour when rated higher
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candy[i] = candy[i - 1] + 1
        # pass 2: beat the RIGHT neighbour too, without losing pass 1's guarantee
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candy[i] = max(candy[i], candy[i + 1] + 1)
        return sum(candy)

What the code is doing, line by line:

1. candy = [1] * n: the minimum each child must get.
2. Pass 1: climbing ratings left to right give 1, 2, 3, …. Each child gets the smallest count that beats its left neighbour.
3. Pass 2 runs right to left so candy[i + 1] is already final when we read it.
4. max(candy[i], candy[i + 1] + 1): take whichever requirement is larger; both still hold afterwards.
5. Each value is the minimum that satisfies both neighbours, so the sum is minimal.

Dry run on the example:

ratings = [1, 0, 2] (LeetCode Example 1). Returns 5 ([2, 1, 2]).

Edge cases to test:

• Equal ratings don't need more candy, e.g. [1, 2, 2] → 4.
• Strictly decreasing ratings.
• A single child → 1.

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

Problem: You may buy and sell as many times as you like, holding at most one share at a time (you can sell and buy again on the same day). Return the maximum profit.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ prices.length ≤ 3 * 10⁴ · 0 ≤ prices[i] ≤ 10⁴

From brute force to the pattern: Trying all buy/sell schedules is exponential; DP with hold/cash states is O(n). The greedy view (collect every rise) is the same O(n) with one line of logic.

Spot it: Unlimited transactions → any rising stretch a < b < c earns the same as the separate steps (b − a) + (c − b). So greedily take every positive day-to-day difference.

Approach:

1. Walk through consecutive pairs of days.
2. If the price rose, add the rise to the profit (buy yesterday, sell today).
3. Ignore falls: on those days you simply don't hold the stock.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            rise = prices[i] - prices[i - 1]
            if rise > 0:
                # buy yesterday, sell today: always worth it on an up day
                profit = profit + rise
        return profit

What the code is doing, line by line:

1. rise = prices[i] - prices[i - 1]: the change from yesterday.
2. if rise > 0: profit = profit + rise: the greedy choice. Taking every up-step adds up to the total of all rising stretches, and no strategy can earn more than that.
3. Falls are skipped because being out of the market costs nothing.

Dry run on the example:

prices = [7, 1, 5, 3, 6, 4] (LeetCode Example 1). Returns 7 (buy 1 sell 5, buy 3 sell 6).

Edge cases to test:

• Prices only fall → 0.
• Prices only rise → last − first.
• Flat prices.

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

Problem: citations[i] is the citation count of paper i. The h-index is the largest h such that at least h papers have at least h citations each. Return it.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: n == citations.length · 1 ≤ n ≤ 5000 · 0 ≤ citations[i] ≤ 1000

From brute force to the pattern: Trying every h and counting papers with ≥ h citations is O(n²). Sorting is O(n log n); counting sort (citations capped at n) is O(n).

Spot it: Sorting papers from most to least cited turns it into a greedy scan: the top h papers are the best candidates for an h-index of h, so keep increasing h while the h-th best paper still has at least h citations.

Approach:

1. Sort the citations in descending order.
2. For position i (0-based), the paper there is the (i + 1)-th best. If it has at least i + 1 citations, h = i + 1 is achievable.
3. Stop at the first paper that fails: every later paper has even fewer citations.

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        papers = sorted(citations, reverse=True)
        h = 0
        for i in range(len(papers)):
            # papers[0..i] are the i + 1 most-cited papers
            if papers[i] >= i + 1:
                h = i + 1
            else:
                break        # later papers have even fewer citations
        return h

What the code is doing, line by line:

1. sorted(citations, reverse=True): most-cited first; the input is left unchanged.
2. if papers[i] >= i + 1: the i + 1 best papers all have at least papers[i] citations, which is at least i + 1, so h = i + 1 works.
3. else: break: once a paper has fewer citations than its rank, no larger h can work.
4. A counting-sort version (buckets 0..n) runs in O(n).

Dry run on the example:

citations = [3, 0, 6, 1, 5] (LeetCode Example 1). Sorted: [6, 5, 3, 1, 0]. Returns 3.

Edge cases to test:

• All zeros → 0.
• A single paper.
• Citations larger than n.

Complexity: O(n log n) time for the sort, O(n) space for the sorted copy.

Problem: From index 0, nums[i] is the max jump length at i. Return the minimum number of jumps to reach the last index.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁴ · 0 ≤ nums[i] ≤ 1000 · It's guaranteed that you can reach nums[n - 1].

From brute force to the pattern: DP min jumps for each index over all its jumps is O(n²); level greedy is O(n).

Spot it: Indices reachable with j jumps form a contiguous range. Scan it, tracking the farthest index reachable with one more jump: that's the next range. Counting ranges is a greedy BFS without a queue.

Why not another pattern? DP over every index and every jump length is O(n²).

Approach:

1. end = end of the current range, far = farthest reach seen.
2. For i in 0..n − 2: far = max(far, i + nums[i]); when i == end, take a jump: jumps += 1, end = far.

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0
        end = 0  # last index reachable with `jumps` jumps
        far = 0  # farthest index reachable with one more jump
        for i in range(len(nums) - 1):
            far = max(far, i + nums[i])
            if i == end:
                jumps += 1  # we must jump to go past this range
                end = far
        return jumps

What the code is doing, line by line:

1. All indices up to end are reachable in jumps jumps.
2. Reaching end without being done means another jump is needed, and the best next range ends at far.
3. The loop stops before the last index, so no extra jump is counted there.

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 element → 0.
• One big first jump.
• Many zeros that must be jumped over.

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

Problem: Return the maximum difference between successive elements in sorted order, in linear time.

Solve it on LeetCode ↗

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

From brute force to the pattern: Sort and scan: O(n log n). Buckets: O(n).

Spot it: The answer is at least the average gap (max − min) / (n − 1). With buckets narrower than that, the max gap can't be inside a bucket, only between a bucket's max and the next non-empty bucket's min — a pigeonhole argument.

Why not another pattern? Sorting is O(n log n); the problem asks for linear time.

Approach:

1. size = max(1, (hi − lo) // (n − 1)); bucket index (x − lo) // size.
2. Keep min and max per bucket.
3. Scan buckets in order: gap = bucket min − previous bucket max.

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return 0
        lo, hi = min(nums), max(nums)
        size = max(1, (hi - lo) // (n - 1))  # no bigger than the average gap
        count = (hi - lo) // size + 1
        bucket_min = [None] * count
        bucket_max = [None] * count
        for x in nums:
            b = (x - lo) // size
            bucket_min[b] = x if bucket_min[b] is None else min(bucket_min[b], x)
            bucket_max[b] = x if bucket_max[b] is None else max(bucket_max[b], x)
        best = 0
        prev_max = lo
        for b in range(count):
            if bucket_min[b] is not None:
                best = max(best, bucket_min[b] - prev_max)  # gap across empty space between buckets
                prev_max = bucket_max[b]
        return best

What the code is doing, line by line:

1. Inside one bucket, values differ by less than size ≤ the answer, so they can't hold the maximum gap.
2. Only each bucket's extremes matter.
3. Empty buckets are skipped; the gap jumps over them.

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:

• Fewer than 2 elements → 0.
• All equal → 0.
• Two elements.

Complexity: O(n) time and space.

Problem: Arrange non-negative integers to form the largest number; return it as a string.

Solve it on LeetCode ↗

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

From brute force to the pattern: Trying all permutations is n!; the comparator sort is O(n log n).

Spot it: A greedy ordering: for any two numbers, the better order is decided by comparing the concatenations a + b and b + a. This comparison is transitive, so sorting with it gives the answer.

Why not another pattern? Sorting numerically or lexicographically fails: [3, 30] should give 330, not 303.

Approach:

1. Convert to strings.
2. Sort with cmp(a, b) = −1 if a + b > b + a.
3. Join; if the result starts with 0, return "0".

from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        strs = [str(x) for x in nums]

        def order(a, b):
            if a + b > b + a:
                return -1  # a should come first
            if a + b < b + a:
                return 1
            return 0

        strs.sort(key=cmp_to_key(order))
        result = "".join(strs)
        return "0" if result[0] == "0" else result  # all zeros

What the code is doing, line by line:

1. Comparing a + b vs b + a asks which order is better for this pair, and a sorted list is locally optimal everywhere.
2. If the largest piece is 0, every piece is 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:

• All zeros → "0".
• Prefixes like 3, 34, 30.
• A single number.

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

Problem: Each person is [h, k]: k people in front are at least as tall. Reconstruct the queue.

Solve it on LeetCode ↗

Constraints: 1 ≤ people.length ≤ 2000 · 0 ≤ hi ≤ 10⁶ · 0 ≤ ki < people.length · It is guaranteed that the queue can be reconstructed.

From brute force to the pattern: Trying permutations is n!; sorted insertion is O(n²).

Spot it: Shorter people are invisible to taller ones' k. Place the tallest first; then each shorter person inserted at index k has exactly k taller-or-equal people before them, and later (shorter) inserts don't break earlier counts — a greedy insertion.

Why not another pattern? Placing the shortest first makes every later insertion disturb existing counts.

Approach:

1. Sort by height descending, k ascending.
2. Insert each person at position k of the result list.

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people = sorted(people, key=lambda p: (-p[0], p[1]))  # tall first; fewer in front first
        queue = []
        for person in people:
            queue.insert(person[1], person)  # exactly k taller-or-equal people are already placed
        return queue

What the code is doing, line by line:

1. When a person is inserted, everyone already placed is at least as tall, so index k is exactly right.
2. Shorter people inserted later don't change the count of taller people ahead of anyone.

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 heights (k ascending).
• All k = 0.
• One person.

Complexity: O(n²) time (list inserts), O(n) space.

Problem: Can the cards be split into groups of groupSize consecutive values?

Solve it on LeetCode ↗

Constraints: 1 ≤ hand.length ≤ 10⁴ · 0 ≤ hand[i] ≤ 10⁹ · 1 ≤ groupSize ≤ hand.length

From brute force to the pattern: Trying all groupings is exponential; greedy from the smallest is near-linear after sorting.

Spot it: The smallest card can't be in the middle of a group, so it must start one. Greedily form groups from the smallest value using a counter.

Why not another pattern? Backtracking over group choices is exponential.

Approach:

1. If len(hand) % groupSize, false.
2. For each value x in sorted order with c = count[x] > 0: every x + d (d < groupSize) needs count ≥ c; subtract c.

from collections import Counter

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize:
            return False
        count = Counter(hand)
        for x in sorted(count):
            c = count[x]
            if c == 0:
                continue
            for v in range(x, x + groupSize):  # x must start c groups
                if count[v] < c:
                    return False
                count[v] -= c
        return True

What the code is doing, line by line:

1. The smallest remaining value has nothing below it, so every copy starts a group.
2. All c groups starting at x are formed at once.

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:

• groupSize = 1 → true.
• Count not divisible → false.
• Duplicates spanning several groups.

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

Problem: Sort the array in O(n log n) without built-in sort, using as little space as possible.

Solve it on LeetCode ↗

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

From brute force to the pattern: Insertion sort is O(n²); merge sort is O(n log n) in every case.

Spot it: Interviewers want a real O(n log n) sort. Merge sort is guaranteed O(n log n); its merge step is the same greedy "take the smaller front element" used in many problems.

Why not another pattern? Quicksort with a fixed pivot hits O(n²) on sorted or duplicate-heavy tests; bubble/insertion sorts are O(n²).

Approach:

1. Split in half and sort each recursively.
2. Merge: compare the heads of the two halves, append the smaller.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) <= 1:
            return nums
        mid = len(nums) // 2
        left = self.sortArray(nums[:mid])
        right = self.sortArray(nums[mid:])
        merged = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])  # the smaller head goes next
                i += 1
            else:
                merged.append(right[j])
                j += 1
        merged.extend(left[i:])  # one side may have leftovers
        merged.extend(right[j:])
        return merged

What the code is doing, line by line:

1. Each level of recursion does O(n) merging work, and there are log n levels.
2. <= keeps equal elements in their original order (stable).

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:

• Duplicates.
• Already sorted.
• Negative numbers.

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

Problem: Can nums be divided into sets of k consecutive numbers?

Solve it on LeetCode ↗

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

From brute force to the pattern: Exponential search vs a near-linear greedy.

Spot it: The smallest remaining number must start a set → greedy from the smallest with a counter.

Why not another pattern? Backtracking over set choices is exponential.

Approach:

1. If len(nums) % k, false.
2. For each value x ascending with c = count[x]: subtract c from x..x + k − 1, failing if any count is short.

from collections import Counter

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k:
            return False
        count = Counter(nums)
        for x in sorted(count):
            c = count[x]
            if c:
                for v in range(x, x + k):  # every copy of x starts a run
                    if count[v] < c:
                        return False
                    count[v] -= c
        return True

What the code is doing, line by line:

1. Identical to Hand of Straights with groupSize = k.
2. Handling all c copies at once avoids repeated scans.

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:

• k = 1.
• Length not divisible by k.
• Large repeated values.

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

Problem: Permute nums to maximise the total of all range-sum requests (mod 10⁹ + 7).

Solve it on LeetCode ↗

Constraints: n == nums.length · 1 ≤ n ≤ 10⁵ · 0 ≤ nums[i] ≤ 10⁵ · 1 ≤ requests.length ≤ 10⁵ · requests[i].length == 2 · 0 ≤ starti ≤ endi < n

From brute force to the pattern: Every permutation is n!; coverage counts + sorting is O(n log n).

Spot it: Each index contributes nums[index] × (number of requests covering it). By the rearrangement inequality, pair the largest values with the largest counts (greedy sort). Counts come from a difference array.

Why not another pattern? Trying permutations is n!; counting coverage per request naively is O(n · requests).

Approach:

1. diff[start] += 1, diff[end + 1] −= 1; prefix sums give freq.
2. Sort freq and nums; sum the products.

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        diff = [0] * (n + 1)
        for start, end in requests:
            diff[start] += 1  # coverage starts here
            diff[end + 1] -= 1  # and stops after end
        freq = []
        running = 0
        for i in range(n):
            running += diff[i]
            freq.append(running)  # how many requests include index i
        freq.sort()
        return sum(a * b for a, b in zip(sorted(nums), freq)) % (10**9 + 7)  # biggest with busiest

What the code is doing, line by line:

1. The total equals Σ nums[i] · freq[i] for the chosen arrangement.
2. Pairing sorted with sorted maximises a sum of products (rearrangement inequality).

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:

• Indices covered by no request (smallest numbers go there).
• One request.
• Overlapping requests.

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

Problem: Return the minimum number of deci-binary numbers (digits 0/1) that sum to the decimal string n.

Solve it on LeetCode ↗

Constraints: 1 ≤ n.length ≤ 10⁵ · n consists of only digits. · n does not contain any leading zeros and represents a positive integer.

From brute force to the pattern: Building summands one at a time is O(9 · len); the max digit is the answer directly.

Spot it: Each summand contributes at most 1 to each digit position (no carries help), so the biggest digit d needs d summands, and d summands are enough (greedy).

Why not another pattern? Constructing summands explicitly is unnecessary.

Approach:

1. Return int(max(n)).

class Solution:
    def minPartitions(self, n: str) -> int:
        return int(max(n))  # the largest digit needs that many 1s stacked on it

What the code is doing, line by line:

1. A digit d requires at least d summands with a 1 there.
2. With d = max digit summands, put a 1 in position p of the first digit[p] summands.

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 1s → 1.
• A 9 anywhere → 9.
• Very long strings.

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

Problem: You may reorder the columns freely. Return the largest all-ones submatrix area.

Solve it on LeetCode ↗

Constraints: m == matrix.length · n == matrix[i].length · 1 ≤ m * n ≤ 10⁵ · matrix[i][j] is either 0 or 1.

From brute force to the pattern: Permutations of columns are factorial; sorting heights per row is O(mn log n).

Spot it: Fix the bottom row. Each column has a height of consecutive 1s ending there. Since columns can be rearranged, sort heights descending: using the first w columns gives area heights[w − 1] · w (greedy).

Why not another pattern? Trying column permutations is factorial.

Approach:

1. Update height[c] row by row (reset to 0 on a 0).
2. Sort a copy descending; area candidates h · (i + 1).

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        n = len(matrix[0])
        height = [0] * n  # consecutive 1s ending at the current row
        best = 0
        for row in matrix:
            for c in range(n):
                height[c] = height[c] + 1 if row[c] else 0
            for width, h in enumerate(sorted(height, reverse=True), 1):
                best = max(best, h * width)  # tallest `width` columns side by side
        return best

What the code is doing, line by line:

1. Heights describe how far up a full column of 1s reaches from this row.
2. Placing the tallest columns next to each other is optimal; the shortest of them limits the rectangle.

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 zeros → 0.
• One row → number of 1s.
• One column.

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

Problem: With coins, buy as many ice cream bars as possible (each costs costs[i]).

Solve it on LeetCode ↗

Constraints: costs.length == n · 1 ≤ n ≤ 10⁵ · 1 ≤ costs[i] ≤ 10⁵ · 1 ≤ coins ≤ 10⁸

From brute force to the pattern: Comparison sorting is O(n log n); counting sort is O(n + C).

Spot it: To maximise the count, always buy the cheapest available bar → greedy. The problem asks for counting sort, as costs are small.

Why not another pattern? Any other choice can be swapped for a cheaper bar without reducing the count.

Approach:

1. Count bars per cost.
2. Go through costs ascending; buy min(count, coins // cost) bars.

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        count = [0] * (max(costs) + 1)
        for c in costs:
            count[c] += 1  # counting sort
        bought = 0
        for cost in range(1, len(count)):
            if count[cost] == 0:
                continue
            take = min(count[cost], coins // cost)  # as many as we can afford at this price
            bought += take
            coins -= take * cost
            if take < count[cost]:
                break  # can't afford more at this price, so nothing pricier either
        return bought

What the code is doing, line by line:

1. Cheapest-first maximises how many bars fit in the budget.
2. If not all bars at one price fit, no more expensive bar fits either.

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 for any bar → 0.
• Enough for all.
• Many equal costs.

Complexity: O(n + max cost) time and space.

Problem: You may decrease elements and rearrange. The first must be 1 and neighbours differ by ≤ 1. Maximise the largest element.

Solve it on LeetCode ↗

Constraints: 1 ≤ arr.length ≤ 10⁵ · 1 ≤ arr[i] ≤ 10⁹

From brute force to the pattern: Trying arrangements is factorial; sort + one pass is O(n log n).

Spot it: Sorted order gives each element its best chance to climb. Greedily make each value as large as allowed: min(value, previous + 1).

Why not another pattern? Decreasing values more than necessary only lowers the final maximum.

Approach:

1. Sort.
2. cur = 0; for each x: cur = min(x, cur + 1).
3. Return cur.

class Solution:
    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:
        cur = 0
        for x in sorted(arr):
            cur = min(x, cur + 1)  # climb by at most 1, never above x
        return cur

What the code is doing, line by line:

1. Starting from cur = 0 makes the first value min(x, 1) = 1.
2. Ascending order lets the sequence climb as long as possible.

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 large values → n.
• Many 1s.
• One element → 1.

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

Problem: A planet of mass can absorb an asteroid of mass ≤ its own, gaining it. Can it destroy all asteroids?

Solve it on LeetCode ↗

Constraints: 1 ≤ mass ≤ 10⁵ · 1 ≤ asteroids.length ≤ 10⁵ · 1 ≤ asteroids[i] ≤ 10⁵

From brute force to the pattern: Trying orders is factorial; sorting is optimal.

Spot it: Absorbing small asteroids only helps, so take them in increasing order (greedy). If even the smallest remaining is too big, it's impossible.

Why not another pattern? Any other order can only meet a big asteroid earlier with less mass.

Approach:

1. Sort asteroids.
2. For each: if bigger than mass, false; else mass += a.

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        for a in sorted(asteroids):  # smallest first
            if a > mass:
                return False  # too big, and every later one is at least as big
            mass += a
        return True

What the code is doing, line by line:

1. Mass never decreases, so absorbing easy asteroids first maximises mass for the hard ones.
2. Python integers don't overflow, so mass can grow freely.

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 huge asteroid.
• Equal mass (allowed).
• Mass grows past all asteroids.

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

Problem: Each processor has 4 cores and an availability time. Assign 4 tasks per processor to minimise the overall finish time.

Solve it on LeetCode ↗

Constraints: 1 ≤ n == processorTime.length ≤ 25000 · 1 ≤ tasks.length ≤ 10⁵ · 0 ≤ processorTime[i] ≤ 10⁹ · 1 ≤ tasks[i] ≤ 10⁹ · tasks.length == 4 * n

From brute force to the pattern: Trying assignments is factorial; two sorts give the optimal pairing.

Spot it: A processor's finish time is its start + its longest task. Greedy pairing: give the longest tasks to the earliest processors, four at a time.

Why not another pattern? Balancing by total work is wrong: cores run in parallel, only the longest task per processor matters.

Approach:

1. Sort processors ascending, tasks descending.
2. Processor i gets tasks 4i..4i + 3; its finish is p[i] + tasks[4i].
3. Return the maximum finish.

class Solution:
    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:
        processorTime = sorted(processorTime)
        tasks = sorted(tasks, reverse=True)
        return max(p + tasks[4 * i] for i, p in enumerate(processorTime))  # its longest of 4 tasks

What the code is doing, line by line:

1. The four tasks of a processor run in parallel; only the longest matters.
2. Pairing earliest processors with the longest tasks minimises the maximum (exchange argument).

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 processor.
• Equal processor times.
• Very long single task.

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

Problem: One trade: turn a 1-block surrounded by 0s into 0s, then a 0-block surrounded by 1s into 1s. Maximise the number of 1s.

Solve it on LeetCode ↗

Constraints: 1 ≤ n == s.length ≤ 10⁵ · s[i] is either '0' or '1'

From brute force to the pattern: Trying every trade and recounting is O(n²); one pass over block lengths is O(n).

Spot it: Clearing a 1-block glues its two neighbouring 0-blocks into one big 0-block, which then becomes all 1s. Net gain = the two 0-blocks' sizes. Greedy: pick the adjacent pair of 0-blocks with the largest total.

Why not another pattern? Simulating every trade and recounting is O(n²).

Approach:

1. Count the 1s.
2. List the lengths of the 0-blocks in order.
3. Answer: ones + max(z[i] + z[i + 1]) (just ones if fewer than two 0-blocks).

from itertools import groupby

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str) -> int:
        ones = s.count("1")
        zeros = [len(list(g)) for ch, g in groupby(s) if ch == "0"]  # 0-block lengths, in order
        best_gain = max((a + b for a, b in zip(zeros, zeros[1:])), default=0)  # merge two neighbouring 0-blocks
        return ones + best_gain

What the code is doing, line by line:

1. Consecutive 0-blocks are separated by exactly one 1-block, which is surrounded by 0s.
2. After removing that 1-block, the merged 0-block is surrounded by 1s (the augmented ends count), so it can be filled.
3. The removed 1s come back as part of the filled block, so the gain is exactly the two 0-blocks.

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:

• Fewer than two 0-blocks → just the 1s.
• All zeros.
• All ones.

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

Problem: Take one land ride and one water ride, in either order (each starts no earlier than its opening). Return the earliest finish.

Solve it on LeetCode ↗

From brute force to the pattern: All n · m pairs in both orders vs two linear passes.

Spot it: If land goes first, only the earliest land finish matters (finishing earlier never hurts). Then each water ride finishes at max(that time, its start) + duration. Do both orders (greedy on the first ride).

Why not another pattern? Trying all pairs is O(n · m), too slow for 5·10⁴ each.

Approach:

1. best_land = min(start + duration), same for water.
2. Land first: min(max(best_land, ws) + wd); water first: symmetric.
3. Return the smaller.

class Solution:
    def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int],
                           waterStartTime: List[int], waterDuration: List[int]) -> int:
        def then(first_start, first_dur, second_start, second_dur):
            ready = min(s + d for s, d in zip(first_start, first_dur))  # earliest end of the first ride
            return min(max(ready, s) + d for s, d in zip(second_start, second_dur))  # wait if it isn't open

        return min(then(landStartTime, landDuration, waterStartTime, waterDuration),
                   then(waterStartTime, waterDuration, landStartTime, landDuration))

What the code is doing, line by line:

1. Finishing the first ride earlier can only make the second ride finish earlier or at the same time.
2. So the first ride is always the one with the smallest finish time, and the second is tried exhaustively.

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 second ride opens later than the first finishes (waiting).
• One ride of each type.
• A long early ride vs a short late one.

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

Problem: Choose exactly k subarrays (repeats allowed); a subarray's value is max − min. Maximise the total.

Solve it on LeetCode ↗

Constraints: 1 ≤ n == nums.length ≤ 5 * 10⁴ · 0 ≤ nums[i] ≤ 10⁹ · 1 ≤ k ≤ 10⁵

From brute force to the pattern: Listing all subarray values is O(n²); the bound is reached by the whole array.

Spot it: Every subarray's value is at most max(nums) − min(nums), and the whole array achieves it. Repeats are allowed → greedy: pick it k times.

Why not another pattern? Enumerating subarray values (as in Range II, where repeats aren't allowed) is unnecessary here.

Approach:

1. Return (max(nums) − min(nums)) · k.

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        return (max(nums) - min(nums)) * k  # the whole array, chosen k times

What the code is doing, line by line:

1. A subarray's max is ≤ the global max and its min ≥ the global min.
2. Since the same subarray may be chosen repeatedly, the best one is used every time.

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 → 0.
• One element → 0.
• Large k (64-bit result).

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

Problem: A special binary string has equal 1s and 0s and every prefix has at least as many 1s as 0s. You may swap two adjacent special substrings. Return the lexicographically largest result.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 50 · s[i] is either '0' or '1'. · s is a special binary string.

From brute force to the pattern: BFS over swap results is exponential; recursive sorting is polynomial.

Spot it: Read 1 as ( and 0 as ): special strings are balanced bracket strings. Swapping adjacent special substrings = reordering sibling blocks. Greedy: make each block's inside as large as possible (recursion), then sort sibling blocks in descending order.

Why not another pattern? Simulating swaps with BFS explores exponentially many strings.

Approach:

1. Split s into top-level blocks where the balance returns to 0.
2. Each block is 1 + inner + 0; recursively optimise inner.
3. Sort blocks descending and concatenate.

class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        blocks = []
        balance = 0
        start = 0
        for i, ch in enumerate(s):
            balance += 1 if ch == "1" else -1
            if balance == 0:  # a top-level special block ends here
                inner = self.makeLargestSpecial(s[start + 1:i])  # best arrangement inside it
                blocks.append("1" + inner + "0")
                start = i + 1
        return "".join(sorted(blocks, reverse=True))  # bigger blocks first

What the code is doing, line by line:

1. Each top-level block is 1…0 with a special string inside.
2. Swaps can reorder sibling blocks arbitrarily, but never move characters across a block's wall.
3. Sorting siblings descending puts the largest prefix first, which is lexicographically optimal.

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 largest.
• Deeply nested 1111…0000.
• Many sibling blocks.

Complexity: O(n²) time in the worst case, O(n) recursion depth.

Problem: Task [actual, minimum] needs at least minimum energy to start and costs actual. Return the least starting energy to finish all tasks in some order.

Solve it on LeetCode ↗

Constraints: 1 ≤ tasks.length ≤ 10⁵ · 1 ≤ actuali ≤ minimumi ≤ 10⁴

From brute force to the pattern: All n! orders vs one sort.

Spot it: An exchange argument: tasks with a large "slack" minimum − actual should go first, while energy is high. Sort by slack descending (greedy), then compute the required start.

Why not another pattern? Trying all orders is n!; sorting by minimum alone is wrong.

Approach:

1. Sort by minimum − actual descending.
2. Walk the order: need = max(need, spent + minimum); spent += actual.

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks = sorted(tasks, key=lambda t: t[1] - t[0], reverse=True)  # largest slack first
        need = 0
        spent = 0
        for actual, minimum in tasks:
            need = max(need, spent + minimum)  # must still have `minimum` left after spending `spent`
            spent += actual
        return need

What the code is doing, line by line:

1. Starting with E, task i in the order needs E − spent ≥ minimum, i.e. E ≥ spent + minimum.
2. Swapping two adjacent tasks so the larger slack comes first never increases the requirement.

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 slacks.
• One task → its minimum.
• A task with huge minimum but small cost.

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

Problem: Build the smallest string word (length n + m − 1) such that the window at i equals str2 exactly when str1[i] == 'T', or return "".

Solve it on LeetCode ↗

Constraints: 1 ≤ n == str1.length ≤ 10⁴ · 1 ≤ m == str2.length ≤ 500 · str1 consists only of 'T' or 'F'. · str2 consists only of lowercase English characters.

From brute force to the pattern: Trying every letter in every free cell is exponential; the greedy is O(nm).

Spot it: T windows are forced: write str2 there (a conflict means ""). Every other cell is free; make it 'a' (greedy smallest). An F window that accidentally equals str2 must change one free cell; changing the rightmost free cell to 'b' hurts the order the least.

Why not another pattern? Trying characters for every free cell is exponential.

Approach:

1. Write str2 at every T start; conflict → "".
2. Remember which cells are free; set them to 'a'.
3. For each F window (left to right) that equals str2: set its rightmost free cell to 'b'; if it has none, return "".

class Solution:
    def generateString(self, str1: str, str2: str) -> str:
        n, m = len(str1), len(str2)
        word = [None] * (n + m - 1)
        for i, flag in enumerate(str1):
            if flag == "T":
                for j in range(m):
                    if word[i + j] not in (None, str2[j]):
                        return ""  # two T windows disagree
                    word[i + j] = str2[j]
        free = [ch is None for ch in word]  # cells no T window fixes
        word = [ch or "a" for ch in word]  # smallest letter everywhere free
        for i, flag in enumerate(str1):
            if flag == "F" and "".join(word[i:i + m]) == str2:
                p = next((q for q in range(i + m - 1, i - 1, -1) if free[q]), -1)
                if p < 0:
                    return ""  # nothing we may change in this window
                word[p] = "b"  # the latest change keeps the string smallest
        return "".join(word)

What the code is doing, line by line:

1. T windows leave no choice; overlapping T windows must agree.
2. Every free cell starts as 'a', the smallest possible letter.
3. An F window equal to str2 must differ somewhere; only free cells can change. Changing the rightmost one to 'b' (the next letter) keeps the prefix as small as possible.
4. Windows are fixed left to right, so later bumps never undo earlier fixes.

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:

• Conflicting T windows → "".
• An F window fully covered by T cells that equals str2 → "".
• str2 of length 1.

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

Problem: Heights start at 0, change by at most 1 between neighbours, and obey per-building maxima. Maximise the tallest building.

Solve it on LeetCode ↗

Constraints: 2 ≤ n ≤ 10⁹ · 0 ≤ restrictions.length ≤ min(n - 1, 10⁵) · 2 ≤ idi ≤ n · idi is unique. · 0 ≤ maxHeighti ≤ 10⁹

From brute force to the pattern: Building-by-building simulation is O(n) with n up to 10⁹; working only with restrictions is O(r log r).

Spot it: Each restriction also limits its neighbours (a limit of h at x caps h + |y − x| elsewhere). Greedily propagate the limits in both directions; then between two adjacent limits the tallest possible point is where the two slopes meet.

Why not another pattern? Simulating all n buildings (up to 10⁹) is impossible.

Approach:

1. Add [1, 0], sort by position.
2. Left to right: h[i] = min(h[i], h[i − 1] + gap). Right to left: h[i] = min(h[i], h[i + 1] + gap).
3. Between neighbours: peak = (h1 + h2 + gap) // 2. After the last: h_last + (n − last_pos).

class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        limits = sorted(restrictions + [[1, 0]])  # building 1 has height 0
        for i in range(1, len(limits)):  # a limit on the left caps the right side
            gap = limits[i][0] - limits[i - 1][0]
            limits[i][1] = min(limits[i][1], limits[i - 1][1] + gap)
        for i in range(len(limits) - 2, -1, -1):  # and a limit on the right caps the left side
            gap = limits[i + 1][0] - limits[i][0]
            limits[i][1] = min(limits[i][1], limits[i + 1][1] + gap)
        best = 0
        for (x1, h1), (x2, h2) in zip(limits, limits[1:]):
            best = max(best, (h1 + h2 + x2 - x1) // 2)  # where the two slopes meet
        last_x, last_h = limits[-1]
        return max(best, last_h + n - last_x)  # free climb after the last limit

What the code is doing, line by line:

1. After both passes, neighbouring limits are compatible: they differ by at most their distance.
2. Between limits h1 at x1 and h2 at x2, a height y at position p needs y ≤ h1 + (p − x1) and y ≤ h2 + (x2 − p); the best y is (h1 + h2 + x2 − x1) // 2.
3. After the last restriction, heights can keep rising by 1 per building.

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 restrictions → n − 1.
• A tight restriction far to the right.
• Restrictions that are looser than their neighbours allow.

Complexity: O(r log r) time for r restrictions, O(r) space.

Problem: Change exactly one character of a palindrome so it's no longer a palindrome and is as small as possible lexicographically.

Solve it on LeetCode ↗

Constraints: 1 ≤ palindrome.length ≤ 1000 · palindrome consists of only lowercase English letters.

From brute force to the pattern: Trying every single-character change and checking it is O(n²); the greedy is O(n).

Spot it: The earliest position decides lexicographic order, so greedily lower the first character you can: the first non-a in the first half becomes a. (Changing the middle of an odd-length string keeps it a palindrome, so only the first half counts.) If that half is all a, the smallest damage is turning the last character into b.

Why not another pattern? Trying all 25 · n single changes and checking each is O(n²).

Approach:

1. Length 1 → "" (any change is still a palindrome).
2. For i < n // 2: if s[i] != 'a', set it to a and return.
3. Otherwise set the last character to b.

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        n = len(palindrome)
        if n == 1:
            return ""  # one letter is always a palindrome
        chars = list(palindrome)
        for i in range(n // 2):  # first half only (the middle can't break it)
            if chars[i] != "a":
                chars[i] = "a"  # earliest possible decrease
                return "".join(chars)
        chars[-1] = "b"  # all 'a' so far: the cheapest increase, at the very end
        return "".join(chars)

What the code is doing, line by line:

1. Lowering a first-half character breaks the symmetry (its mirror is unchanged) and makes the string smaller at the earliest spot.
2. If the first half is all a, the string is all a except perhaps the middle; no character can be lowered usefully, so increase the last one.

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:

• Length 1 → "".
• All 'a' → last becomes 'b'.
• Odd length with a non-'a' only in the middle (aba → abb).

Complexity: O(n) time and space.

Problem: Is there i < j < k with nums[i] < nums[j] < nums[k]? Use O(n) time and O(1) space.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 5 * 10⁵ · -2³¹ ≤ nums[i] ≤ 2³¹ - 1

From brute force to the pattern: Triple loops O(n³); two variables O(n).

Spot it: Greedy with two variables: first = smallest value so far, second = smallest value that has something smaller before it. A value larger than second finishes a triplet. (It's LIS with only two tails.)

Why not another pattern? Triple loops are O(n³); prefix-min/suffix-max arrays use O(n) space.

Approach:

1. first = second = ∞.
2. x ≤ first → first = x; elif x ≤ second → second = x; else return true.

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        first = second = float("inf")
        for x in nums:
            if x <= first:
                first = x  # best possible start
            elif x <= second:
                second = x  # best middle with something smaller before it
            else:
                return True  # x is bigger than a valid pair
        return False

What the code is doing, line by line:

1. first may later move past second's position, but second still had a smaller value before it, which is all that matters.
2. Keeping both as small as possible maximises the chance of completing a triplet.

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 values (not strictly increasing).
• Decreasing → false.
• The triplet at the end.

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

Problem: Fly 2n people, exactly n to city A and n to city B, minimising total cost.

Solve it on LeetCode ↗

Constraints: 2 * n == costs.length · 2 ≤ costs.length ≤ 100 · costs.length is even. · 1 ≤ aCosti, bCosti ≤ 1000

From brute force to the pattern: All splits: C(2n, n); sorting by difference: O(n log n).

Spot it: Start by sending everyone to B; switching a person to A changes the cost by a − b. Pick the n most negative differences → greedy sort.

Why not another pattern? Trying every split is C(2n, n).

Approach:

1. Sort by a − b.
2. First n go to A, the rest to B.

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs = sorted(costs, key=lambda c: c[0] - c[1])  # people who save most by going to A first
        n = len(costs) // 2
        return sum(a for a, _ in costs[:n]) + sum(b for _, b in costs[n:])

What the code is doing, line by line:

1. Total = Σ b + Σ (a − b) over the A group, so the A group should have the smallest differences.
2. Exactly half go to each city.

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 differences.
• All prefer A (still only half go).
• n = 1.

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

Problem: Split into subsequences where max − min ≤ k in each. Return the fewest subsequences.

Solve it on LeetCode ↗

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

From brute force to the pattern: Combinatorial grouping vs sort + greedy.

Spot it: Order inside groups doesn't matter, so sort and greedily extend each group as far as start + k allows.

Why not another pattern? Trying groupings is combinatorial.

Approach:

1. Sort.
2. groups = 1, start = nums[0]; whenever x − start > k, start a new group at x.

class Solution:
    def partitionArray(self, nums: List[int], k: int) -> int:
        nums = sorted(nums)
        groups = 1
        start = nums[0]  # smallest value of the current group
        for x in nums:
            if x - start > k:
                groups += 1  # x can't join: open a new group
                start = x
        return groups

What the code is doing, line by line:

1. The smallest remaining value must start a group; that group should take everything within k of it.
2. Sorting makes groups contiguous.

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:

• k = 0 (equal values only).
• All within k → 1.
• Single element.

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

Problem: Using some digits of num, form the largest palindromic integer without leading zeros.

Solve it on LeetCode ↗

Constraints: 1 ≤ num.length ≤ 10⁵ · num consists of digits.

From brute force to the pattern: Subsets of digits are exponential; greedy pairing is linear.

Spot it: A palindrome is two mirrored halves plus an optional middle. Greedy: pairs of the largest digits go first, then the largest leftover digit in the middle.

Why not another pattern? Searching subsets of digits is exponential.

Approach:

1. Counts per digit.
2. Left half: for d from 9 to 0, append count[d] // 2 copies — but skip zeros if the half is still empty.
3. Middle: the largest digit with an odd remaining count.
4. If everything is empty, return "0".

from collections import Counter

class Solution:
    def largestPalindromic(self, num: str) -> str:
        count = Counter(num)
        left = ""
        for d in "9876543210":
            if d == "0" and not left:
                continue  # zeros can't lead the number
            left += d * (count[d] // 2)  # pairs: one copy on each side
            count[d] %= 2
        middle = next((d for d in "9876543210" if count[d]), "")  # biggest digit left over
        result = left + middle + left[::-1]
        return result or "0"

What the code is doing, line by line:

1. Bigger digits further left make the number larger; pairs fill both sides symmetrically.
2. If only zeros could form pairs, they're skipped, leaving a single digit (or "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:

• Only zeros → "0".
• Zero pairs with no other pairs.
• Single digit.

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

Problem: Split s into the fewest substrings with no repeated letters.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 10⁵ · s consists of only English lowercase letters.

From brute force to the pattern: Exponential split choices vs a greedy scan.

Spot it: Greedy: make each part as long as possible; start a new part exactly when the next letter is already in the current one (a set).

Why not another pattern? Trying split points is exponential.

Approach:

1. parts = 1, seen = set().
2. For each letter: if seen, parts += 1 and reset seen; add the letter.

class Solution:
    def partitionString(self, s: str) -> int:
        parts = 1
        seen = set()
        for ch in s:
            if ch in seen:
                parts += 1  # this letter would repeat: start a new part here
                seen = set()
            seen.add(ch)
        return parts

What the code is doing, line by line:

1. Cutting later is never worse than cutting earlier (exchange argument).
2. A bitmask of 26 bits works the same way.

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 distinct → 1.
• All equal → n.
• Single character.

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

Problem: In a circular array, make every subarray of length k have the same sum using ±1 operations. Return the fewest operations.

Solve it on LeetCode ↗

Constraints: 1 ≤ k ≤ arr.length ≤ 10⁵ · 1 ≤ arr[i] ≤ 10⁹

From brute force to the pattern: Trying targets per group is slow; the median per gcd-group is optimal.

Spot it: Neighbouring windows differ by arr[i + k] − arr[i], so all sums are equal iff arr[i] == arr[i + k] (circularly). That links indices into gcd(n, k) groups; each group must become one value, cheapest at its median (a greedy choice).

Why not another pattern? Trying target values or simulating operations is slow.

Approach:

1. g = gcd(n, k).
2. For each r < g: the group arr[r], arr[r + g], …; cost = Σ |x − median|.
3. Sum the costs.

from math import gcd

class Solution:
    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:
        g = gcd(len(arr), k)  # stepping by k around the circle visits exactly these groups
        total = 0
        for r in range(g):
            group = sorted(arr[r::g])
            mid = group[len(group) // 2]  # the median minimises total distance
            total += sum(abs(x - mid) for x in group)
        return total

What the code is doing, line by line:

1. Stepping by k around a circle of length n visits exactly the indices congruent mod gcd(n, k).
2. All values in a group must end equal; the median minimises the number of ±1 steps.

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:

• k = n (one window).
• gcd = 1 (everything equal).
• Already equal → 0.

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

Problem: Each operation adds a positive x to a subarray (cost x). Return the minimum total cost to make the array non-decreasing.

Solve it on LeetCode ↗

Constraints: 1 ≤ n == nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁹

From brute force to the pattern: Searching operations is pointless once the difference view is clear.

Spot it: Each drop nums[i] > nums[i + 1] must be closed. An operation on [l, r] raises only the step into l (by x), so it can close at most x of drop in total; adding to the whole suffix after a drop closes exactly that drop without harming anything → greedy: the answer is the sum of drops.

Why not another pattern? Simulating raises or searching operation sets is unnecessary.

Approach:

1. Sum max(0, nums[i] − nums[i + 1]) over all i.

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        return sum(max(0, a - b) for a, b in zip(nums, nums[1:]))  # every drop must be lifted

What the code is doing, line by line:

1. Lower bound: one operation with value x increases exactly one boundary difference by x, so the total x is at least the total drop.
2. Upper bound: lifting the suffix after each drop by its size achieves 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:

• Already sorted → 0.
• Strictly decreasing.
• Large values.

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

Problem: In each move, any machines each pass one dress to a neighbour. Return the fewest moves to make all machines equal, or −1.

Solve it on LeetCode ↗

Constraints: n == machines.length · 1 ≤ n ≤ 10⁴ · 0 ≤ machines[i] ≤ 10⁵

From brute force to the pattern: Simulation is slow; the two bounds give the answer in O(n).

Spot it: Two greedy bounds: dresses crossing a boundary move one per step, so the largest prefix imbalance is a lower bound; and a machine can give away only one dress per move, so the largest surplus is another. The answer is their maximum.

Why not another pattern? Simulating moves is slow and hard to make optimal.

Approach:

1. If the total isn't divisible by n, −1. avg = total / n.
2. Running flow += m − avg; track max(|flow|, m − avg).

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        total, n = sum(machines), len(machines)
        if total % n:
            return -1
        avg = total // n
        flow = 0  # dresses that must cross the boundary to the right of this machine
        best = 0
        for m in machines:
            extra = m - avg
            flow += extra
            best = max(best, abs(flow), extra)  # boundary traffic, or one machine emptying itself
        return best

What the code is doing, line by line:

1. flow after machine i is how many dresses must cross between i and i + 1; only one crosses per move.
2. A machine with surplus e needs at least e moves (it gives one per move), even if it gives both ways.
3. The maximum of these bounds is achievable (a known result).

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 divisible → −1.
• Already balanced → 0.
• One machine holding everything.

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

Problem: Tap i waters [i − ranges[i], i + ranges[i]]. Return the fewest taps covering [0, n], or −1.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10⁴ · ranges.length == n + 1 · 0 ≤ ranges[i] ≤ 100

From brute force to the pattern: DP over positions is O(n · range); the greedy is O(n).

Spot it: Covering a segment with the fewest intervals → greedy interval jumping. Record, for each start, the farthest reach; then sweep like Jump Game II, opening a new tap when the current coverage ends.

Why not another pattern? DP over positions is O(n · range).

Approach:

1. reach[l] = max(reach[l], r) for each tap (clamped to [0, n]).
2. Sweep i = 0..n−1: track far; when i reaches end, open a tap (end = far); if far ≤ i, it's impossible.

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        reach = [0] * (n + 1)  # reach[l]: farthest point covered by a tap starting at or before... exactly l
        for i, r in enumerate(ranges):
            left, right = max(0, i - r), min(n, i + r)
            reach[left] = max(reach[left], right)
        taps = 0
        end = far = 0  # end: covered so far; far: best reach among taps starting <= i
        for i in range(n):
            far = max(far, reach[i])
            if i == end:
                if far <= i:
                    return -1  # nothing reaches past i
                taps += 1  # open the tap that reaches farthest
                end = far
        return taps

What the code is doing, line by line:

1. Only the farthest reach per starting point matters.
2. Like Jump Game II: when the current coverage ends, the best next tap is the one reaching farthest among those starting inside 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:

• A gap no tap covers → −1.
• One tap covering everything.
• Ranges of 0.

Complexity: O(n) time and space.

Problem: Repeatedly remove a prefix of nums, appending its MEX to result. Return the lexicographically largest result.

Solve it on LeetCode ↗

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

From brute force to the pattern: All cutting choices are exponential; the greedy is linear.

Spot it: A prefix's MEX can't exceed the MEX of the whole remainder, so the best next value is the remainder's MEX. Reach it with the shortest prefix (greedy): that leaves the longest remainder, whose MEX (and length) can only be larger.

Why not another pattern? Trying all ways to cut the array is exponential.

Approach:

1. suffix_mex[i] = MEX of nums[i:] (scan from the right, raising a pointer).
2. At i: t = suffix_mex[i]. If t == 0, append 0 and take one element.
3. Else scan forward until all of 0..t−1 are seen; append t and continue after that point.

class Solution:
    def maximumMEX(self, nums: List[int]) -> List[int]:
        n = len(nums)
        suffix_mex = [0] * (n + 1)
        present = set()
        mex = 0
        for i in range(n - 1, -1, -1):
            present.add(nums[i])
            while mex in present:
                mex += 1  # MEX only grows as the suffix grows
            suffix_mex[i] = mex
        result = []
        i = 0
        while i < n:
            target = suffix_mex[i]  # the best value we can append now
            if target == 0:
                result.append(0)
                i += 1  # shortest prefix: one element
                continue
            need = set(range(target))
            while need:
                need.discard(nums[i])  # collect 0..target-1
                i += 1
            result.append(target)
        return result

What the code is doing, line by line:

1. MEX(prefix) ≤ MEX(remainder), since a missing value of the remainder is missing from the prefix too.
2. Taking the shortest prefix that reaches it leaves a superset for later, which can only keep later values (and the length) at least as large.
3. Each element is scanned once overall, plus O(target) work per step bounded by the elements consumed.

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 0 at all → all zeros.
• Everything in one step.
• Repeated small values.

Complexity: O(n + max) time, O(n) space.

Problem: Multiply elements by 2 at most k times in total. Maximise the OR of the array.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁹ · 1 ≤ k ≤ 15

From brute force to the pattern: Trying every distribution of k doublings is exponential; one element at a time is O(n).

Spot it: Greedy: shifting one number left by k pushes its highest bit higher than anything else can reach, so all k doublings go to a single element. Try each element, OR-ing it (shifted) with the prefix and suffix ORs of the rest.

Why not another pattern? Splitting doublings between elements never beats putting them all on the one that gets the highest bit.

Approach:

1. prefix[i] = OR of nums[:i], suffix[i] = OR of nums[i+1:].
2. Candidate prefix[i] | (nums[i] << k) | suffix[i]; take the max.

class Solution:
    def maximumOr(self, nums: List[int], k: int) -> int:
        n = len(nums)
        suffix = [0] * (n + 1)  # suffix[i]: OR of nums[i:]
        for i in range(n - 1, -1, -1):
            suffix[i] = suffix[i + 1] | nums[i]
        best = prefix = 0  # prefix: OR of nums[:i]
        for i, x in enumerate(nums):
            best = max(best, prefix | (x << k) | suffix[i + 1])  # all doublings on x
            prefix |= x
        return best

What the code is doing, line by line:

1. The highest bit of the result decides most of its value; one element shifted by k reaches the highest possible bit.
2. Prefix and suffix ORs give "everything except i" in O(1).

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 element.
• Equal elements.
• k = 15 (large shifts).

Complexity: O(n) time and space.

Problem: Swap at most two digits once to make the largest possible number.

Solve it on LeetCode ↗

Constraints: 0 ≤ num ≤ 10⁸

From brute force to the pattern: All pairs of positions is O(d²); the greedy is O(10d).

Spot it: Greedy: improve the leftmost position possible. For each digit from the left, if a bigger digit appears later, swap with the last occurrence of the biggest one (the last keeps smaller digits further left).

Why not another pattern? Trying all pairs of swaps is O(d²) — fine for 9 digits, but the greedy shows the reasoning.

Approach:

1. last[d] = last index of digit d.
2. For each position i: for d from 9 down to digit[i] + 1: if last[d] > i, swap and return.
3. Otherwise the number is already maximal.

class Solution:
    def maximumSwap(self, num: int) -> int:
        digits = list(str(num))
        last = {int(d): i for i, d in enumerate(digits)}  # last position of each digit
        for i, d in enumerate(digits):
            for bigger in range(9, int(d), -1):
                if last.get(bigger, -1) > i:
                    j = last[bigger]  # the rightmost copy of the largest bigger digit
                    digits[i], digits[j] = digits[j], digits[i]
                    return int("".join(digits))
        return num  # already the largest arrangement reachable

What the code is doing, line by line:

1. Raising the leftmost possible digit dominates any change further right.
2. Taking the last copy of the larger digit moves the smaller digit as far right as possible.

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 descending → unchanged.
• Repeated digits (1993 → 9913).
• Single digit.

Complexity: O(10 · d) time for d digits, O(d) space.