Two Pointers

Problem: height[i] is a vertical wall at position i. Pick two walls so that, together with the x-axis, they hold the most water. Return that area.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: n == height.length · 2 ≤ n ≤ 10⁵ · 0 ≤ height[i] ≤ 10⁴

From brute force to the pattern: Trying every pair of lines is O(n²). Start at both ends (maximum width) and always move the shorter wall inward: every pair you skip by doing so is provably no better, because the shorter wall already limits it. One pass: O(n).

Spot it: the answer depends on two ends (width × shorter wall) and the brute force checks all pairs. Start with the widest container and squeeze.

Key insight: area = (r − l) × min(h[l], h[r]). If h[l] is the shorter wall, every container that keeps l and moves r inward is narrower and no taller, so it can't win. Discard l.

Approach:

1. Put left at the first wall and right at the last: the widest possible container.
2. Compute the area (right − left) × min(height[left], height[right]) and keep the best in best_area.
3. Move the pointer at the shorter wall inward (on a tie, either one).
4. Stop when left meets right and return best_area.

from typing import List


class Solution:
    def maxArea(self, height: List[int]) -> int:
        # start with the WIDEST container: the first wall and the last wall
        left = 0
        right = len(height) - 1
        best_area = 0
        while left < right:
            # water can only rise as high as the SHORTER of the two walls
            shorter_wall = min(height[left], height[right])
            width = right - left
            area = width * shorter_wall
            # remember the biggest area we have seen so far
            if area > best_area:
                best_area = area
            # move the pointer at the shorter wall inward:
            # keeping the shorter wall can only give narrower, no-taller containers
            if height[left] < height[right]:
                left = left + 1
            else:
                right = right - 1
        return best_area

What the code is doing, line by line:

1. left = 0, right = len(height) - 1: start with the widest container, the first wall and the last wall.
2. best_area = 0: the biggest area found so far.
3. while left < right: a container needs two different walls.
4. shorter_wall = min(height[left], height[right]): water spills over the shorter wall, so the water level is the height of the shorter wall.
5. width = right - left and area = width * shorter_wall: the area of a rectangle.
6. if area > best_area: best_area = area: remember it if it is the best so far.
7. if height[left] < height[right]: left = left + 1 / else: right = right - 1: move the pointer at the shorter wall. Any other container that keeps the shorter wall is narrower and still capped by that same short wall, so it can only be smaller. On a tie the code moves right (either is fine).
8. return best_area once the pointers meet.

Dry run on the example:

height = [1, 8, 6, 2, 5, 4, 8, 3, 7] (LeetCode Example 1). Returns 49.

Edge cases to test:

• Two lines only, e.g. [1, 1] → 1.
• Equal heights at both ends: moving either is safe.
• Strictly decreasing heights, e.g. [5, 4, 3, 2, 1].

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

Problem: Return every unique triplet [a, b, c] from nums with a + b + c = 0.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 3 ≤ nums.length ≤ 3000 · -10⁵ ≤ nums[i] ≤ 10⁵

From brute force to the pattern: Three nested loops over all triplets is O(n³), and removing duplicate triplets needs a set. Sorting lets you fix one number and find the other two with opposite-end pointers in O(n), so O(n²) total, and sorted order makes skipping duplicates trivial.

Spot it: "triplets that sum to a target", values (not indices) returned, so we may sort. Fix the first number, then it's Two Sum II on the rest.

Key insight: sorting gives both the squeeze rule and an easy way to skip duplicates: skip an i equal to the previous i, and after a hit skip l values equal to the one just used.

Approach:

1. Sort the array.
2. For each index i (the first number, first = nums[i]): stop if first > 0; skip it if it equals nums[i − 1].
3. Run Two Sum II on the part to the right of i with target −first: left = i + 1, right = length − 1, and squeeze by the sign of total.
4. On a hit, record the triplet, move both pointers, and skip repeated values of left.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # sorting lets us squeeze with two pointers AND puts equal values side by side
        nums.sort()
        result = []
        length = len(nums)
        # i is the position of the FIRST number of the triplet
        for i in range(length - 2):
            first = nums[i]
            # the list is sorted: if the smallest of the three numbers is already
            # positive, the sum can never be zero, so we can stop completely
            if first > 0:
                break
            # the same first number as last round would only find the same triplets
            if i > 0 and first == nums[i - 1]:
                continue
            # now find two numbers to the right of i that add up to -first
            left = i + 1
            right = length - 1
            while left < right:
                total = first + nums[left] + nums[right]
                if total < 0:
                    # too small: we need a bigger number, so move left to the right
                    left = left + 1
                elif total > 0:
                    # too big: we need a smaller number, so move right to the left
                    right = right - 1
                else:
                    # the three numbers sum to zero: save the triplet
                    result.append([first, nums[left], nums[right]])
                    # step both pointers past the numbers we just used
                    left = left + 1
                    right = right - 1
                    # skip copies of the second number so we don't save the same triplet twice
                    while left < right and nums[left] == nums[left - 1]:
                        left = left + 1
        return result

What the code is doing, line by line:

1. nums.sort(): sorting makes the squeeze rule work and puts equal numbers next to each other (needed to skip duplicates).
2. result = [], length = len(nums): the list of triplets we will return, and the list size.
3. for i in range(length - 2): i picks the first number. We stop two places before the end so there is room for a second and third number.
4. first = nums[i]; if first > 0: break: the list is sorted, so if the smallest of the three is positive, all three are positive and can never sum to zero. Nothing later can work either, so stop the whole loop.
5. if i > 0 and first == nums[i - 1]: continue: we already tried this same first number in the previous round; trying again would find the same triplets.
6. left = i + 1, right = length - 1: two pointers on the part to the right of i.
7. total = first + nums[left] + nums[right]: the sum of the three candidates.
8. total < 0 → left = left + 1 (we need a bigger number); total > 0 → right = right - 1 (we need a smaller number).
9. Otherwise the total is zero: result.append([...]) saves the triplet, then both pointers step inward. The inner while ... nums[left] == nums[left - 1] keeps moving left past copies of the number we just used, so the same triplet is not saved twice.
10. return result.

Dry run on the example:

nums = [-1, 0, 1, 2, -1, -4] (LeetCode Example 1). After nums.sort() it is [-4, -1, -1, 0, 1, 2]. Returns [[-1, -1, 2], [-1, 0, 1]].

Edge cases to test:

• All zeros, e.g. [0, 0, 0, 0] → just [[0, 0, 0]] (duplicate skipping).
• No triplet exists, e.g. [0, 1, 1] → [].
• Many repeated values, e.g. [-2, 0, 0, 2, 2].

Complexity: O(n²) time, O(1) extra space (ignoring sort/output).

Problem: A sorted array and a target; exactly one pair sums to it. Return their 1-based indices using constant extra space.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 2 ≤ numbers.length ≤ 3 * 10⁴ · -1000 ≤ numbers[i] ≤ 1000 · numbers is sorted in non-decreasing order. · -1000 ≤ target ≤ 1000 · The tests are generated such that there is exactly one solution.

From brute force to the pattern: Checking every pair is O(n²); a hash map is O(n) but uses O(n) space. Because the input is sorted, two pointers at the ends find the pair in O(n) time and O(1) space: every move discards a value that can't be part of the answer.

Spot it: "sorted" + "pair sums to target" + "constant space" is the textbook opposite-ends case (the first visualizer above is exactly this).

Approach:

1. left = 0, right = len(numbers) − 1.
2. If pair_sum equals the target, return [left + 1, right + 1] (1-based).
3. Sum too small → left = left + 1; too big → right = right - 1.
4. Repeat while left < right. A solution is guaranteed.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # left = smallest number, right = biggest number
        left = 0
        right = len(numbers) - 1
        while left < right:
            pair_sum = numbers[left] + numbers[right]
            if pair_sum == target:
                # the problem wants 1-based positions, so add 1 to each index
                return [left + 1, right + 1]
            if pair_sum < target:
                # sum too small: the only way to grow it is a bigger left number
                left = left + 1
            else:
                # sum too big: the only way to shrink it is a smaller right number
                right = right - 1
        # the problem promises an answer exists, so we never get here
        return []

What the code is doing, line by line:

1. left = 0, right = len(numbers) - 1: smallest and biggest numbers.
2. while left < right: keep going while they point at two different numbers.
3. pair_sum = numbers[left] + numbers[right]: the sum of the current pair.
4. if pair_sum == target: return [left + 1, right + 1]: LeetCode numbers positions from 1, while Python indexes from 0, so add 1 to each.
5. if pair_sum < target: left = left + 1: too small, and only a bigger left number can make it bigger.
6. else: right = right - 1: too big, and only a smaller right number can make it smaller.
7. return []: never reached because the problem guarantees one answer, but every function path should return something.

Dry run on the example:

numbers = [2, 7, 11, 15], target = 9 (LeetCode Example 1). Returns [1, 2].

In that example only right moved, so here is one more input (not from LeetCode) where both pointers move: numbers = [1, 3, 4, 5, 7, 11], target = 9. Returns [3, 4].

Edge cases to test:

• The answer uses the first and last elements.
• Negative numbers, e.g. [-1, 0], target -1 → [1, 2].
• Remember the answer is 1-indexed.

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

Problem: Sort an array of 0s, 1s and 2s in place, in one pass, without a library sort.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: n == nums.length · 1 ≤ n ≤ 300 · nums[i] is either 0, 1, or 2.

From brute force to the pattern: Calling sort() is O(n log n); counting 0s, 1s and 2s and rewriting needs two passes. The Dutch-flag partition puts every element in its zone in a single pass: O(n) time, O(1) space.

Spot it: "in place" + "partition into groups". Use three pointers: low (next slot for a 0), mid (reader), high (next slot for a 2).

Key insight: after swapping a 2 to high, don't advance mid: the value that came back hasn't been inspected yet. After swapping a 0 to low, the value that came back is a 1 (already inspected), so advance both.

Approach:

1. Keep regions: [0, low) are 0s, [low, mid) are 1s, (high, end] are 2s, and [mid, high] is still unknown.
2. nums[mid] == 0 → swap it with low, then advance low and mid.
3. nums[mid] == 1 → it's already in place; advance mid.
4. nums[mid] == 2 → swap it with high and shrink high. Do not advance mid.
5. Stop when mid passes high.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        low = 0                    # next slot (from the front) where a 0 should go
        mid = 0                    # the reader: the value we are inspecting now
        high = len(nums) - 1       # next slot (from the back) where a 2 should go
        # positions mid .. high are still unchecked; stop when that range is empty
        while mid <= high:
            value = nums[mid]
            if value == 0:
                # swap nums[low] and nums[mid] using a temporary variable
                temp = nums[low]
                nums[low] = nums[mid]
                nums[mid] = temp
                # the 0 is now in its region; the value that came back from "low"
                # was already inspected (it is a 1), so both pointers move on
                low = low + 1
                mid = mid + 1
            elif value == 1:
                # a 1 belongs in the middle, which is exactly where it is: move on
                mid = mid + 1
            else:
                # value is 2: swap it to the back
                temp = nums[high]
                nums[high] = nums[mid]
                nums[mid] = temp
                high = high - 1
                # do NOT move mid: the value that came from the back is still unchecked

What the code is doing, line by line:

1. low = 0, mid = 0, high = len(nums) - 1: everything before low is 0, between low and mid is 1, after high is 2, and mid .. high is still unchecked.
2. while mid <= high: keep going while there is at least one unchecked value.
3. value = nums[mid]: the value we are inspecting.
4. if value == 0: swap nums[low] and nums[mid] in three steps: save nums[low] in temp, overwrite nums[low], then put temp into nums[mid]. (Without temp, the first assignment would destroy the old value.) Then low = low + 1 and mid = mid + 1: the value that came back from low was already inspected, so we can move past it.
5. elif value == 1: mid = mid + 1: a 1 is already in the middle region, just move on.
6. else: (a 2) swap nums[mid] with nums[high] the same way and high = high - 1. mid does not move, because the value that just arrived from the back has never been inspected.
7. There is no return: LeetCode wants the list changed in place, and the function returns None.

Dry run on the example:

nums = [2, 0, 2, 1, 1, 0] (LeetCode Example 1). Ends as [0, 0, 1, 1, 2, 2].

Edge cases to test:

• Already sorted, e.g. [0, 1, 2].
• All one colour, e.g. [2, 2, 2].
• Swapping a 2 from high that lands another 2 at mid: that's why mid stays put.

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

