Two Pointer Techniques

Stop checking pairs you have already ruled out

A sorted array holds 30,000 integers, which is the most that LeetCode 167: Two Sum II - Input Array Is Sorted allows. Do two of them add up to a target? Checking every pair means 30,000 × 29,999 / 2 = 449,985,000 sums. The method in this lesson needs at most 29,999.

The speed-up does not come from a faster comparison. It comes from reading each comparison more carefully. Suppose the smallest value plus the largest value falls short of the target. Then the smallest value is useless: it just failed with the biggest partner it could ever get. One comparison has ruled out 29,999 pairs, and the brute force goes on to check every one of them anyway.

That is the big idea: a pointer may move only when you can say why the positions it leaves behind can never matter again. Within one scan, no pointer ever moves backward, so the work of that scan is bounded by how far its pointers can travel. Each technique below is a different reason for moving.

This lesson builds on Foundation: Arrays & Strings. You should know its output contracts, the read/write pointers from its Move 3 (Remove Element) and its Move Zeroes challenge, and the opposite-end swap loop that reverses an array in its Move 4. Here those pointers get new jobs, and each job comes with a proof.

Move 1: Squeeze from both ends

Smell: the input is sorted and you want a pair whose sum hits a target.

The contract

LeetCode 167 gives you numbers, sorted in non-decreasing order, and a target. Exactly one pair of different positions adds up to it. Return the two positions 1-based, smaller first, using O(1) extra space.

The version below returns 0-based indices, and None when no pair exists, which makes it easy to test on any input. For LeetCode, return [left + 1, right + 1] instead.

Predict first: nums = [2, 7, 11, 15, 18, 24, 30], target 33. Put one finger on each end: 2 + 30 = 32, one short. Which finger moves? How many pairs does that single move rule out?

The slow version tries all 7 × 6 / 2 = 21 pairs. Look at what it repeats: for each left value it tries partner after partner, even after the largest partner has already failed.

The fast version keeps one index at each end and moves exactly one of them per step:

def two_sum_sorted(nums, target):
    """nums is sorted ascending. Return 0-based (i, j) with i < j, or None."""
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return (left, right)
        if s < target:
            left += 1      # even the largest partner left is too small for nums[left]
        else:
            right -= 1     # even the smallest partner left is too big for nums[right]
    return None

Six sums instead of 21. The function returns (3, 4), and LeetCode would want [4, 5].

Why one comparison rules out a whole row

Lay every possible sum out in a grid. Row i is the left index, column j is the right index, and only i < j counts. Because the array is sorted, sums grow from left to right along each row and from top to bottom down each column. The bracketed cells are the six sums the loop computed:

              j=1    j=2    j=3    j=4    j=5    j=6
              (7)   (11)   (15)   (18)   (24)   (30)
i=0 ( 2)      9     13     17     20     26   [32]
i=1 ( 7)            18     22     25   [31]   [37]
i=2 (11)                   26   [29]   [35]     41
i=3 (15)                        [33]     39     45
i=4 (18)                                 42     48
i=5 (24)                                        54

The search starts in the top-right corner, cell (0, 6).

• Too small (32 at (0, 6)): every cell to its left in row 0 is smaller still. The whole row is dead, and left += 1 moves down one row.
• Too big (37 at (1, 6)): every cell below it in column 6 is bigger still. The whole column is dead, and right -= 1 moves one column left.

Each step deletes a row or a column, which gives the loop its invariant: if a valid pair exists, both of its indices lie in [left, right]. Here is the proof for the too-small case. Every index j with left < j ≤ right has nums[j] ≤ nums[right], so nums[left] + nums[j] ≤ s < target. The value at left has no partner inside the window, and partners outside the window were ruled out by earlier steps. The too-big case is the mirror image.

Each iteration shrinks right − left by exactly one, so the loop runs at most n − 1 times. That is O(n) time and O(1) extra space, where n is len(nums).

🧠 It is tempting to say the loop "considers every pair". It computed 6 of 21. The accurate claim is that every pair was either checked or proved useless.

The grid also handles counting. Suppose the question is how many pairs have a sum below the target. A too-small sum at (left, right) means every pair (left, j) with left < j ≤ right is below the target too. That is right − left pairs, counted in one step before the row is dropped.