Problem: height is an elevation map of bars of width 1. How much rain water is trapped after it rains?

Solve it on LeetCode ↗ · Video walkthrough ↗

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

From brute force to the pattern: For every bar, scan left and right for the tallest walls: O(n²). Precomputing left-max and right-max arrays makes it O(n) time but O(n) space. Two pointers drop the arrays: the lower running maximum decides the water, so one side can always be settled: O(1) space.

Spot it: water above bar i = min(tallest on the left, tallest on the right) − height[i]. Depends on both ends, so squeeze from both sides.

Key insight: if height[l] < height[r], then the right side certainly has a wall at least as tall as height[r], so the water at l is decided by left_max alone. Settle l and move on. Mirror for the right.

Approach:

1. left = 0, right = n − 1, and left_max, right_max, water all start at 0.
2. Compare height[left] and height[right]. The lower side is the one whose water level can be settled now.
3. If height[left] < height[right]: update left_max, add left_max − height[left], move left right.
4. Otherwise do the mirror image on the right side.
5. Stop when the pointers meet; water is the answer.

class Solution:
    def trap(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        left_max = 0       # tallest bar seen so far coming from the left
        right_max = 0      # tallest bar seen so far coming from the right
        water = 0          # total trapped water
        while left < right:
            if height[left] < height[right]:
                # the right side has a wall at least as tall as height[right],
                # so the water above "left" is decided by left_max alone
                if height[left] > left_max:
                    left_max = height[left]
                # water above this bar = how far it sits below the tallest wall on its left
                water = water + (left_max - height[left])
                left = left + 1
            else:
                # mirror image: the left side is at least as tall, so settle "right"
                if height[right] > right_max:
                    right_max = height[right]
                water = water + (right_max - height[right])
                right = right - 1
        return water

What the code is doing, line by line:

1. left = 0, right = len(height) - 1: one pointer at each end.
2. left_max = 0, right_max = 0, water = 0: the tallest bar seen from each side so far, and the running total of water.
3. while left < right: settle one bar per round until the pointers meet.
4. if height[left] < height[right]: the left bar is the lower one. Somewhere on the right there is a wall at least as tall as height[right], so the water above left is limited only by the tallest wall on its left, left_max.
5. if height[left] > left_max: left_max = height[left]: update the tallest-on-the-left.
6. water = water + (left_max - height[left]): the water above this bar is how far it sits below left_max. If this bar is itself the new tallest, that is 0.
7. left = left + 1: this bar is settled, move on.
8. The else branch is the exact mirror image for the right side, using right_max and moving right left.
9. return water.

Dry run on the example:

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] (LeetCode Example 1). Returns 6.

Edge cases to test:

• Fewer than 3 bars → 0.
• Monotonic heights (only rising or only falling) → 0.
• A deep valley between two tall walls, e.g. [5, 0, 0, 5] → 10.

Complexity: O(n) time, O(1) space (versus O(n) for the prefix-max/suffix-max arrays version).

Problem: After lower-casing and ignoring everything that isn't a letter or digit, does s read the same forwards and backwards?

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ s.length ≤ 2 * 10⁵ · s consists only of printable ASCII characters.

From brute force to the pattern: Building a cleaned, lower-cased copy and comparing it with its reverse is O(n) time but O(n) extra space. Two pointers skip junk characters in place and compare as they go: O(n) time, O(1) space.

Spot it: "Compare from both ends" → opposite-end pointers. No need to build a cleaned copy of the string.

Approach:

1. left = 0, right = len(s) − 1.
2. If s[left] isn't a letter or digit, move left right; if s[right] isn't, move right left.
3. Otherwise compare the lowercase characters; a mismatch means False.
4. Move both inward. If they meet or cross, it's a palindrome.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # one pointer at each end of the string
        left = 0
        right = len(s) - 1
        while left < right:
            left_char = s[left]
            right_char = s[right]
            if not left_char.isalnum():
                # a space or punctuation mark on the left: ignore it
                left = left + 1
            elif not right_char.isalnum():
                # a space or punctuation mark on the right: ignore it
                right = right - 1
            else:
                # both are letters/digits: compare them ignoring upper/lower case
                if left_char.lower() != right_char.lower():
                    return False
                # they match: move both pointers inward
                left = left + 1
                right = right - 1
        # the pointers met without finding a mismatch
        return True

What the code is doing, line by line:

1. left = 0, right = len(s) - 1: one pointer at each end of the string.
2. while left < right: compare characters until the pointers meet in the middle.
3. left_char = s[left], right_char = s[right]: the two characters we are looking at.
4. if not left_char.isalnum(): left = left + 1: isalnum() is True for letters and digits. A space or punctuation mark on the left is ignored by moving past it. Only one pointer moves this round; the loop checks again next round.
5. elif not right_char.isalnum(): right = right - 1: same on the right.
6. else: both are letters/digits. .lower() makes 'A' and 'a' equal. If they differ, return False immediately; otherwise move both pointers inward.
7. return True: no mismatch was found, so it is a palindrome.

Dry run on the example:

s = "race a car" (LeetCode Example 2). Returns False.

Edge cases to test:

• Only punctuation, e.g. " , . " → True (nothing left to mismatch).
• Digits next to letters, e.g. "0P" → False.
• Mixed case, e.g. "Aa" → True.

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

Problem: A sorted array; remove extra copies in place so every value appears at most twice. Return the new length k (the first k slots hold the result).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 3 * 10⁴ · -10⁴ ≤ nums[i] ≤ 10⁴ · nums is sorted in non-decreasing order.

From brute force to the pattern: Deleting extra copies from a Python list shifts everything after them: O(n²). A read/write pointer pair copies keepers forward in one pass. Comparing with the element two slots back is all the bookkeeping needed: O(n), O(1) space.

Spot it: "In place" + keep-or-drop each element → reader/writer pointers. Sorted, so copies sit next to each other.

Key insight: Compare with the value two slots back in the kept part, nums[write − 2]. If they're equal, keeping value would make three copies.

Approach:

1. write = 0 marks the next free slot.
2. For each position read (the reader), with value = nums[read]: keep it if write < 2 or value != nums[write − 2].
3. To keep it: nums[write] = value, then write = write + 1.
4. Return write.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # next free slot; positions 0 .. write-1 hold the kept part
        write = 0
        # "read" visits every position from left to right
        for read in range(len(nums)):
            value = nums[read]
            if write < 2:
                # the first two values can always be kept
                keep = True
            elif value != nums[write - 2]:
                # different from the value two slots back in the kept part,
                # so keeping it makes at most 2 copies
                keep = True
            else:
                # equal to the value two slots back: it would be a 3rd copy
                keep = False
            if keep:
                nums[write] = value      # copy it into the next free slot
                write = write + 1        # the kept part grew by one
        # "write" is how many values were kept
        return write

What the code is doing, line by line:

1. write = 0: the next free slot. Positions 0 .. write - 1 are the kept part.
2. for read in range(len(nums)): and value = nums[read]: the reader looks at every value once.
3. if write < 2: keep = True: with fewer than two values kept, any value may still appear twice.
4. elif value != nums[write - 2]: keep = True: look two slots back in the kept part. The kept part is sorted, so if that value equals value, the last two kept values are both value and this would be a 3rd copy. If it differs, keeping it is fine.
5. else: keep = False: a 3rd copy, drop it (the writer does not move).
6. if keep: nums[write] = value then write = write + 1: copy into the next free slot. This is safe because write is never ahead of read, so we never overwrite a value the reader still needs.
7. return write: the number of values kept.

Dry run on the example:

nums = [1, 1, 1, 2, 2, 3] (LeetCode Example 1). Returns 5; the first 5 slots are [1, 1, 2, 2, 3].

Edge cases to test:

• Length ≤ 2 → return the length unchanged.
• All the same value, e.g. [1, 1, 1, 1] → 2.
• No duplicates at all.

Complexity: O(n) time, O(1) space. Change the 2 to any k for "at most k copies".

Problem: Choose three numbers whose sum is as close as possible to target; return that sum.

Solve it on LeetCode ↗

Constraints: 3 ≤ nums.length ≤ 500 · -1000 ≤ nums[i] ≤ 1000 · -10⁴ ≤ target ≤ 10⁴

From brute force to the pattern: All triplets in O(n³). Sorting plus a two-pointer squeeze per fixed element covers the useful triplets in O(n²): when the sum is below target only moving left can help, and above it only moving right can.

Spot it: Same skeleton as 3Sum, but instead of looking for == 0 we track the smallest |sum − target|.

Approach:

1. Sort the array; start best_sum at the sum of the first three numbers.
2. Fix i; set left = i + 1, right = length − 1.
3. Compute current_sum; if it's closer to the target than best_sum, update best_sum.
4. current_sum < target → move left right; current_sum > target → move right left; equal → return it straight away.

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # sort so we can squeeze with two pointers
        nums.sort()
        length = len(nums)
        # start with any real sum of three numbers: the first three
        best_sum = nums[0] + nums[1] + nums[2]
        # i is the position of the first number of the three
        for i in range(length - 2):
            left = i + 1
            right = length - 1
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                # how far is this sum from the target, compared with the best so far?
                current_distance = abs(current_sum - target)
                best_distance = abs(best_sum - target)
                if current_distance < best_distance:
                    best_sum = current_sum
                if current_sum < target:
                    # too small: try a bigger second number
                    left = left + 1
                elif current_sum > target:
                    # too big: try a smaller third number
                    right = right - 1
                else:
                    # exactly the target: nothing can be closer
                    return current_sum
        return best_sum

What the code is doing, line by line:

1. nums.sort(), length = len(nums): sort so the squeeze works.
2. best_sum = nums[0] + nums[1] + nums[2]: we need a starting answer that is a real sum of three numbers, so take the first three.
3. for i in range(length - 2): fix the first number; left = i + 1, right = length - 1 squeeze the other two.
4. current_sum = nums[i] + nums[left] + nums[right]: the sum of the three candidates.
5. current_distance = abs(current_sum - target) and best_distance = abs(best_sum - target): abs drops the minus sign, so these are "how far from the target". If the current sum is closer, it becomes best_sum.
6. if current_sum < target: left = left + 1 (try a bigger sum); elif current_sum > target: right = right - 1 (try a smaller sum); else: return current_sum (distance 0 can't be beaten).
7. return best_sum after every i has been tried.

Dry run on the example:

nums = [-1, 2, 1, -4], target = 1 (LeetCode Example 1). Sorted: [-4, -1, 1, 2]; best_sum starts at -4 + -1 + 1 = -4. Returns 2.

Edge cases to test:

• An exact match → return immediately.
• Exactly three numbers → their sum.
• Large negative and positive values mixed.

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

Problem: Return every unique quadruplet [a, b, c, d] with a + b + c + d == target.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 200 · -10⁹ ≤ nums[i] ≤ 10⁹ · -10⁹ ≤ target ≤ 10⁹

From brute force to the pattern: Four nested loops: O(n⁴). Fixing two elements and squeezing the other two after sorting gives O(n³), with sorted order making duplicate handling easy.

Spot it: k-Sum: fix the first two numbers with loops, then squeeze the last two with opposite-end pointers.

Approach:

1. Sort the array.
2. Loop i, skipping repeated values; loop j > i, skipping repeated values.
3. Squeeze left, right on the rest, looking for total == target.
4. On a hit, record it, move both pointers, and skip repeated left values.

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # sort so we can squeeze with two pointers and skip duplicates easily
        nums.sort()
        length = len(nums)
        result = []
        # i = position of the first number
        for i in range(length - 3):
            # same first number as last time would only repeat quadruplets
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # j = position of the second number (always to the right of i)
            for j in range(i + 1, length - 2):
                # same second number as last time would only repeat quadruplets
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                # squeeze the last two numbers from both ends of what is left
                left = j + 1
                right = length - 1
                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]
                    if total < target:
                        left = left + 1        # too small: bigger third number
                    elif total > target:
                        right = right - 1      # too big: smaller fourth number
                    else:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        left = left + 1
                        right = right - 1
                        # skip copies of the third number so we don't repeat this answer
                        while left < right and nums[left] == nums[left - 1]:
                            left = left + 1
        return result

What the code is doing, line by line:

1. nums.sort(), length = len(nums), result = []: sort, remember the size, and prepare the answer list.
2. for i in range(length - 3): picks the first number, leaving room for three more. if i > 0 and nums[i] == nums[i - 1]: continue skips a first number we have already tried.
3. for j in range(i + 1, length - 2): picks the second number, to the right of i. if j > i + 1 and nums[j] == nums[j - 1]: continue skips a repeated second number (the j > i + 1 part makes sure we only compare with an earlier j, never with nums[i]).
4. left = j + 1, right = length - 1: squeeze the last two numbers from both ends of what is left.
5. total = nums[i] + nums[j] + nums[left] + nums[right]; too small → left = left + 1; too big → right = right - 1.
6. On a hit, result.append([...]), move both pointers, and the inner while moves left past copies of the third number.
7. return result.

Dry run on the example:

nums = [1, 0, -1, 0, -2, 2], target = 0 (LeetCode Example 1). Sorted: [-2, -1, 0, 0, 1, 2]. Returns [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]].

Edge cases to test:

• Sums that overflow 32-bit in other languages (Python is fine).
• Many duplicates, e.g. [2, 2, 2, 2, 2], target 8 → one quadruplet.
• Fewer than four numbers → [].

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

Problem: Each boat holds at most two people with total weight ≤ limit. What's the minimum number of boats to carry everyone?

Solve it on LeetCode ↗

Constraints: 1 ≤ people.length ≤ 5 * 10⁴ · 1 ≤ people[i] ≤ limit ≤ 3 * 10⁴

From brute force to the pattern: Trying all pairings is exponential. Greedy with two pointers on the sorted weights is optimal: the heaviest person must go now, and pairing them with the lightest person is the best chance of sharing. O(n log n) for the sort.

Spot it: Pair the lightest with the heaviest after sorting: a greedy opposite-end squeeze.

Key insight: The heaviest person must ride in some boat. Giving them the lightest partner (if one fits) is never worse than any other choice.

Approach:

1. Sort people.
2. lightest = index of the lightest person, heaviest = index of the heaviest.
3. If people[lightest] + people[heaviest] ≤ limit, the lightest boards too (lightest = lightest + 1).
4. The heaviest always boards (heaviest = heaviest - 1); count one boat.
5. Repeat while lightest ≤ heaviest (when they are equal, one person still needs a boat).

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        # sort by weight so the lightest is at the front and the heaviest at the back
        people.sort()
        lightest = 0                    # index of the lightest person still waiting
        heaviest = len(people) - 1      # index of the heaviest person still waiting
        boats = 0
        # when lightest == heaviest, one person is left and still needs a boat
        while lightest <= heaviest:
            if people[lightest] + people[heaviest] <= limit:
                # the lightest person fits in the same boat as the heaviest
                lightest = lightest + 1
            # the heaviest person always leaves on this boat
            heaviest = heaviest - 1
            boats = boats + 1
        return boats

What the code is doing, line by line:

1. people.sort(): lightest at the front, heaviest at the back.
2. lightest = 0, heaviest = len(people) - 1, boats = 0: indexes of the lightest and heaviest person still waiting, and the boat count.
3. while lightest <= heaviest: someone is still waiting. We use <= because when the two indexes are equal there is exactly one person left, and they still need a boat.
4. if people[lightest] + people[heaviest] <= limit: lightest = lightest + 1: if the lightest person fits alongside the heaviest, they ride together.
5. heaviest = heaviest - 1 and boats = boats + 1: the heaviest person always leaves on this boat (alone or with the lightest).
6. return boats.

Dry run on the example:

people = [3, 2, 2, 1], limit = 3 (LeetCode Example 2). Sorted: [1, 2, 2, 3]. Returns 3.

Edge cases to test:

• Everyone exactly at the limit → one boat each.
• Everyone pairs perfectly → n / 2 boats.
• A single person → 1.

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

Problem: Given two sorted arrays, return the median of all their numbers combined. The required time is O(log(m + n)).

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: Two sorted arrays → a two-pointer merge reaches the middle in O(m + n) (shown as findMedianMerge). To get logarithmic time, binary-search the cut point instead (see Modified Binary Search).

Key insight: Cut both arrays so that the left parts together hold half the numbers and every left number ≤ every right number. Then the median sits right at the cut.

Approach:

1. Make shorter the shorter list; half = (total_length + 1) // 2.
2. Binary-search cut_short = how many items of shorter go on the left; cut_long = half − cut_short come from longer.
3. The cut is valid when short_left ≤ long_right and long_left ≤ short_right (use ±∞ beyond the ends).
4. Odd total: median = the larger left value. Even: average of the larger left value and the smaller right value.
5. If short_left > long_right, take fewer from shorter (high = cut_short − 1); otherwise take more (low = cut_short + 1).

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # binary-search the SHORTER list, so the search is as small as possible
        if len(nums1) <= len(nums2):
            shorter = nums1
            longer = nums2
        else:
            shorter = nums2
            longer = nums1
        short_length = len(shorter)
        long_length = len(longer)
        total_length = short_length + long_length
        # how many numbers go into the combined LEFT half (the extra one goes left if odd)
        half = (total_length + 1) // 2
        # we search for cut_short = how many numbers of "shorter" go into the left half
        low = 0
        high = short_length
        while low <= high:
            cut_short = (low + high) // 2
            # the rest of the left half comes from "longer"
            cut_long = half - cut_short
            # the four numbers touching the two cuts (use -inf / +inf past the ends)
            if cut_short > 0:
                short_left = shorter[cut_short - 1]
            else:
                short_left = float("-inf")
            if cut_short < short_length:
                short_right = shorter[cut_short]
            else:
                short_right = float("inf")
            if cut_long > 0:
                long_left = longer[cut_long - 1]
            else:
                long_left = float("-inf")
            if cut_long < long_length:
                long_right = longer[cut_long]
            else:
                long_right = float("inf")
            if short_left <= long_right and long_left <= short_right:
                # valid cut: every number on the left is <= every number on the right
                biggest_left = max(short_left, long_left)
                if total_length % 2 == 1:
                    # odd count: the median is the biggest number of the left half
                    return float(biggest_left)
                # even count: average the two numbers around the cut
                smallest_right = min(short_right, long_right)
                return (biggest_left + smallest_right) / 2
            if short_left > long_right:
                # took too many from "shorter": move the cut left
                high = cut_short - 1
            else:
                # took too few from "shorter": move the cut right
                low = cut_short + 1
        # only reached if the inputs were not sorted
        return 0.0

    def findMedianMerge(self, nums1: List[int], nums2: List[int]) -> float:
        # The two-pointer version: merge until the middle, O(m + n).
        total_length = len(nums1) + len(nums2)
        i = 0                 # pointer into nums1
        j = 0                 # pointer into nums2
        previous = 0          # the value taken one step before "current"
        current = 0           # the latest value taken, in sorted order
        middle = total_length // 2
        steps = 0
        # take values in sorted order until we have taken position "middle"
        while steps <= middle:
            previous = current
            # decide which list holds the next smallest value
            if j >= len(nums2):
                take_from_first = True        # nums2 is used up
            elif i >= len(nums1):
                take_from_first = False       # nums1 is used up
            elif nums1[i] <= nums2[j]:
                take_from_first = True
            else:
                take_from_first = False
            if take_from_first:
                current = nums1[i]
                i = i + 1
            else:
                current = nums2[j]
                j = j + 1
            steps = steps + 1
        if total_length % 2 == 1:
            # odd count: the middle value itself
            return float(current)
        # even count: average of the two middle values
        return (previous + current) / 2

What the code is doing, line by line:

findMedianSortedArrays (binary search on the cut)

1. The first if / else names the shorter list shorter and the other longer, so the binary search runs over the smaller range.
2. short_length, long_length, total_length: the sizes. half = (total_length + 1) // 2 is how many numbers belong in the combined left half (// is whole-number division; with an odd count the extra number goes left).
3. low = 0, high = short_length: cut_short (how many numbers of shorter go left) can be anything from 0 to all of them.
4. while low <= high: try the middle choice: cut_short = (low + high) // 2, and the rest of the left half comes from longer: cut_long = half - cut_short.
5. The four if / else blocks read the numbers touching each cut: short_left / short_right and long_left / long_right. If a cut is at the very start or end there is no number there, so we use -inf / inf, which can never break the rule below.
6. if short_left <= long_right and long_left <= short_right: each list is already sorted on its own, so these two "cross" checks are all that's needed to know every left number ≤ every right number. Then the median is at the cut: biggest_left for an odd count, or the average of biggest_left and smallest_right for an even count.
7. if short_left > long_right: high = cut_short - 1: we took too many from shorter; try a smaller cut. else: low = cut_short + 1: too few; try a bigger cut.
8. return 0.0: only reachable if the inputs were not sorted.

findMedianMerge (the two-pointer merge)

1. i and j point into nums1 and nums2. current is the latest value taken in sorted order and previous the one before it. middle = total_length // 2.
2. while steps <= middle: take middle + 1 values in sorted order; the last one taken is the middle value.
3. previous = current: remember the value from the step before (needed for an even count).
4. The if / elif / else chain decides where the next smallest value is: if nums2 is used up take from nums1; if nums1 is used up take from nums2; otherwise take the smaller front value.
5. Take it into current and step that list's pointer forward; steps = steps + 1.
6. Odd count: the median is current. Even count: the average of previous and current.

Dry run on the example:

nums1 = [1, 2], nums2 = [3, 4] (LeetCode Example 2). Both have length 2, so shorter = [1, 2], longer = [3, 4], half = 2. findMedianSortedArrays returns 2.5 = (2 + 3) / 2.

And the merge version on nums1 = [1, 3], nums2 = [2] (LeetCode Example 1): total_length = 3, middle = 1, so it keeps taking values while steps <= 1. findMedianMerge returns 2.0 (odd count, so just current).

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: Binary search: O(log min(m, n)) time; merge: O(m + n). Both O(1) space.

Problem: nums is sorted. Remove the duplicates in place so each value appears once, keep the order, and return k, the number of unique values. The first k slots must hold them; the rest don't matter.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 3 * 10⁴ · -100 ≤ nums[i] ≤ 100 · nums is sorted in non-decreasing order.

From brute force to the pattern: Removing each duplicate from the list shifts the rest of it: O(n²). A reader/writer pointer pair rewrites the unique values to the front in one pass: O(n), O(1) space.

Spot it: "In place" + "sorted" + "remove" → two pointers moving the same direction: a fast read pointer scans everything and a slow write pointer marks where the next keeper goes.

Approach:

1. nums[0] is always kept, so start write = 1.
2. Move read from index 1 to the end.
3. Because the array is sorted, a new value is simply one that differs from the last value kept, nums[write − 1].
4. When it differs, copy it to nums[write] and advance write. Duplicates are just skipped.
5. write ends up equal to the number of unique values. Return it.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # nums[0] is always unique, so the next unique value goes to index 1
        write = 1
        for read in range(1, len(nums)):
            # sorted input: a new value is one that differs from the last value we kept
            if nums[read] != nums[write - 1]:
                nums[write] = nums[read]
                write = write + 1
        # write counts how many unique values sit at the front
        return write

What the code is doing, line by line:

1. write = 1: the first element can never be a duplicate, so it stays where it is.
2. for read in range(1, len(nums)): the reader looks at every other element exactly once.
3. if nums[read] != nums[write - 1]: nums[write - 1] is the last value we kept. Equal means duplicate (skip it); different means a brand-new value.
4. nums[write] = nums[read] copies the new value into the next free slot, and write = write + 1 moves the slot forward.
5. return write: everything before write is the unique, ordered prefix.

Dry run on the example:

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

Edge cases to test:

• A single element → 1.
• All the same, e.g. [1, 1, 1] → 1.
• No duplicates → n.

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

Problem: nums1 has length m + n: its first m values are sorted and the last n slots are zeros. nums2 holds n sorted values. Merge nums2 into nums1 in place so nums1 ends up sorted.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: nums1.length == m + n · nums2.length == n · 0 ≤ m, n ≤ 200 · 1 ≤ m + n ≤ 200 · -10⁹ ≤ nums1[i], nums2[j] ≤ 10⁹

From brute force to the pattern: Copying nums2 in and calling sort() is O((m + n) log(m + n)); merging into a new list costs O(m + n) extra space. Three pointers filling from the back merge in place in O(m + n) with O(1) space.

Spot it: Two sorted inputs → one pointer per array. Filling from the front would overwrite values of nums1 we still need, but the empty space is at the end, so fill backwards: always place the larger of the two tails.

Approach:

1. i points at the last real value of nums1 (m − 1), j at the last value of nums2 (n − 1), and write at the very last slot (m + n − 1).
2. While nums2 still has values (j ≥ 0): compare nums1[i] and nums2[j], copy the larger into nums1[write], and step that pointer left.
3. Move write left after every placement.
4. If nums2 runs out first, the rest of nums1 is already in place, so we can stop.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i = m - 1          # last real value of nums1
        j = n - 1          # last value of nums2
        write = m + n - 1  # last slot of nums1 (the empty space is at the end)
        # once nums2 is used up, whatever is left in nums1 is already in place
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                # nums1's tail is bigger: it belongs at the back
                nums1[write] = nums1[i]
                i = i - 1
            else:
                # nums2's tail is bigger (or nums1 is used up)
                nums1[write] = nums2[j]
                j = j - 1
            write = write - 1

What the code is doing, line by line:

1. i, j, write: three pointers that all start at the right end and move left.
2. while j >= 0: we only need to keep going while nums2 has values. Leftover nums1 values are already sitting in sorted position.
3. if i >= 0 and nums1[i] > nums2[j]: check i >= 0 first so we never read nums1[-1]. If nums1's tail is larger, it goes to write.
4. else: otherwise nums2[j] is larger or equal (or nums1 is exhausted), so it goes to write.
5. write = write - 1: the slot is filled; the next largest value goes one to the left.
6. The function returns nothing: LeetCode checks nums1 itself.

Dry run on the example:

nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3 (LeetCode Example 1). Result [1, 2, 2, 3, 5, 6].

j is now −1, so the loop stops. The [1, 2] at the front never had to move.

Edge cases to test:

• n = 0: nothing to merge.
• m = 0: copy nums2 entirely.
• Every nums2 value smaller than every nums1 value.

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

Problem: Reverse the list of characters s in place, using O(1) extra memory.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ s.length ≤ 10⁵ · s[i] is a printable ascii character.

From brute force to the pattern: s[::-1] builds a new list (O(n) extra space), which the problem forbids. Swapping from both ends in place does it with O(1) space.

Spot it: "Reverse" + "in place" → one pointer at each end; swap and walk inward until they meet.

Approach:

1. left = 0, right = len(s) − 1.
2. While left < right: swap s[left] and s[right].
3. Move left right and right left. When they meet (odd length) or cross (even length), every pair has been swapped.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        left = 0
        right = len(s) - 1
        while left < right:
            # swap the two ends using a temporary variable
            temp = s[left]
            s[left] = s[right]
            s[right] = temp
            # both pointers step toward the middle
            left = left + 1
            right = right - 1

What the code is doing, line by line:

1. left = 0, right = len(s) - 1: the first and last positions.
2. while left < right: stop when the pointers meet: the middle character of an odd-length list stays put.
3. temp = s[left] … s[right] = temp: a three-line swap. (Python's s[left], s[right] = s[right], s[left] does the same in one line.)
4. left = left + 1, right = right - 1: move inward to the next pair.
5. Nothing is returned: the list is changed in place, which is what LeetCode checks.

Dry run on the example:

s = ["h", "e", "l", "l", "o"] (LeetCode Example 1). Result ["o", "l", "l", "e", "h"].

Edge cases to test:

• One character → unchanged.
• Even length: the pointers cross without ever meeting.
• A palindrome → looks unchanged.

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

Problem: Return True if s is a subsequence of t: you can delete some (or no) characters of t, without reordering the rest, to get s.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 0 ≤ s.length ≤ 100 · 0 ≤ t.length ≤ 10⁴ · s and t consist only of lowercase English letters.

From brute force to the pattern: Generating subsequences of t is exponential. Two pointers scan both strings once, greedily matching each character of s at its earliest possible position in t: O(len(t)).

Spot it: Two sequences scanned left to right at different speeds → two pointers moving the same way. t is always consumed; s only moves forward when its current character is found.

Approach:

1. i points at the next character of s we still need to find.
2. Walk through every character of t.
3. If it equals s[i], we found that character in order: move i forward.
4. At the end, s is a subsequence exactly when every character was found, i.e. i == len(s).

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # i = index of the next character of s we still need to find
        i = 0
        for ch in t:
            # only compare while s still has characters left to match
            if i < len(s) and s[i] == ch:
                i = i + 1
        # every character of s was found, in order
        return i == len(s)

What the code is doing, line by line:

1. i = 0: nothing of s has been matched yet.
2. for ch in t: the second pointer walks t one character at a time.
3. if i < len(s) and s[i] == ch: guard first, so once all of s is matched we never read past its end. A match lets s move on to its next character.
4. Non-matching characters of t are simply the ones we "delete".
5. return i == len(s): true only if all of s was matched in order.

Dry run on the example:

s = "abc", t = "ahbgdc" (LeetCode Example 1). Returns True.

Edge cases to test:

• Empty s → True.
• s longer than t → False.
• Repeated letters, e.g. s = "aaa", t = "aa" → False.

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

Problem: nums is sorted in non-decreasing order and may contain negatives. Return the squares of each number, also sorted.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 10⁴ · -10⁴ ≤ nums[i] ≤ 10⁴ · nums is sorted in non-decreasing order.

From brute force to the pattern: Squaring everything and sorting is O(n log n). Because the largest absolute values sit at the ends, two pointers pick the next largest square in O(1), building the sorted result in O(n).

Spot it: Squaring breaks the order because big negatives become big positives. But the largest square must come from one of the two ends. Opposite-end pointers pick it, and we fill the answer from the back.

Approach:

1. left = 0, right = n − 1, and write = n − 1 (the last slot of the answer).
2. Compare abs(nums[left]) and abs(nums[right]). The bigger one gives the largest remaining square.
3. Put that square at result[write] and move the pointer it came from inward.
4. Move write left and repeat until left passes right.

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        left = 0
        right = n - 1
        # fill the answer from the largest square down to the smallest
        write = n - 1
        while left <= right:
            if abs(nums[left]) > abs(nums[right]):
                # a big negative on the left gives the larger square
                result[write] = nums[left] * nums[left]
                left = left + 1
            else:
                result[write] = nums[right] * nums[right]
                right = right - 1
            write = write - 1
        return result

What the code is doing, line by line:

1. result = [0] * n: a list of the right size to fill in.
2. left, right: the two ends of nums. The largest absolute value is always at one of them.
3. write = n - 1: we discover squares from biggest to smallest, so we fill the answer from the back.
4. while left <= right: use <= so the last remaining element (when the pointers meet) is also placed.
5. if abs(nums[left]) > abs(nums[right]): the left end wins: square it, put it at write, move left right. Otherwise the right end wins.
6. write = write - 1: the next square is the next smaller one.

Dry run on the example:

nums = [-4, -1, 0, 3, 10] (LeetCode Example 1). Returns [0, 1, 9, 16, 100].

Edge cases to test:

• All negative, e.g. [-3, -2, -1] → reversed squares.
• All non-negative → squares already sorted.
• Zeros in the middle.

Complexity: O(n) time, O(n) for the output (O(1) extra besides it).

Problem: Merge word1 and word2 by taking letters in alternating order, starting with word1. If one word is longer, append its remaining letters at the end.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ word1.length, word2.length ≤ 100 · word1 and word2 consist of lowercase English letters.

From brute force to the pattern: Building the string with += in a loop can be O(n²). Collecting letters in a list with two pointers and joining once is O(m + n).

Spot it: Two strings consumed side by side → one pointer per string, moving together.

Approach:

1. Start both pointers at 0 and collect letters in a list (building strings with += in a loop is slow).
2. While at least one word still has letters: take word1[i] if it exists, then word2[j] if it exists.
3. Join the list into a string.

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        i = 0
        j = 0
        parts = []
        # keep going while EITHER word still has letters
        while i < len(word1) or j < len(word2):
            if i < len(word1):
                parts.append(word1[i])
                i = i + 1
            if j < len(word2):
                parts.append(word2[j])
                j = j + 1
        return "".join(parts)

What the code is doing, line by line:

1. i, j: the next letter to take from each word.
2. parts = []: collect letters in a list; "".join(parts) at the end is O(n), while repeated string concatenation can be O(n²).
3. while i < len(word1) or j < len(word2): loop until both words are used up, so a longer word's tail is not lost.
4. if i < len(word1): take a letter from word1 only if it has one left; same for word2. This handles the leftover tail automatically.
5. return "".join(parts): glue the letters together.

Dry run on the example:

word1 = "ab", word2 = "pqrs" (LeetCode Example 2). Returns "apbqrs".

Edge cases to test:

• Equal lengths.
• One word much longer than the other.
• One-letter words.

Complexity: O(m + n) time and space.

Problem: Return the longest substring of s that reads the same forwards and backwards.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ s.length ≤ 1000 · s consist of only digits and English letters.

From brute force to the pattern: Checking every substring for being a palindrome is O(n³). Expanding around each centre reuses the matching work: each centre costs at most O(n), so O(n²) total with O(1) space.

Spot it: A palindrome is a mirror around its centre. Instead of squeezing two pointers inward, put them on a centre and walk them outward while the characters match. There are only 2n − 1 centres: every character (odd length) and every gap between two characters (even length).

Key insight: Checking every substring is O(n³). Growing from each centre reuses the matching work, so each centre costs at most O(n) and the whole thing is O(n²) with O(1) space.

Approach:

1. Keep the best palindrome found so far as a start index and a length.
2. For each index center, try two starting pairs: (center, center) for odd lengths and (center, center + 1) for even lengths.
3. While both pointers are inside the string and s[left] == s[right], move left one step left and right one step right.
4. When the loop stops, the palindrome is s[left + 1 : right], of length right − left − 1. Keep it if it beats the best.
5. Return the best slice.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        best_start = 0
        best_len = 0
        for center in range(len(s)):
            # odd length: centred ON a character; even length: centred BETWEEN two characters
            for left, right in ((center, center), (center, center + 1)):
                # spread outwards while both ends are inside the string and match
                while left >= 0 and right < len(s) and s[left] == s[right]:
                    left = left - 1
                    right = right + 1
                # the loop overshot by one on each side, so the palindrome is s[left+1 : right]
                length = right - left - 1
                if length > best_len:
                    best_len = length
                    best_start = left + 1
        return s[best_start:best_start + best_len]

What the code is doing, line by line:

1. best_start, best_len: where the longest palindrome so far begins and how long it is.
2. for center in range(len(s)): every index is a possible middle.
3. for left, right in ((center, center), (center, center + 1)): two tries per centre. (c, c) grows odd palindromes like "bab"; (c, c + 1) grows even ones like "abba".
4. while left >= 0 and right < len(s) and s[left] == s[right]: keep expanding while the ends are valid and equal. The bounds are checked first so s[-1] is never read by mistake.
5. left = left - 1, right = right + 1: one step outward on each side.
6. length = right - left - 1: the loop exits one step past the palindrome on both sides, so the real span is left + 1 .. right − 1.
7. if length > best_len: remember the new best; best_start = left + 1 undoes the overshoot.
8. return s[best_start:best_start + best_len]: slice out the winner.

Dry run on the example:

s = "babad" (LeetCode Example 1). Returns "bab" ("aba" is equally long and also accepted).

Edge cases to test:

• A single character → itself.
• An even-length palindrome, e.g. "cbbd" → "bb" (needs the gap centres).
• All the same character, e.g. "aaaa" → the whole string.

Complexity: O(n²) time (2n − 1 centres, each expanding up to n), O(1) extra space.

Problem: Rotate nums to the right by k steps, in place. For example [1,2,3,4,5,6,7], k = 3 becomes [5,6,7,1,2,3,4].

Solve it on LeetCode ↗ · Video walkthrough ↗

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

From brute force to the pattern: Rotating one step k times is O(n · k); copying into a new array uses O(n) space. Three in-place reversals give the rotation in O(n) time and O(1) space.

Spot it: "In place" with O(1) extra space rules out building a new array. Reversing a range in place is the classic opposite-end two-pointer swap, and three reversals produce a rotation.

Key insight: Rotating right by k moves the last k values to the front. Reverse the whole array (the last k are now first, but backwards), then reverse the first k and the rest separately to fix their order.

Approach:

1. k = k % n: rotating by n changes nothing, so only the remainder matters.
2. Reverse the whole array.
3. Reverse the first k values.
4. Reverse the remaining n − k values.
5. Each reversal swaps left and right, then moves them toward each other until they meet.

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        # rotating by n is a full circle, so only the remainder matters
        k = k % n

        def reverse(left, right):
            # classic opposite-ends two pointers: swap, then step inward
            while left < right:
                temp = nums[left]
                nums[left] = nums[right]
                nums[right] = temp
                left = left + 1
                right = right - 1

        reverse(0, n - 1)  # whole array: the last k values move to the front (backwards)
        reverse(0, k - 1)  # put the first k back in order
        reverse(k, n - 1)  # put the rest back in order

What the code is doing, line by line:

1. k = k % n: with n = 7, rotating by 10 is the same as rotating by 3. Without this, k − 1 could point past the end.
2. def reverse(left, right): a helper that reverses nums[left..right] in place.
3. while left < right: swap the two ends using a temporary variable, then move both pointers inward until they meet.
4. reverse(0, n - 1): the last k values are now at the front, but in reverse order, and so is everything else.
5. reverse(0, k - 1) and reverse(k, n - 1): fix the order inside each block.

Dry run on the example:

nums = [1, 2, 3, 4, 5, 6, 7], k = 3 (LeetCode Example 1). Result [5, 6, 7, 1, 2, 3, 4].

Edge cases to test:

• k ≥ n: use k % n (e.g. k = n changes nothing).
• k = 0.
• A single element.

Complexity: O(n) time (every element is swapped at most twice), O(1) extra space.

Problem: Rearrange nums in place into the next lexicographically greater permutation. If it's already the largest (sorted descending), wrap around to the smallest (sorted ascending).

Solve it on LeetCode ↗

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

From brute force to the pattern: Generating every permutation, sorting them and finding the next one is O(n! · n). All the work is in the tail: the longest descending suffix can't be increased on its own, so you change the element just before it, then reset the suffix to its smallest order. That's three linear passes: O(n) time, O(1) space.

Spot it: "Next greater arrangement", in place, O(1) extra memory. Think of the digits of a number: to make the smallest bigger number you change the digits as far right as possible. That's a scan from the right plus two-pointer swaps and an in-place reverse.

Why not another pattern? Backtracking could list all permutations in order and pick the next one, but that's O(n!). Sorting the tail is O(n log n); since the tail is always in descending order, reversing it with two pointers does the same job in O(n).

Key insight: Scanning from the right, the suffix is non-increasing until some nums[i] < nums[i + 1] (the pivot). That suffix is already the largest arrangement of its values, so the change must happen at i: swap nums[i] with the smallest value in the suffix that is bigger than it (the rightmost one), then make the suffix as small as possible by reversing it.

Approach:

1. From the right, find the first index i with nums[i] < nums[i + 1]. If there's none, the whole array is descending: reverse it and stop.
2. From the right again, find the first j with nums[j] > nums[i] (the smallest bigger value in the suffix).
3. Swap nums[i] and nums[j]. The suffix after i is still in descending order.
4. Reverse the suffix nums[i + 1:] with two pointers so it becomes ascending: the smallest possible tail.

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        # 1) find the pivot: the rightmost i with nums[i] < nums[i + 1]
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i = i - 1  # still descending from the right: keep moving left
        if i >= 0:
            # 2) find the rightmost value bigger than the pivot
            j = n - 1
            while nums[j] <= nums[i]:
                j = j - 1  # too small: keep moving left
            # 3) swap them: the prefix up to i is now as small as possible but bigger
            nums[i], nums[j] = nums[j], nums[i]
        # 4) reverse the tail after i so it becomes the smallest arrangement
        left = i + 1
        right = n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]  # swap the two ends
            left = left + 1
            right = right - 1