Sorting buys correctness, not speed

Run the same function on the unsorted [3, 5, 1, 9] with target 10. 3 + 9 = 12 is too big, so right drops the 9. That move assumes 3 is the smallest partner the 9 could ever get. But 1 is smaller, and 1 + 9 = 10 was the answer. The loop goes on to check 3 + 1 = 4 and 5 + 1 = 6, then returns None.

It doesn't crash and it doesn't slow down, because the loop is O(n) on any input. What breaks is the proof behind each move, so you get a wrong answer that looks plausible.

Sorting first repairs the proof, but check the contract before you sort. LeetCode 1: Two Sum asks for original positions in an unsorted array, and sorting scrambles them. Here are your options:

The hash-map version belongs to Hash Maps & Sets.

Traps

• Every branch must move a pointer. Delete the else and try [2, 3, 4, 8] with target 7. 2 + 8 = 10 is too big, nothing moves, and the loop computes the same sum forever.
• < or <=? The guard left < right means "two different positions". With left <= right, the input [2, 3, 4] with target 8 walks up to left = right = 2 and reports (2, 2), which uses the 4 twice. Some loops do need <=. Move 5's loop does, because there the cell where the pointers meet has not been examined yet. So ask: does the state left == right still have work to do?
• Equal values are fine. [3, 3] with target 6 returns (0, 1). Pointers are positions, not values.
• Short input. An empty or one-element array skips the loop and returns None. But code that reads nums[0] before the loop, for example to set up a "best so far", needs a length check first.
• Overflow. In Java or C++, nums[left] + nums[right] can overflow a 32-bit int. Python integers never overflow. LeetCode 167 keeps values within ±1000, so this only bites in a general version with large values.

Your turn: closest instead of exact

Change the problem: return the pair sum closest to the target. Use nums = [10, 22, 28, 29, 30, 40] with target 54.

1. What must you remember that the exact version didn't?
2. When may you stop early?
3. Is the pointer rule still safe?

def closest_pair(nums, target):
    """nums sorted ascending. Return (best_sum, (i, j)), or None if fewer than 2 values."""
    if len(nums) < 2:
        return None
    left, right = 0, len(nums) - 1
    best_sum, best_pair = None, None
    while left < right:
        s = nums[left] + nums[right]
        if best_sum is None or abs(s - target) < abs(best_sum - target):
            best_sum, best_pair = s, (left, right)
        if s == target:
            break                      # distance 0 cannot be beaten
        if s < target:
            left += 1
        else:
            right -= 1
    return best_sum, best_pair

Move 2: Compare with the last value kept

Smell: the input is sorted, and you must remove repeats in place and report how many distinct values are left.

In the final round of Foundation: Arrays & Strings you kept first occurrences in an unsorted list, and you needed a set to answer "have I kept this value already?". Sorted input answers that question for free. All copies of a value sit next to each other, so a value is new exactly when it differs from the last value you kept.

LeetCode 26: Remove Duplicates from Sorted Array has the same contract shape as Remove Element. Put the distinct values in the first k cells, in their original order, and return k. Whatever sits after cell k doesn't matter.

Predict first: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]. What is k, what are the first k cells, and what does the whole list look like afterward?

def remove_duplicates(nums):
    if not nums:
        return 0
    write = 1                              # nums[0] is always kept
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:  # differs from the last kept value
            nums[write] = nums[read]
            write += 1
    return write

Trace [1, 1, 2, 3, 3]:

It returns 3, and the whole list is now [1, 2, 3, 3, 3].

Why it works. The invariant is: before each iteration, nums[:write] holds each distinct value of nums[:read] exactly once, in order. Because the input is sorted, a value can only be followed by copies of itself or by something larger. So "differs from nums[write - 1]" means the same thing as "never kept before". The writes are safe for the reason you saw in the Foundation lesson: write <= read, so nothing unread gets overwritten. That is O(n) time and O(1) extra space.

Two edges deserve a look:

• The empty guard is load-bearing. Starting at write = 1 assumes a first value exists. Without if not nums, an empty list returns 1.
• Sortedness is doing real work. On the unsorted [1, 2, 1], the function returns 3 and keeps both 1s. The read/write shape itself doesn't need order (Remove Element didn't), but this comparison does.