What the code is doing, line by line:

1. i = n - 2 and the first while: walk left while the array is non-increasing from the right. Stop at the pivot i where nums[i] < nums[i + 1].
2. if i >= 0: a pivot exists. (If i became −1, the array was the last permutation and we only reverse everything.)
3. Second while: j moves left from the end until nums[j] > nums[i]. Because the suffix is descending, the first such j is the smallest value larger than the pivot.
4. nums[i], nums[j] = nums[j], nums[i]: Python swaps both values in one statement.
5. left = i + 1, right = n - 1 and the last loop: reverse the suffix in place, turning descending into ascending.
6. The function returns nothing: LeetCode checks nums after the call.

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 the largest, e.g. [3, 2, 1] → [1, 2, 3].
• Duplicates, e.g. [1, 5, 1] → [5, 1, 1] (use ≥/≤ in the scans so equal values are skipped).
• A single element → unchanged.

Complexity: O(n) time (at most three linear scans), O(1) extra space.

Problem: Compare two version strings such as "1.01" and "1.001". Revisions are separated by dots and compared as integers (leading zeros ignored, missing revisions are 0). Return −1, 1 or 0.

Solve it on LeetCode ↗

Constraints: 1 ≤ version1.length, version2.length ≤ 500 · version1 and version2 only contain digits and '.'. · version1 and version2 are valid version numbers. · All the given revisions in version1 and version2 can be stored in a 32-bit integer.

From brute force to the pattern: Padding both versions to the same number of revisions and comparing them as strings fails on leading zeros and on 10 vs 9. Parsing each revision as an integer with two pointers handles both, in one pass and O(1) space.

Spot it: Two sequences compared position by position, possibly of different lengths: one pointer walking each string, reading one revision number at a time.

Why not another pattern? Splitting both strings on . is simpler and fine here (O(n) space). The two-pointer scan avoids building the lists and stops at the first difference. String comparison is wrong: "10" < "9" as strings.

Approach:

1. Keep a pointer i into version1 and j into version2.
2. While either string has characters left: read the next revision from each (digits up to the next dot) as an integer; an exhausted string gives 0.
3. If the two numbers differ, return −1 or 1. Otherwise skip the dots and continue.
4. If everything matched, return 0.

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        i = 0
        j = 0
        while i < len(version1) or j < len(version2):
            a = 0  # next revision of version1 (0 if it has run out)
            while i < len(version1) and version1[i] != ".":
                a = a * 10 + int(version1[i])  # build the number digit by digit
                i = i + 1
            b = 0  # next revision of version2
            while j < len(version2) and version2[j] != ".":
                b = b * 10 + int(version2[j])
                j = j + 1
            if a != b:
                return -1 if a < b else 1  # the first different revision decides
            i = i + 1  # skip the dot
            j = j + 1
        return 0

What the code is doing, line by line:

1. while i < len(version1) or j < len(version2): keep going while either version has revisions left.
2. The inner loops read one revision each, turning digits into a number ("01" becomes 1, so leading zeros vanish).
3. If a string is exhausted its inner loop doesn't run, so its revision stays 0, exactly the rule for missing revisions.
4. if a != b: return ...: the first differing revision decides the comparison.
5. i = i + 1, j = j + 1: step over the dots (stepping past the end is harmless).

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:

• Leading zeros, e.g. "1.01" vs "1.001" → 0.
• Different lengths with trailing zeros, e.g. "1.0" vs "1.0.0.0" → 0.
• "0.1" vs "1.1" → −1.

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

Problem: Compress the character array in place: each run of a repeated character becomes the character followed by the run length (only if longer than 1, written digit by digit). Return the new length.

Solve it on LeetCode ↗

Constraints: 1 ≤ chars.length ≤ 2000 · chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.

From brute force to the pattern: Building the compressed string in a new list and copying it back is easy but uses O(n) extra space. A read/write pair works in place because the output is never longer than the part of the input already read.

Spot it: "In place" + rewriting a shorter version of the array → a fast read pointer and a slow write pointer moving the same way.

Why not another pattern? Building a new string and copying it back uses O(n) space, which the problem forbids. A hash map of counts loses the order and the run boundaries.

Approach:

1. read finds the end of the current run of equal characters.
2. Write the character at write; if the run is longer than 1, write each digit of its length.
3. Continue from the start of the next run. write is the new length.

class Solution:
    def compress(self, chars: List[str]) -> int:
        write = 0  # where the next output character goes
        read = 0   # start of the current run
        while read < len(chars):
            letter = chars[read]
            run_end = read
            while run_end < len(chars) and chars[run_end] == letter:
                run_end = run_end + 1  # extend the run of equal letters
            count = run_end - read
            chars[write] = letter  # write the letter once
            write = write + 1
            if count > 1:
                for digit in str(count):
                    chars[write] = digit  # then its count, digit by digit
                    write = write + 1
            read = run_end  # jump to the next run
        return write

What the code is doing, line by line:

1. write, read: the slow and fast pointers. write never passes read, because a run of length k produces at most 1 + len(str(k)) ≤ k characters.
2. Inner while: run_end stops at the first different character, so count = run_end - read is the run length.
3. chars[write] = letter: every run writes its letter.
4. for digit in str(count): a count like 12 is written as '1', '2'.
5. read = run_end: the next run starts right after this one; return write is the compressed length.

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 single character → 1.
• A run longer than 9, e.g. 12 'b's → ['b', '1', '2'].
• No repeats at all → unchanged length.

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

Problem: Return the number of unique pairs (nums[i], nums[j]) with i != j whose difference is exactly k.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁴ · -10⁷ ≤ nums[i] ≤ 10⁷ · 0 ≤ k ≤ 10⁷

From brute force to the pattern: Comparing all pairs and putting the matches into a set is O(n²). After sorting, each pointer only moves forward, so the scan is O(n), plus the sort.

Spot it: A pair condition on a difference: after sorting, the difference between nums[right] and nums[left] grows when right moves and shrinks when left moves, so two pointers moving in the same direction can find every pair.

Why not another pattern? A hash-map version (count values; for k = 0 count values seen twice, else check x + k) is also O(n) and a fine alternative. Checking all pairs is O(n²).

Approach:

1. Sort the array.
2. Keep left = 0, right = 1. Compare nums[right] − nums[left] with k.
3. Too small → move right. Too big → move left (keep left < right).
4. Equal → count it, then move left past all copies of nums[left] so the pair isn't counted again.

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        nums = sorted(nums)
        count = 0
        left = 0
        right = 1
        while right < len(nums):
            if left == right:
                right = right + 1  # the two pointers must point at different elements
                continue
            diff = nums[right] - nums[left]
            if diff < k:
                right = right + 1  # need a bigger difference
            elif diff > k:
                left = left + 1  # need a smaller difference
            else:
                count = count + 1  # found a unique pair
                value = nums[left]
                while left < len(nums) and nums[left] == value:
                    left = left + 1  # skip copies so this pair isn't counted again
        return count

What the code is doing, line by line:

1. nums = sorted(nums): sorting makes the difference move predictably with the pointers.
2. if left == right: a pair needs two different indices.
3. diff < k: moving right to a larger value increases the difference; diff > k: moving left decreases it.
4. On a match, skip every copy of nums[left]; that guarantees each value pair is counted once (this also handles k = 0, which needs two equal values).

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: only values that appear at least twice count, e.g. [1, 1, 1] → 1.
• Duplicates that would create the same pair twice, e.g. [3, 1, 4, 1, 5], k = 2 → 2.
• Negative numbers.

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

Problem: Return the smallest integer greater than n that uses exactly the same digits, or −1 if none exists or it doesn't fit in a signed 32-bit integer.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 2³¹ - 1

From brute force to the pattern: Trying every permutation of the digits and picking the smallest larger one is O(d! · d). Next Permutation finds it in O(d).

Spot it: "Smallest greater arrangement of the same digits" is exactly Next Permutation applied to the digit list.

Why not another pattern? Generating all permutations of the digits is O(d!). Sorting is unnecessary because the tail is already in descending order and only needs reversing.

Approach:

1. Turn n into a list of digits.
2. Find the pivot i (rightmost digits[i] < digits[i + 1]). If there is none, return −1.
3. Swap it with the rightmost digit larger than it, then reverse the tail after i.
4. Convert back; return −1 if the result exceeds 2³¹ − 1.

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        digits = list(str(n))
        i = len(digits) - 2
        while i >= 0 and digits[i] >= digits[i + 1]:
            i = i - 1  # find the pivot from the right
        if i < 0:
            return -1  # digits are in descending order: no bigger number
        j = len(digits) - 1
        while digits[j] <= digits[i]:
            j = j - 1  # rightmost digit bigger than the pivot
        digits[i], digits[j] = digits[j], digits[i]
        left = i + 1
        right = len(digits) - 1
        while left < right:
            digits[left], digits[right] = digits[right], digits[left]  # reverse the tail
            left = left + 1
            right = right - 1
        result = int("".join(digits))
        return result if result < 2 ** 31 else -1  # must fit in 32 bits

What the code is doing, line by line:

1. digits = list(str(n)): work on the digits as characters; comparing '3' < '5' works digit by digit.
2. The first loop finds the pivot exactly as in Next Permutation. No pivot means the digits are already the largest arrangement.
3. The second loop finds the smallest digit bigger than the pivot (it's the rightmost one, since the tail is descending).
4. Swap, then reverse the tail with two pointers to make it as small as possible.
5. result < 2 ** 31: LeetCode requires a 32-bit result; Python itself wouldn't overflow.

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:

• Digits in descending order, e.g. 21 → −1.
• Overflow, e.g. 2147483486 → −1.
• Repeated digits, e.g. 12443322 → 13222344.

Complexity: O(d) time and space for d digits (at most 10).

Problem: Count the triplets in nums that can form a triangle (the sum of any two sides is greater than the third).

Solve it on LeetCode ↗

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

From brute force to the pattern: Checking every triplet is O(n³). Sorting reduces the triangle rule to one inequality, and fixing the longest side lets two pointers count all valid pairs in O(n) per side: O(n²) total.

Spot it: With sides sorted a ≤ b ≤ c, the only condition that can fail is a + b > c. Fixing c turns it into "count pairs with sum > c" in a sorted prefix: a classic opposite-end two-pointer count.

Why not another pattern? Three nested loops are O(n³). Binary search for each pair is O(n² log n). Two pointers count a whole block of pairs at once, giving O(n²).

Approach:

1. Sort the array.
2. For each index k (the longest side), set left = 0, right = k − 1.
3. If nums[left] + nums[right] > nums[k], every left' from left to right − 1 also works with right: add right − left, move right left.
4. Otherwise move left right to increase the sum.

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums = sorted(nums)
        count = 0
        for k in range(len(nums) - 1, 1, -1):
            longest = nums[k]  # fix the longest side
            left = 0
            right = k - 1
            while left < right:
                if nums[left] + nums[right] > longest:
                    count = count + (right - left)  # every left..right-1 also works with this right
                    right = right - 1
                else:
                    left = left + 1  # the sum is too small: use a longer short side
        return count

What the code is doing, line by line:

1. nums = sorted(nums): with a ≤ b ≤ c, only a + b > c needs checking.
2. for k in range(len(nums) - 1, 1, -1): each element in turn plays the longest side.
3. count + (right - left): if the smallest candidate nums[left] already works with nums[right], all larger ones in between work too.
4. else: left = left + 1: the pair is too short, so increase the smaller side.

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:

• Zeros can't form a triangle (0 + b > c fails when b ≤ c).
• Fewer than three numbers → 0.
• Equal sides, e.g. [2, 2, 2] → 1.

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

Problem: Return True if there are integers a and b with a² + b² = c.

Solve it on LeetCode ↗

Constraints: 0 ≤ c ≤ 2³¹ - 1

From brute force to the pattern: Trying every pair (a, b) up to √c is O(c). Since squares are sorted, two pointers find a pair in O(√c).

Spot it: The squares 0², 1², …, r² (with r = ⌊√c⌋) form a sorted list, and you want two of them adding up to c: Two Sum II with opposite-end pointers.

Why not another pattern? Checking every a and computing whether c − a² is a perfect square is also O(√c) and fine. Trying all pairs (a, b) is O(c).

Approach:

1. left = 0, right = isqrt(c).
2. If left² + right² == c, return True.
3. If the sum is too small, increase left; if too big, decrease right.
4. Stop when left > right.

from math import isqrt

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        left = 0
        right = isqrt(c)  # the largest b with b * b <= c
        while left <= right:
            total = left * left + right * right
            if total == c:
                return True
            if total < c:
                left = left + 1  # need a bigger sum
            else:
                right = right - 1  # need a smaller sum
        return False

What the code is doing, line by line:

1. isqrt(c): the integer square root, so right² never exceeds c.
2. while left <= right: a and b may be equal (e.g. 2 = 1² + 1²).
3. The comparisons move exactly one pointer, like Two Sum II on a sorted list of squares.

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:

• c = 0 → True (0² + 0²).
• Perfect squares, e.g. c = 4 → True.
• Large c near 2³¹ − 1 (use isqrt, not floating-point sqrt).

Complexity: O(√c) time, O(1) space.

Problem: A move replaces "XL" with "LX" (an L moves left) or "RX" with "XR" (an R moves right). Can start be turned into result?

Solve it on LeetCode ↗

Constraints: 1 ≤ start.length ≤ 10⁴ · start.length == result.length · Both start and result will only consist of characters in 'L', 'R', and 'X'.

From brute force to the pattern: Simulating all possible moves with BFS explores exponentially many strings. Two invariants (same piece order, allowed direction per piece) characterise reachability, so a single two-pointer scan decides it.

Spot it: Pieces can't pass each other, so the sequence of Ls and Rs (ignoring X) must be identical. Matching the pieces in order means one pointer per string, each skipping the Xs.

Why not another pattern? BFS over string states is exponential. The invariant (same piece order, L never moves right, R never moves left) is checkable in one two-pointer pass.

Approach:

1. Move i in start and j in result to their next non-X characters.
2. If one string has a piece and the other doesn't, or the pieces differ, return False.
3. An L can only move left: its position in start must be ≥ its position in result. An R must have i ≤ j.
4. Advance both and repeat; return True at the end.

class Solution:
    def canTransform(self, start: str, result: str) -> bool:
        n = len(start)
        i = 0
        j = 0
        while i < n or j < n:
            while i < n and start[i] == "X":
                i = i + 1  # skip blanks in start
            while j < n and result[j] == "X":
                j = j + 1  # skip blanks in result
            if i == n or j == n:
                return i == n and j == n  # both must run out of pieces together
            if start[i] != result[j]:
                return False  # pieces can't pass each other, so the order must match
            if start[i] == "L" and i < j:
                return False  # an L would have to move right
            if start[i] == "R" and i > j:
                return False  # an R would have to move left
            i = i + 1
            j = j + 1
        return True

What the code is doing, line by line:

1. The two inner while loops skip Xs, so i and j land on the next piece of each string.
2. if i == n or j == n: one string ran out of pieces; that's fine only if the other did too.
3. start[i] != result[j]: the k-th piece must be the same letter in both strings.
4. L with i < j or R with i > j: the piece would have to move in a forbidden direction.

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 pieces at all → True.
• Different numbers of pieces → False.
• start = "X", result = "L" → False.

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

Problem: Count index triples i < j < k with arr[i] + arr[j] + arr[k] == target, modulo 10⁹ + 7.

Solve it on LeetCode ↗

Constraints: 3 ≤ arr.length ≤ 3000 · 0 ≤ arr[i] ≤ 100 · 0 ≤ target ≤ 300

From brute force to the pattern: Three nested loops are O(n³), about 27·10⁹ steps for n = 3000. Fixing one index and squeezing the other two is O(n²); counting runs of equal values keeps it correct when values repeat.

Spot it: A triplet-sum condition on an array: fix the first element and squeeze the other two from both ends of a sorted array. Because indices (not values) are counted, runs of equal values have to be counted with combinatorics.

Why not another pattern? Values are only 0..100, so counting by value and enumerating value triples is another neat O(101²) solution. Three nested loops (O(n³)) are too slow for n = 3000.

Approach:

1. Sort the array. Fix i; look for pairs in i + 1 .. n − 1 summing to target − arr[i] with left and right.
2. If the pair sum is too small, move left; too big, move right.
3. On a match with arr[left] != arr[right]: count the run of arr[left] values and the run of arr[right] values; add their product and skip both runs.
4. On a match with equal values: all m = right − left + 1 elements are the same, so add m·(m−1)/2 and stop.

class Solution:
    def threeSumMulti(self, arr: List[int], target: int) -> int:
        MOD = 10 ** 9 + 7
        arr = sorted(arr)
        n = len(arr)
        answer = 0
        for i in range(n):
            need = target - arr[i]  # the other two must add up to this
            left = i + 1
            right = n - 1
            while left < right:
                pair = arr[left] + arr[right]
                if pair < need:
                    left = left + 1
                elif pair > need:
                    right = right - 1
                elif arr[left] != arr[right]:
                    left_count = 1
                    while left + 1 < right and arr[left + 1] == arr[left]:
                        left = left + 1  # extend the run of equal left values
                        left_count = left_count + 1
                    right_count = 1
                    while right - 1 > left and arr[right - 1] == arr[right]:
                        right = right - 1  # extend the run of equal right values
                        right_count = right_count + 1
                    answer = answer + left_count * right_count  # every left copy pairs with every right copy
                    left = left + 1
                    right = right - 1
                else:
                    m = right - left + 1  # everything between is the same value
                    answer = answer + m * (m - 1) // 2  # choose any 2 of them
                    break
        return answer % MOD

What the code is doing, line by line:

1. need = target - arr[i]: the remaining pair must sum to need.
2. Too-small / too-big moves are the usual sorted two-pointer squeeze.
3. Different values on a match: count the run lengths on both sides; each combination is a distinct index pair.
4. Equal values on a match: every index between left and right holds that value, so any 2 of the m work: m·(m−1)/2.
5. answer % MOD at the end (Python integers don't overflow, so one final % 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:

• All values equal, e.g. [1, 1, 1, 1], target = 3 → 4.
• Many duplicates, e.g. [1, 1, 2, 2, 2, 2], target = 5 → 12.
• No valid triple → 0.

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

Problem: A box is an m × n grid of stones '#', obstacles '*' and empty cells '.'. Rotate it 90° clockwise; gravity then pulls stones down until they hit an obstacle, another stone or the floor. Return the rotated box.

Solve it on LeetCode ↗

Constraints: m == boxGrid.length · n == boxGrid[i].length · 1 ≤ m, n ≤ 500 · boxGrid[i][j] is either '#', '*', or '.'.

From brute force to the pattern: Moving each stone one cell at a time until it stops costs O(n²) per row. A write pointer drops every stone directly into its final slot, so each row takes one pass.

Spot it: After rotating clockwise, "down" is the right end of each original row. So in each row, stones slide right until an obstacle: a read pointer scanning from the right and a write pointer marking where the next stone lands.

Why not another pattern? Simulating gravity one cell at a time repeats work (O(n²) per row). Rotating first and then simulating gravity column by column is the same idea done twice. The write pointer handles each row in one pass.

Approach:

1. For each row, set empty = n − 1 (the rightmost free spot) and scan c from right to left.
2. An obstacle '*' resets empty = c − 1 (stones can't pass it).
3. A stone '#' moves to empty: set row[c] = '.', row[empty] = '#', then empty -= 1.
4. Rotate: cell (r, c) of the box goes to (c, m − 1 − r) of the result.

class Solution:
    def rotateTheBox(self, boxGrid: List[List[str]]) -> List[List[str]]:
        m = len(boxGrid)
        n = len(boxGrid[0])
        for row in boxGrid:
            empty = n - 1  # where the next falling stone lands
            for c in range(n - 1, -1, -1):
                if row[c] == "*":
                    empty = c - 1  # an obstacle: stones stop just before it
                elif row[c] == "#":
                    row[c] = "."  # the stone leaves its cell ...
                    row[empty] = "#"  # ... and lands as far right as possible
                    empty = empty - 1
        rotated = [["."] * m for _ in range(n)]
        for r in range(m):
            for c in range(n):
                rotated[c][m - 1 - r] = boxGrid[r][c]  # 90 degrees clockwise
        return rotated

What the code is doing, line by line:

1. empty = n - 1: before rotating, gravity points to the right end of every row.
2. Scanning right to left, '*' sets the landing spot just left of the obstacle.
3. For a stone, clear its cell first and then write it at empty (if they're the same cell, the stone simply stays).
4. rotated[c][m - 1 - r] = boxGrid[r][c]: the standard clockwise rotation; the result is n × m.

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 row with no obstacles: all stones pile up at the right end.
• A stone directly next to an obstacle stays put.
• A single row → the output is a single column.

Complexity: O(m · n) time, O(m · n) for the output.

Problem: nums has equally many positive and negative numbers. Rearrange it so signs alternate, starting with a positive, while keeping the original order within each sign.

Solve it on LeetCode ↗

Constraints: 2 ≤ nums.length ≤ 2 * 10⁵ · nums.length is even · 1 ≤ |nums[i]| ≤ 10⁵ · nums consists of equal number of positive and negative integers.

From brute force to the pattern: Repeatedly searching for the next number of the needed sign is O(n²). Writing each number straight into its slot with two pointers is one pass.

Spot it: Two interleaved output streams: one write pointer for even positions and one for odd positions, both moving forward.

Why not another pattern? Splitting into two lists and zipping them back is equally O(n) (with two extra lists). Sorting would break the relative order.

Approach:

1. Create result of the same length; pos = 0, neg = 1.
2. Scan nums in order: a positive goes to result[pos] (then pos += 2), a negative to result[neg] (then neg += 2).

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        result = [0] * len(nums)
        pos = 0  # next even index (positives)
        neg = 1  # next odd index (negatives)
        for x in nums:
            if x > 0:
                result[pos] = x
                pos = pos + 2  # skip over the slot reserved for a negative
            else:
                result[neg] = x
                neg = neg + 2
        return result

What the code is doing, line by line:

1. pos and neg are write pointers into the even and odd slots.
2. Scanning nums once keeps each sign in its original order, as required.
3. Each pointer jumps by 2 because the slots in between belong to the other sign.

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:

• Two elements, e.g. [-1, 1] → [1, -1].
• All positives first, then all negatives.
• Already alternating.

Complexity: O(n) time, O(n) for the output.

Problem: Buses depart at buses[i], passengers arrive at passengers[j], each bus takes at most capacity waiting passengers (earliest first). You may arrive at any minute not already used by another passenger. What's the latest time you can arrive and still board?

Solve it on LeetCode ↗

Constraints: n == buses.length · m == passengers.length · 1 ≤ n, m, capacity ≤ 10⁵ · 2 ≤ buses[i], passengers[i] ≤ 10⁹ · Each element in buses is unique. · Each element in passengers is unique.

From brute force to the pattern: Trying every possible arrival minute and re-simulating the boarding is far too slow (times go up to 10⁹). One simulation pinpoints the latest feasible minute, and a short backward walk avoids taken minutes.

Spot it: Two sorted timelines (buses and passengers) processed together: a pointer over passengers advances as each bus fills. The answer depends only on the last bus, so after the simulation, step back from the latest possible time.

Why not another pattern? Binary search on your arrival time with a full simulation per guess works but is O((n + m) log T). The direct simulation plus a backward scan is linear after sorting.

Approach:

1. Sort both arrays. For each bus, board waiting passengers (passengers[j] ≤ bus) until it's full; j moves forward.
2. Look at the last bus: if it has a free seat, the latest candidate is its departure time; otherwise it's the time of the last passenger who boarded it.
3. Move the candidate one minute earlier while it collides with an existing passenger (walking k back over the boarded passengers).

class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses = sorted(buses)
        passengers = sorted(passengers)
        j = 0  # next passenger who hasn't boarded
        count = 0
        for bus in buses:
            count = 0  # seats used on this bus
            while j < len(passengers) and passengers[j] <= bus and count < capacity:
                j = j + 1  # this passenger boards
                count = count + 1
        k = j - 1  # last passenger who boarded (on any bus)
        # free seat on the last bus: arrive when it leaves; full: arrive with the last boarder
        time = buses[-1] if count < capacity else passengers[k]
        while k >= 0 and passengers[k] == time:
            time = time - 1  # that minute is taken: try one minute earlier
            k = k - 1
        return time

What the code is doing, line by line:

1. Sorting makes boarding a simple forward scan: passengers board in arrival order, buses leave in time order.
2. After the loop, count is how many boarded the last bus and j is the number of passengers who boarded at all.
3. A free seat means arriving exactly at the last departure works; a full bus means you must beat its last boarder.
4. The backward while skips minutes already used by boarded passengers (their times are consecutive in the sorted list).

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 last bus isn't full: the answer can be its departure time.
• Several passengers arrive in consecutive minutes right before the candidate.
• Passengers who arrive after the last bus never board.

Complexity: O(n log n + m log m) for the sorts, then O(n + m).

Problem: Strings contain 'L', 'R' and blanks '_'. An L can move left into a blank, an R can move right into a blank. Can start be turned into target?

Solve it on LeetCode ↗

Constraints: n == start.length == target.length · 1 ≤ n ≤ 10⁵ · start and target consist of the characters 'L', 'R', and '_'.

From brute force to the pattern: Exploring move sequences is exponential. The two invariants (piece order and direction) make one linear scan enough.

Spot it: Pieces never pass each other, so match the k-th piece of both strings with two pointers that skip blanks.

Why not another pattern? Simulating moves or searching over states is exponential; the order-and-direction invariant decides it in one pass.

Approach:

1. Advance i and j to the next piece in start and target.
2. If only one string has a piece left, or the pieces differ, return False.
3. L needs i ≥ j (it can only move left); R needs i ≤ j.
4. Advance both and continue.

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        n = len(start)
        i = 0
        j = 0
        while i < n or j < n:
            while i < n and start[i] == "_":
                i = i + 1  # skip blanks in start
            while j < n and target[j] == "_":
                j = j + 1  # skip blanks in target
            if i == n or j == n:
                return i == n and j == n  # both must run out of pieces together
            if start[i] != target[j]:
                return False  # pieces can't pass each other
            if start[i] == "L" and i < j:
                return False  # L can't move right
            if start[i] == "R" and i > j:
                return False  # R can't move left
            i = i + 1
            j = j + 1
        return True

What the code is doing, line by line:

1. Skip blanks so i and j point at the next piece in each string.
2. Running out of pieces in only one string means the counts differ.
3. Mismatched letters mean the order changed, which is impossible.
4. The direction checks enforce L-only-left and R-only-right.

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 blanks in both → True.
• Different counts of L/R → False.
• An R that would have to move left → False.

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

Problem: Pick ascending indices in word1 whose characters spell a string that equals word2 with at most one character changed. Return the lexicographically smallest such index list, or [].

Solve it on LeetCode ↗

Constraints: 1 ≤ word2.length < word1.length ≤ 3 * 10⁵ · word1 and word2 consist only of lowercase English letters.

From brute force to the pattern: For every possible change position, re-checking whether the rest is a subsequence costs O(n) each: O(n · m). The suffix table answers "can the rest still match?" in O(1), so one greedy pass suffices.

Spot it: Matching word2 as a subsequence of word1 is a two-pointer walk. To decide greedily whether the one allowed mismatch can be used now, you need to know whether the rest of word2 can still be matched exactly afterwards, which a precomputed suffix table answers in O(1).

Why not another pattern? Trying every position for the single change and re-running a subsequence check is O(n · m). DP over (index, changed) can't easily recover the lexicographically smallest list. The suffix table makes the greedy choice safe and linear.

Key insight: suf[i] = how many characters at the end of word2 can be matched as a subsequence of word1[i:]. Scanning word1 from the left with pointer j into word2: take index i when word1[i] == word2[j], or, if the change is unused and suf[i + 1] ≥ m − j − 1, take i as the changed character. Taking the earliest possible index each time gives the smallest list.

Approach:

1. Build suf from the right: walk word1 backwards, matching word2 from its end greedily.
2. Walk word1 from the left with j = next character of word2 to place.
3. If word1[i] == word2[j], take i. Else if the change is unused and the remaining m − j − 1 characters fit in word1[i + 1:] (suf[i + 1]), take i and mark the change used.
4. Return the indices if all of word2 was placed, otherwise [].

class Solution:
    def validSequence(self, word1: str, word2: str) -> List[int]:
        n = len(word1)
        m = len(word2)
        # suf[i] = how many characters at the END of word2 match as a subsequence of word1[i:]
        suf = [0] * (n + 1)
        j = m - 1
        for i in range(n - 1, -1, -1):
            if j >= 0 and word1[i] == word2[j]:
                j = j - 1  # matched one more character from the back
            suf[i] = m - 1 - j
        answer = []
        changed = False  # has the single allowed change been used?
        j = 0  # next character of word2 to place
        for i in range(n):
            if j == m:
                break  # everything placed
            if word1[i] == word2[j]:
                answer.append(i)  # exact match: always take the earliest index
                j = j + 1
            elif not changed and suf[i + 1] >= m - j - 1:
                answer.append(i)  # use the change here: the rest can still match exactly
                changed = True
                j = j + 1
        return answer if j == m else []

What the code is doing, line by line:

1. The first loop fills suf: matching word2 backwards greedily from the end of word1 gives the longest matchable suffix for every start.
2. suf[i] = m - 1 - j: after processing word1[i], characters j + 1 .. m − 1 of word2 are matched.
3. Second loop: exact matches are always taken immediately (the earliest index keeps the list smallest).
4. A mismatch is taken as the change only if it's unused and the remaining m − j − 1 characters can still be matched exactly after i; using it as early as possible also keeps the list smallest.
5. answer if j == m else []: success only if all of word2 was placed.

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 valid sequence even with one change → [].
• An exact subsequence exists, but changing an earlier character gives smaller indices.
• word2 one shorter than word1.

Complexity: O(n) time, O(n) space for the suffix table.

Problem: Build prefixGcd[i] = gcd(nums[i], max(nums[0..i])), sort it, then repeatedly pair the smallest and largest unpaired values (ignoring the middle one if n is odd). Return the sum of the GCDs of all pairs.

Solve it on LeetCode ↗

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

From brute force to the pattern: Recomputing max(nums[0..i]) for every i is O(n²); a running maximum makes it O(1) each. Pairing extremes is then a simple two-pointer walk after sorting.

Spot it: "Pair the smallest with the largest" on a sorted array is opposite-end two pointers moving inward.

Why not another pattern? There's no clever shortcut needed: the work is one pass for the prefix maxima, a sort, and an inward two-pointer pass.

Approach:

1. Scan nums keeping the running maximum; record gcd(nums[i], running_max).
2. Sort these values.
3. left = 0, right = n − 1: while left < right, add gcd(values[left], values[right]) and move both inward.

from math import gcd

class Solution:
    def gcdSum(self, nums: List[int]) -> int:
        prefix_gcd = []
        running_max = 0
        for x in nums:
            running_max = max(running_max, x)  # max(nums[0..i])
            prefix_gcd.append(gcd(x, running_max))
        prefix_gcd.sort()
        total = 0
        left = 0
        right = len(prefix_gcd) - 1
        while left < right:
            total = total + gcd(prefix_gcd[left], prefix_gcd[right])  # smallest with largest
            left = left + 1
            right = right - 1
        return total

What the code is doing, line by line:

1. running_max is the maximum of the prefix, updated before computing the GCD (so x itself counts).
2. prefix_gcd.sort(): pairing needs the values in order.
3. while left < right: pairs the extremes and moves inward; with odd n the middle element is left out automatically.

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 single element → 0 (nothing to pair).
• Odd length: the middle value is ignored.
• All equal values.

Complexity: O(n log n) for the sort (plus O(n log V) for the GCDs).

Problem: Return the lexicographically largest substring of s. (It's always a suffix: extending a substring never makes it smaller.)

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 4 * 10⁵ · s contains only lowercase English letters.

From brute force to the pattern: max(s[i:] for i in range(n)) compares up to n suffixes of length up to n: O(n²), too slow for 4·10⁵. Keeping just two candidates and letting the loser skip everything it already matched makes the scan O(n).

Spot it: The answer is the largest suffix. Comparing suffixes naively is O(n²). Instead keep two candidate starts i < j and a match length k, and let the loser of each comparison jump forward: three pointers walking the string once.

Why not another pattern? Sorting all suffixes (or building a suffix array) works but is O(n log n) or more and far more code. Taking the maximum of s[i:] over all i builds n substrings: O(n²) time.

Key insight: If s[i:i+k] == s[j:j+k] and then s[i+k] < s[j+k], every start in i..i+k loses to the matching start in j..j+k, so i can jump to max(i + k + 1, j). Symmetrically, if s[i+k] > s[j+k], j jumps to j + k + 1. Each jump skips k + 1 positions, so the whole scan is linear.

Approach:

1. i = 0 is the best start so far, j = 1 the challenger, k = 0 the matched length.
2. If s[i + k] == s[j + k], extend the match: k += 1.
3. If s[i + k] > s[j + k]: the challenger loses; j = j + k + 1, k = 0.
4. If s[i + k] < s[j + k]: the best loses; i = max(i + k + 1, j), j = i + 1, k = 0.
5. Stop when j + k reaches the end; the answer is s[i:].

class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s)
        i = 0  # best starting index so far
        j = 1  # challenger starting index
        k = 0  # how many characters of s[i:] and s[j:] matched
        while j + k < n:
            if s[i + k] == s[j + k]:
                k = k + 1  # still tied: compare the next character
            elif s[i + k] > s[j + k]:
                j = j + k + 1  # challenger loses, and so do the starts it just matched
                k = 0
            else:
                i = max(i + k + 1, j)  # best loses: skip past everything it matched
                j = i + 1
                k = 0
        return s[i:]

What the code is doing, line by line:

1. i holds the best start found so far and j the one being tested; k counts how far they agree.
2. Equal characters: keep comparing (k += 1).
3. s[i + k] > s[j + k]: s[j:] is smaller, and so is every s[j + t:] for t ≤ k (each loses to s[i + t:]), so j jumps by k + 1.
4. s[i + k] < s[j + k]: the same argument in reverse; i moves to max(i + k + 1, j) and a new challenger starts right after it.
5. return s[i:]: the winning suffix.

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 characters equal, e.g. "aaaa" → the whole string.
• The largest letter appears once, e.g. "leetcode" → "tcode".
• Repeating patterns, e.g. "abab" → "bab".

Complexity: O(n) time (every jump skips the characters just compared), O(1) extra space besides the answer.

Problem: A celebrity is known by everyone and knows nobody. Using knows(a, b), find them (or −1) with few calls.

Solve it on LeetCode ↗ (Premium)

Constraints: n == graph.length == graph[i].length · 2 ≤ n ≤ 100 · graph[i][j] is 0 or 1 · graph[i][i] == 1

From brute force to the pattern: Checking all pairs is O(n²) calls; elimination is O(n).

Spot it: Each knows(a, b) call rules someone out: if a knows b, a isn't the celebrity; otherwise b isn't. A two-pointer elimination leaves one candidate in n − 1 calls; then verify it.

Why not another pattern? Checking every pair is O(n²) calls.

Approach:

1. cand = 0; for i in 1..n−1: if knows(cand, i), cand = i.
2. Verify: for every i ≠ cand, knows(cand, i) must be false and knows(i, cand) true.

class Solution:
    def findCelebrity(self, n: int) -> int:
        cand = 0
        for i in range(1, n):
            if knows(cand, i):
                cand = i  # cand knows someone, so cand can't be the celebrity
        for i in range(n):
            if i != cand and (knows(cand, i) or not knows(i, cand)):
                return -1  # the survivor fails the definition
        return cand

What the code is doing, line by line:

1. If cand knows i, cand is out; if not, i is out (the celebrity is known by everyone, including cand).
2. Only one candidate survives, and it still has to be checked.

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 celebrity → −1.
• The celebrity is person 0.
• n = 2.

Complexity: O(n) time and at most 3n calls to knows, O(1) space.

Problem: Sort a permutation of 1..n using prefix reversals (flip the first k elements). Return any sequence of ks with at most 10n flips.

Solve it on LeetCode ↗

Constraints: 1 ≤ arr.length ≤ 100 · 1 ≤ arr[i] ≤ arr.length · All integers in arr are unique (i.e. arr is a permutation of the integers from 1 to arr.length).

From brute force to the pattern: Searching for the minimum flips is exponential; two flips per value is O(n²) and valid.

Spot it: Place values from largest to smallest: each takes two flips (to the front, then to the back of the unsorted part) — a two-pointer reversal pattern.

Why not another pattern? Searching for the fewest flips is NP-hard; the problem only asks for any sequence within 10n.

Approach:

1. For size from n down to 2: find the index i of size.
2. Flip i + 1 (it goes to the front), then flip size (it goes to position size − 1).

class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        flips = []
        for size in range(len(arr), 1, -1):
            i = arr.index(size)  # where the largest unsorted pancake is
            if i == size - 1:
                continue  # already in place
            if i > 0:
                arr[:i + 1] = arr[:i + 1][::-1]  # bring it to the top
                flips.append(i + 1)
            arr[:size] = arr[:size][::-1]  # flip it down into place
            flips.append(size)
        return flips

What the code is doing, line by line:

1. After processing size, the last n − size + 1 positions hold their final values.
2. At most two flips per value: 2n ≤ 10n.

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 → [].
• Reversed array.
• n = 1.

Complexity: O(n²) time, O(n) space for the answer.

Problem: Remove one subarray (possibly empty) so the rest is non-decreasing. Return the shortest such removal.

Solve it on LeetCode ↗

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

From brute force to the pattern: Every removal + check is O(n³); binary search on the suffix is O(n log n); two pointers is O(n).

Spot it: What remains is a sorted prefix plus a sorted suffix. Find the longest sorted suffix starting at r; then for each prefix end l, move r forward until arr[r] ≥ arr[l] — two pointers, both only moving right.

Why not another pattern? Trying every removal and checking sortedness is O(n³).

Approach:

1. r = start of the longest non-decreasing suffix. If r == 0, return 0.
2. Answer starts as r (remove the whole prefix).
3. For l = 0, 1, … while the prefix stays sorted: advance r while arr[r] < arr[l]; candidate r − l − 1.

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        r = n - 1
        while r > 0 and arr[r - 1] <= arr[r]:
            r -= 1  # longest sorted suffix starts at r
        if r == 0:
            return 0  # already sorted
        best = r  # remove everything before the suffix
        for l in range(n):
            if l > 0 and arr[l] < arr[l - 1]:
                break  # the prefix is no longer sorted
            while r < n and arr[r] < arr[l]:
                r += 1  # suffix must start at a value >= arr[l]
            best = min(best, r - l - 1)  # remove arr[l+1 .. r-1]
        return best

What the code is doing, line by line:

1. The kept prefix must be sorted and the kept suffix must be sorted, and the junction must not decrease.
2. As l grows, arr[l] grows, so the needed r never moves back.

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 → n − 1.
• Equal values.

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

Problem: Repeatedly remove two numbers summing to k. Return the maximum number of removals.

Solve it on LeetCode ↗

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

From brute force to the pattern: Nested loops are O(n²); sort + two pointers is O(n log n).

Spot it: Pairs with a fixed sum → sort + two pointers from both ends (or a hash map of unmatched values).

Why not another pattern? Greedy pairing in arbitrary order with nested loops is O(n²).

Approach:

1. Sort.
2. l, r at the ends: equal to k → count, move both; less → l += 1; more → r −= 1.

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        nums = sorted(nums)
        l, r = 0, len(nums) - 1
        pairs = 0
        while l < r:
            s = nums[l] + nums[r]
            if s == k:
                pairs += 1  # use both
                l += 1
                r -= 1
            elif s < k:
                l += 1  # need a bigger sum
            else:
                r -= 1  # need a smaller sum
        return pairs

What the code is doing, line by line:

1. In a sorted array, if nums[l] + nums[r] < k, nums[l] can't pair with anything left, so it's discarded.
2. Pairing a matching couple never hurts 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:

• Duplicates (k = 2x).
• No pairs → 0.
• All pairs.

Complexity: O(n log n) time, O(n) space (or O(n) time with a hash map).

Problem: Rearrange so values < pivot come first, then == pivot, then > pivot, keeping the relative order inside each group.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · -10⁶ ≤ nums[i] ≤ 10⁶ · pivot equals to an element of nums.

From brute force to the pattern: Three separate list passes are also O(n); the two-pointer version does it in one.

Spot it: A three-way partition, but stable. In-place swapping (Dutch flag) breaks the order, so fill the result with two pointers: smaller values from the front, larger values from the back (reading the array backwards), pivots in between.

Why not another pattern? The Dutch national flag swap scheme is O(1) space but not stable.

Approach:

1. lo writes smaller values from the left (scan forward); hi writes larger values from the right (scan backward).
2. Fill the gap between them with pivot.

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        n = len(nums)
        result = [pivot] * n  # anything not overwritten is the pivot
        lo, hi = 0, n - 1
        for i in range(n):
            if nums[i] < pivot:
                result[lo] = nums[i]  # smaller values, in order, from the left
                lo += 1
            if nums[n - 1 - i] > pivot:
                result[hi] = nums[n - 1 - i]  # larger values, scanned backwards, from the right
                hi -= 1
        return result

What the code is doing, line by line:

1. Scanning backwards while writing backwards keeps the larger values in their original order.
2. Pre-filling with pivot handles the middle group automatically.

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:

• Pivot appears many times.
• All smaller or all larger.
• Negative numbers.

Complexity: O(n) time, O(n) space for the result.

Problem: Group all 1s to the right and 0s to the left using adjacent swaps. Return the minimum number of swaps.

Solve it on LeetCode ↗

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

From brute force to the pattern: Bubble-sort simulation is O(n²); counting is O(n).

Spot it: Each adjacent swap moves one 0 past one 1. So the answer is the number of (1, 0) pairs in order — count 1s seen so far while scanning (a two-pointer / counting idea: the next 0 goes to the next free left slot).

Why not another pattern? Simulating swaps (bubble sort) is O(n²).

Approach:

1. ones = 0; for each character: 1 → ones += 1; 0 → swaps += ones.

class Solution:
    def minimumSteps(self, s: str) -> int:
        swaps = 0
        ones = 0  # black balls to the left of the current position
        for ch in s:
            if ch == "1":
                ones += 1
            else:
                swaps += ones  # this white ball must pass every black ball before it
        return swaps

What the code is doing, line by line:

1. Every out-of-order pair needs exactly one swap, and each swap fixes exactly one pair.
2. The answer can exceed 32 bits (n up to 10⁵).

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 separated → 0.
• All ones or all zeros.
• Alternating pattern.

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

Problem: Build the lexicographically smallest array whose absolute values are a permutation of 1..n and whose sum is target, or [].

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10⁵ · -10¹⁰ ≤ target ≤ 10¹⁰

From brute force to the pattern: All 2ⁿ sign choices vs a greedy pick from the top.

Spot it: Starting from 1 + … + n = S, negating a set N changes the sum to S − 2 · sum(N), so sum(N) = (S − target) / 2. To be lexicographically smallest, the array should start with the most negative numbers: greedily put the largest values into N, then sort.

Why not another pattern? Trying all 2ⁿ sign patterns is exponential.

Approach:

1. S = n(n + 1)/2. If S − target is odd or outside [0, 2S], return [].
2. T = (S − target)/2; for v = n … 1: if v ≤ T, negate it and T −= v.
3. Return the values sorted ascending.

class Solution:
    def lexSmallestNegatedPerm(self, n: int, target: int) -> List[int]:
        total = n * (n + 1) // 2
        if (total - target) % 2 or not (-total <= target <= total):
            return []  # the negated part would need a non-integer or impossible sum
        need = (total - target) // 2  # sum of the values we negate
        values = []
        for v in range(n, 0, -1):
            if v <= need:
                values.append(-v)  # negate the biggest values first
                need -= v
            else:
                values.append(v)
        return sorted(values)

What the code is doing, line by line:

1. Any T between 0 and S is a subset sum of 1..n, and taking the largest value that fits always leaves a reachable remainder.
2. Sorted ascending, the array starts with −(largest negated); making that as large as possible makes the first element as small as possible, and the same for the next ones.

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 out of range → [].
• Wrong parity → [].
• Target equals the full sum (nothing negated).

Complexity: O(n log n) time (O(n) without the final sort, since the order is known), O(n) space.

Problem: A word is stretchy if extending some of its letter groups to length ≥ 3 makes it equal to s. Count stretchy words.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length, words.length ≤ 100 · 1 ≤ words[i].length ≤ 100 · s and words[i] consist of lowercase letters.

From brute force to the pattern: Trying stretch combinations is exponential; comparing runs is linear.

Spot it: Walk s and a word with two pointers, run by run. Runs must have the same letter, and the s run must equal the word's run or be at least 3 and not shorter.

Why not another pattern? Generating all stretched versions of a word is exponential.

Approach:

1. runs(x) = list of (letter, length).
2. A word matches if it has the same letters in order and for each run: ls == lw or (ls ≥ 3 and ls ≥ lw).

from itertools import groupby

class Solution:
    def expressiveWords(self, s: str, words: List[str]) -> int:
        def runs(x):
            return [(ch, len(list(g))) for ch, g in groupby(x)]

        target = runs(s)

        def stretchy(word):
            r = runs(word)
            if len(r) != len(target):
                return False
            for (c1, n1), (c2, n2) in zip(target, r):  # walk both run lists together
                if c1 != c2 or n1 < n2 or (n1 != n2 and n1 < 3):
                    return False  # different letter, too short, or an extension shorter than 3
            return True

        return sum(stretchy(w) for w in words)

What the code is doing, line by line:

1. Run-length encoding turns the two-pointer walk into comparing pairs.
2. A group can only be extended to a total of 3 or more, never shrunk.

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:

• Group of length 2 in s (can't come from length 1).
• Equal strings (stretchy).
• Different letters.

Complexity: O(len(s) + Σ word lengths) time, O(len(s)) space.