Plot twist: keep at most two of each

LeetCode 80: Remove Duplicates from Sorted Array II allows each value up to twice. A value may be kept unless the last two kept values already equal it. In sorted input, that is one comparison: nums[read] != nums[write - 2].

Your turn: write it. Then a teammate suggests comparing with nums[read - 2] instead, "because it's the same thing in the input". Find an input where the teammate's version fails, and explain why.

def remove_duplicates_keep2(nums):
    write = 0
    for read in range(len(nums)):
        if write < 2 or nums[read] != nums[write - 2]:
            nums[write] = nums[read]
            write += 1
    return write

Move 3: The tortoise and the hare

Smell: you have a linked list, or any "next step" rule, and a question about its shape: does it loop, and where is its middle?

A linked list gives you a head node and a .next link on each node. You can't index into it and you don't know its length, so all you can do is walk forward.

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

LeetCode 141: Linked List Cycle asks whether following .next ever comes back to a node you have visited. The follow-up asks for O(1) memory.

The simple answer is the Foundation lesson's set of seen items, applied to nodes. Walk the list, store each node, and report a cycle when you meet a stored one. That is expected O(n) time but also O(n) memory. Without any memory, a plain walk around a cycle never ends.

Floyd's algorithm uses two pointers instead. The tortoise moves one node per iteration and the hare moves two. With no cycle, the hare falls off the end. With a cycle, the hare can never leave it, and it eventually lands on the tortoise.

def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next           # tortoise: one step
        fast = fast.next.next      # hare: two steps
        if slow is fast:           # same node, not just the same value
            return True
    return False

Predict first: in the list below, E links back to C. Both pointers start at A. After which iteration do they meet, and on which node?

A → B → C → D → E
        ↑       │
        └───────┘

Why they must meet

Once the tortoise enters the loop, the hare is already inside it, because it is ahead and can't get out. Measure the gap as the number of steps the hare must walk forward around the loop to reach the tortoise. Each iteration the tortoise moves 1 and the hare moves 2, so the gap shrinks by exactly one. A gap that shrinks by one per step can't jump over zero, so they meet no later than the end of the tortoise's first lap. For a list of n nodes the loop runs at most n iterations: O(n) time, O(1) extra space.

Why two steps and not three? The proof needs the gap to shrink by exactly one. A three-step hare shrinks it by two, which can jump over zero every time: on a 4-node loop, a gap of 1 goes 1, 3, 1, 3, and so on. Pointers that start on the same node never get into that state, though: the gap on an even-length loop is then always even, so shrinking it by two still lands on zero. A three-step hare does detect every cycle. What it breaks is the loop-start trick below.

⚠️ Compare nodes, not values. slow is fast asks whether both pointers are on the same node. With slow.val == fast.val, the acyclic list 5 → 7 → 5 → 9 → 5 reports a cycle: after two iterations the tortoise is on the middle 5 and the hare on the last 5.

Guarding the hare's jump

fast.next.next needs both fast and fast.next to exist. Guards that look almost right fail on specific lengths:

Non-empty acyclic lists of even length and all lists with a cycle pass all three guards, so tests that only use even lengths never catch the bug. The order inside the correct guard matters too: and checks fast before it reads fast.next.

Same loop, different question: the middle

When the hare reaches the end, the tortoise has gone half as far. That answers LeetCode 876: Middle of the Linked List in one pass:

def middle_node(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

On A → B → C → D → E it returns C. On A → B → C → D it also returns C, the second of the two middles, which is the convention LeetCode 876 asks for. To split a list into halves you often want the first middle. Start the hare one node ahead with fast = head.next, and A → B → C → D gives B.

A third variant keeps a fixed gap instead of a speed ratio. Walk fast k nodes ahead first, then move both pointers one node at a time. When fast falls off the end, slow is on the k-th node from the end.

Your turn: what does middle_node return for lists of 1, 2 and 6 nodes, and what does the fast = head.next variant return for 6?

Boss level: where does the loop start?

LeetCode 142: Linked List Cycle II wants the first node of the loop. After the two pointers meet, put one pointer back at head and move both one node at a time. They meet again exactly at the loop's first node.

def meeting_node(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return slow
    return None

def cycle_start(head):
    meet = meeting_node(head)
    if meet is None:
        return None
    a, b = head, meet
    while a is not b:          # both walk one node at a time
        a = a.next
        b = b.next
    return a

On the A to E list, the pointers first meet at D. Then a and b go through (A, D), (B, E) and finally (C, C). The loop starts at C.

Why it works. Say the tail has μ nodes before the loop and the loop has λ nodes. At the meeting, the tortoise has taken t steps and the hare 2t. The hare's extra t steps were whole laps of the loop, so t is a multiple of λ. The tortoise stands t − μ steps past the loop's first node, so μ more steps take it t steps past that node. That is a whole number of laps, which puts it back on the first node. The pointer that restarts at head also needs μ steps to get there. Before that, one pointer is on the tail and the other is inside the loop, so they can't meet early. In the example, μ = 2 (A and B), λ = 3 (C, D, E) and t = 3.

This is where the hare's speed matters. A three-step hare has walked 3t, so its extra 2t steps are whole laps, and t itself can be half a lap. Take A → B → C → D → E → F → C, a 2-node tail and a 4-node loop. The three-step pointers meet at C after t = 2. In the second phase, the restarted pointer needs two steps to reach C, and by then the other one has moved on to E. They stay two nodes apart forever.

Move 4: Sort, fix one, squeeze the rest

Smell: you want triplets whose values hit a target, and the answer lists values, not positions.

LeetCode 15: 3Sum asks for every triplet [a, b, c], taken from three different positions, with a + b + c = 0. The output must not contain the same triplet twice, and any order is fine.

Read the contract first. The answer is values, so sorting is allowed.

Predict first: nums = [-1, 0, 1, 2, -1, -4]. How many different triples of positions sum to zero, and how many triplets belong in the answer?

The slow version runs three nested loops and throws the results into a set of sorted tuples. That is O(n³). At LeetCode's limit of n = 3,000 it means C(3000, 3) = 4,495,501,000 triples.

The fast version sorts, then treats each nums[i] as a fixed value. For each fixed value it runs Move 1's squeeze on the part after i, looking for a pair that sums to -nums[i]:

def three_sum(nums):
    nums = sorted(nums)            # values only, so sorting is allowed
    n = len(nums)
    result = []
    for i in range(n - 2):
        if nums[i] > 0:
            break                  # everything from i on is positive
        if i > 0 and nums[i] == nums[i - 1]:
            continue               # same fixed value as last time
        left, right = i + 1, n - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1      # skip copies of the value just used
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif s < 0:
                left += 1
            else:
                right -= 1
    return result

On the example, the sorted list is [-4, -1, -1, 0, 1, 2]. The table shows each pair tried as (left value, right value) and the triple sum s:

The result is [[-1, -1, 2], [-1, 0, 1]]. At i = 0 the pair (−1, 2) appears twice because left steps from the first −1 to the second.

Duplicates without a set

Two skips keep the output clean.

• The outer skip compares nums[i] with nums[i - 1], so each fixed value gets exactly one turn, at its first occurrence. The first copy is the one that can still pair with its own twins: at i = 1, the fixed −1 finds [-1, -1, 2] by using the second −1 as a partner. Compare with nums[i + 1] instead and you skip the first copy and keep the last one. The last −1 has no −1 after it, so [-1, -1, 2] vanishes, and that version returns only [[-1, 0, 1]].
• The inner skip runs after a match. With the fixed value a, any other pair that uses the same left value b would need the same c = −a − b, so it would repeat the triplet. Skip past the copies of both. Without the inner skip, [-2, 0, 0, 2, 2] outputs [-2, 0, 2] twice, even with the outer skip in place.

⚠️ The skip loops need their own left < right check. On [0, 0, 0], an unguarded while nums[left] == nums[left - 1] walks past the end of the list and raises IndexError.

Why no triplet repeats. Each triplet comes out in sorted order a ≤ b ≤ c. The outer skip gives each value of a one turn. Within that turn, left only moves right and jumps past every copy of b once b is used, so each b appears once. And c is fixed by a and b. You could also dedupe with a set of tuples, since the triplets come out sorted. The skips are better because they never build the duplicates in the first place.

The early exit if nums[i] > 0: break is safe because every value from i on is positive, so no three of them can sum to zero. It must be > 0, not >= 0: [0, 0, 0] is a valid answer.

What sorting costs

Sorting is O(n log n). Then the outer loop runs up to n times and each squeeze is O(n), which gives O(n²) overall, because n² outgrows n log n. At n = 3,000 the squeezes take at most (n − 1)(n − 2)/2 = 4,495,501 steps, exactly 1,000 times fewer than the 4.5 billion triples. 4Sum adds one more fixed loop around the same squeeze, which makes it O(n³).

Extra space is less obvious. sorted(nums) makes an O(n) copy. nums.sort() avoids the copy but reorders the caller's list, and Python's sort (Timsort) can still use about n/2 temporary slots while it merges. So in Python, 3Sum uses O(n) extra space either way. That does not count the output, which can hold O(n²) triplets.

Your turn: 3Sum Closest

LeetCode 16: 3Sum Closest asks for the sum of three values that is closest to a target, and guarantees exactly one best answer. Combine this move with the closest-pair loop from Move 1. Which parts of three_sum can you delete? Predict the answer for [-1, 2, 1, -4] with target 1.

def three_sum_closest(nums, target):
    nums = sorted(nums)
    best = nums[0] + nums[1] + nums[2]      # LeetCode guarantees len(nums) >= 3
    for i in range(len(nums) - 2):
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if abs(s - target) < abs(best - target):
                best = s
            if s == target:
                return s
            if s < target:
                left += 1
            else:
                right -= 1
    return best

Move 5: Four regions, three pointers

Smell: the values come in three kinds, and you must rearrange them in place in one pass.

LeetCode 75: Sort Colors gives you only 0s, 1s and 2s and asks you to sort them in place without the library sort. The simple answer uses two passes: count each value, then overwrite the list. The follow-up asks for one pass with constant extra space.

Keep four regions and three pointers:

 0 … low-1    low … mid-1   mid … high    high+1 … n-1
[  all 0s   |   all 1s    |  unknown   |    all 2s    ]

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:                          # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1                  # mid stays: the value that arrived is unchecked
    return nums

Predict first: on [2, 0, 2, 1, 1, 0] the first nums[mid] is a 2, so it is swapped with nums[high]. What are (low, mid, high) afterward, and why doesn't mid move?

mid has passed high, so the unknown region is empty and the loop stops.

Why it works. Every iteration either moves mid up or high down, so the unknown region shrinks by exactly one each time. That means exactly n iterations: O(n) time, O(1) extra space. The pointer moves are licensed by what each swap brings back:

• A 0 at mid is swapped to low. What comes back from low? If low < mid, it comes from the 1s region, so it is a 1 and already classified. If low == mid, it is the same cell. Either way mid may advance.
• A 2 at mid is swapped to high. What comes back is from the unknown region, so nobody has checked it. mid stays.
• The guard is mid <= high, because when mid == high that cell is still unknown. With mid < high, the input [1, 0] comes back unchanged.

⚠️ Advancing mid after the swap with high is the classic bug. On [1, 2, 0] it produces [1, 0, 2], with a 0 stranded among the 1s. Whatever arrives from high is unchecked, whether it is a 0 or a 2.

The swaps don't keep equal values in their original order: the partition is not stable. For bare numbers nobody can tell. If the values are records with other fields, or the problem demands the original order within each group, this method is the wrong tool.

Your turn: any pivot

Generalize to partition3(nums, pivot): values below the pivot first, then values equal to it, then values above it. Three-way quicksort uses exactly this partition to cope with many repeated values. Predict partition3([5, 1, 7, 5, 3, 9], 5).

def partition3(nums, pivot):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] < pivot:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == pivot:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
    return nums

Choosing: what does each move prove?

Every move in this lesson has a license, a fact that proves the positions behind the pointer are finished:

The opposite-effects test

A squeeze from both ends needs a quantity that one move pushes up and the other pushes down. For a sum on sorted input, left += 1 raises the sum and right -= 1 lowers it. So "too small" has exactly one fix and "too big" has exactly one fix.

Predict first: in the sorted [1, 4, 6, 7, 14, 19], find two values whose difference is 7. Start at the ends: 19 − 1 = 18, too big. Which pointer do you move?

The fix is to start both pointers at the left, with j ahead of i. Now j += 1 widens the gap and i += 1 narrows it, so the moves have opposite effects again:

def has_pair_with_difference(nums, k):
    """nums sorted ascending, k >= 0. Is there i != j with nums[j] - nums[i] == k?"""
    i, j = 0, 1
    while j < len(nums):
        gap = nums[j] - nums[i]
        if i == j or gap < k:
            j += 1             # widen the gap
        elif gap > k:
            i += 1             # narrow the gap
        else:
            return True
    return False

Neither pointer moves backward and each moves at most n times, so this is O(n) time and O(1) extra space. The i == j check handles k = 0, where a value may not pair with itself. Counting the distinct pairs instead is LeetCode 532: K-diff Pairs in an Array.

Products pass the test when every value is positive, because then both factors grow to the right. With mixed signs the test fails. On [-5, -1, 2, 3] with target product 5, the squeeze checks −15, −3 and 6, then gives up, but (−5) × (−1) = 5. Once signs mix, moving left no longer pushes the product in one known direction.

Converging without sorting

Some converging loops need no sorted input, because their license comes from somewhere else. A palindrome check compares the two ends: a mismatch ends the search, and a match finishes both ends at once. Container With Most Water moves the shorter wall, which has its own proof. Each has a lesson: Palindrome Validation and Container With Most Water.

When pointers are the wrong tool

• Unsorted input, and the answer needs original positions. Sorting destroys them. Use a hash map, as in Hash Maps & Sets.
• A contiguous range that must satisfy a condition, such as the longest substring without repeats. That is a same-direction pair with a job of its own: Sliding Window Patterns.

Final round: no label on the problem

Real problems don't say which move they want. Read the contract, find the smell, and name the license before you write a loop.

Challenge 1: Squares of a Sorted Array

LeetCode 977: Squares of a Sorted Array gives you nums sorted in non-decreasing order, possibly with negatives. Return the squares, also sorted. [-4, -1, 0, 3, 10] becomes [0, 1, 9, 16, 100]. Squaring and then sorting is O(n log n); do it in O(n).

1. Where in the input can the largest square be?
2. Which move applies?
3. In which order do you fill the output?

def sorted_squares(nums):
    n = len(nums)
    out = [0] * n
    left, right = 0, n - 1
    for write in range(n - 1, -1, -1):     # fill from the largest square down
        if abs(nums[left]) > abs(nums[right]):
            out[write] = nums[left] * nums[left]
            left += 1
        else:
            out[write] = nums[right] * nums[right]
            right -= 1
    return out

Challenge 2: Happy Number

LeetCode 202: Happy Number: replace a positive integer by the sum of the squares of its digits, and repeat. The number is happy if this reaches 1. So 19 → 82 → 68 → 100 → 1 is happy. And 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → … repeats forever without reaching 1. Decide whether n is happy using O(1) extra memory.

def is_happy(n):
    def step(x):
        return sum(int(d) ** 2 for d in str(x))
    slow, fast = n, step(n)
    while fast != 1 and slow != fast:
        slow = step(slow)
        fast = step(step(fast))
    return fast == 1

Challenge 3: Two Sum, unsorted

LeetCode 1: Two Sum: nums = [3, 2, 4], target 6. Return the original positions of the two values. A teammate sorts the array and calls two_sum_sorted. What do they return, and what is the right answer?

def two_sum_unsorted(nums, target):
    seen = {}                      # value -> index where it appeared
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

Cheat sheet

Before moving on, pick one move and explain it aloud from a blank editor. Say what the smell is, what license each pointer move has, why the loop guard is < or <=, and which input breaks the code once the license is missing: unsorted input, mixed signs, a three-step hare in the loop-start trick, a lookback into overwritten cells. If you can do that for each move, you can rebuild the rest.

Next: Palindrome Validation and Container With Most Water take converging pointers further, Sliding Window Patterns gives same-direction pointers a range to maintain, and Hash Maps & Sets covers pair problems where sorting is not allowed.