Two Pointers Checkpoint

Optional

26 min · Intermediate

A review of this module. Skip it if you feel confident; the next module does not need it.

Fix the mistakes

The slips that cost marks in this module. Spot each one, then check the fix.

This checkpoint mixes all three patterns on marks, prices and chains. Decide first which pointer pattern fits the clue, then write it.

Opposite ends: use the largest at either side

Marks change from -7 to 11, sorted. Their squares are largest at the two ends. Fill a new list from the back with the larger square, moving the pointer that gave it.

Python

1def sorted_squares(nums):2    result = [0] * len(nums)3    left, right = 0, len(nums) - 14    for pos in range(len(nums) - 1, -1, -1):5        if abs(nums[left]) > abs(nums[right]):6            result[pos] = nums[left] ** 27            left += 18        else:9            result[pos] = nums[right] ** 210            right -= 111    return result12
13
14print(sorted_squares([-7, -3, 2, 3, 11]))

Example 1 · Pairs under a budget

Python

1prices = sorted([40, 10, 25, 5, 30])2budget = 503left, right = 0, len(prices) - 14count = 05while left < right:6    if prices[left] + prices[right] < budget:7        count += right - left8        left += 19    else:10        right -= 111print(count)

Output

What this code does

Sorted prices are 5, 10, 25, 30, 40. With a budget of 50, 5 + 40 fits, so 5 pairs with all four others at once.
Counting right - left pairs at once keeps it O(n) after the sort.

Each value is used once, so it is O(n) time. Sorting the squares would cost O(n log n).

Same direction: keep what passes a test

Read visits every score and write collects the kept ones at the front. The order of kept scores never changes, and no second list is needed.

Python

1def remove_value(nums, bad):2    write = 03    for read in range(len(nums)):4        if nums[read] != bad:5            nums[write] = nums[read]6            write += 17    return write8
9
10scores = [4, 9, 4, 7, 4]11kept = remove_value(scores, 4)12print(kept, scores[:kept])

Example 2 · Negative marks to the end

Python

1marks = [5, -1, 8, -1, 3]2write = 03for read in range(len(marks)):4    if marks[read] != -1:5        marks[write], marks[read] = marks[read], marks[write]6        write += 17print(marks)

Output

[5, 8, 3, -1, -1]

What this code does

Valid marks are swapped to the front, so -1 values gather at the back.
The order of 5, 8, 3 is kept.

The answer is the first kept cells. Cells after that hold old values.

Choose the pattern from the clue

Sorted data and a pair or triple points to pointers from both ends. Filtering or compacting in place points to read and write. A chain or a repeating sequence points to fast and slow.

Example 3 · Happy numbers with a hand-made loop

Python

1def step(n):2    return sum(int(d) ** 2 for d in str(n))3
4
5def is_happy(n):6    slow, fast = n, step(n)7    while fast != 1 and slow != fast:8        slow = step(slow)9        fast = step(step(fast))10    return fast == 111
12
13print(is_happy(7), is_happy(4))

Output

True False

What this code does

7 reaches 1 in a few steps, so it is happy.
4 falls into a loop, so fast meets slow without reaching 1.

Example 4 · Choose the pattern from the clue

Python

1def count_triples(nums):2    nums = sorted(nums)3    count = 04    for i in range(len(nums) - 2):5        if i > 0 and nums[i] == nums[i - 1]:6            continue7        left, right = i + 1, len(nums) - 18        while left < right:9            total = nums[i] + nums[left] + nums[right]10            if total < 0:11                left += 112            elif total > 0:13                right -= 114            else:15                count += 116                left += 117                right -= 118                while left < right and nums[left] == nums[left - 1]:19                    left += 120    return count21
22
23print(count_triples([-1, 0, 1, 2, -1, -4]))

Output

What this code does

Three sum is the opposite-end pattern inside a loop, so it costs O(n squared).
Skipping equal values keeps each triple unique.

Module quiz

Questions from the whole module. Your first answer is your score.

Problems

Graded easy to hard, using everything from this module.

Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.

Exercise 1· Easy

Print whether any two values of the sorted list [1, 4, 6, 8, 10, 45] add up to 16.

Expected output

True

Exercise 2· Easy

Reverse the list [1, 2, 3, 4, 5] in place with two pointers and print it.

Expected output

[5, 4, 3, 2, 1]

Exercise 3· Easy

Remove every 0 from [0, 5, 0, 0, 7, 9] in place. Print the kept values.

Expected output

[5, 7, 9]

Exercise 4· Medium

Print the squares of [-6, -2, 1, 4, 5] in sorted order, using two pointers and no sort call.

Expected output

[1, 4, 16, 25, 36]

Exercise 5· Medium

Print the number of unique values in the sorted list [1, 1, 2, 3, 3, 3, 4] using a write pointer.

Expected output

Exercise 6· Medium

Print the unique triples of [-3, -1, 0, 1, 2, 3] that add up to zero.

Expected output

[[-3, 0, 3], [-3, 1, 2], [-1, 0, 1]]

Exercise 7· Medium

Print the middle value of the chain values = [3, 6, 9, 12, 15, 18, 21] with next links [1, 2, 3, 4, 5, 6, -1], using fast and slow pointers.

Expected output

Exercise 8· Hard

Print the repeated number in [2, 5, 9, 6, 9, 3, 8, 9, 7, 1] using fast and slow pointers.

Expected output

Interview questions

Questions interviewers ask on this topic.

Finish up

Mark complete & continue

Next: Must-do problems: Two Pointers

1def sorted_squares(nums):2 result = [0] * len(nums)3 left, right = 0, len(nums) - 14 for pos in range(len(nums) - 1, -1, -1):5 if abs(nums[left]) > abs(nums[right]):6 result[pos] = nums[left] ** 27 left += 18 else:9 result[pos] = nums[right] ** 210 right -= 111 return result12 13 14print(sorted_squares([-7, -3, 2, 3, 11]))

1prices = sorted([40, 10, 25, 5, 30])2budget = 503left, right = 0, len(prices) - 14count = 05while left < right:6 if prices[left] + prices[right] < budget:7 count += right - left8 left += 19 else:10 right -= 111print(count)

1def remove_value(nums, bad):2 write = 03 for read in range(len(nums)):4 if nums[read] != bad:5 nums[write] = nums[read]6 write += 17 return write8 9 10scores = [4, 9, 4, 7, 4]11kept = remove_value(scores, 4)12print(kept, scores[:kept])

1def step(n):2 return sum(int(d) ** 2 for d in str(n))3 4 5def is_happy(n):6 slow, fast = n, step(n)7 while fast != 1 and slow != fast:8 slow = step(slow)9 fast = step(step(fast))10 return fast == 111 12 13print(is_happy(7), is_happy(4))

1def count_triples(nums):2 nums = sorted(nums)3 count = 04 for i in range(len(nums) - 2):5 if i > 0 and nums[i] == nums[i - 1]:6 continue7 left, right = i + 1, len(nums) - 18 while left < right:9 total = nums[i] + nums[left] + nums[right]10 if total < 0:11 left += 112 elif total > 0:13 right -= 114 else:15 count += 116 left += 117 right -= 118 while left < right and nums[left] == nums[left - 1]:19 left += 120 return count21 22 23print(count_triples([-1, 0, 1, 2, -1, -4]))

Opposite ends: use the largest at either side

What this code does

Same direction: keep what passes a test

What this code does

Choose the pattern from the clue

What this code does

What this code does

Exercise 1· Easy

Exercise 2· Easy

Exercise 3· Easy

Exercise 4· Medium

Exercise 5· Medium

Exercise 6· Medium

Exercise 7· Medium

Exercise 8· Hard

Opposite ends: use the largest at either side

What this code does

Same direction: keep what passes a test

What this code does

Choose the pattern from the clue

What this code does

What this code does

A sorted list needs the pair that adds up to a target. Which pattern fits?

You must remove every 0 from a list in place and keep the order. Which pattern fits?

You have only next links and must detect a loop with O(1) memory. Which pattern fits?

What does this print?

What is the cost of sorted squares with two pointers?

What does this print?

Why does three sum sort first?

What is the time of three sum with sorting and two pointers?

What does this print?

Pair sum on an unsorted list where you need the original indexes is best done with:

In which case is values[len(values) // 2] better than fast and slow pointers?

Which is true for two pointers from both ends on a palindrome check?

Exercise 1· Easy

Exercise 2· Easy

Exercise 3· Easy

Exercise 4· Medium

Exercise 5· Medium

Exercise 6· Medium

Exercise 7· Medium

Exercise 8· Hard

Q1How do you choose between the three two-pointer patterns?

Q2Why are two-pointer solutions usually O(n) or O(n squared)?

Q3When would you not use two pointers?

Q4What do you say about space in an interview answer?

Q5Why does the loop condition use left < right for pair problems?

A sorted list needs the pair that adds up to a target. Which pattern fits?

You must remove every 0 from a list in place and keep the order. Which pattern fits?

You have only next links and must detect a loop with O(1) memory. Which pattern fits?

What does this print?

What is the cost of sorted squares with two pointers?

What does this print?

Why does three sum sort first?

What is the time of three sum with sorting and two pointers?

What does this print?

Pair sum on an unsorted list where you need the original indexes is best done with:

In which case is values[len(values) // 2] better than fast and slow pointers?

Which is true for two pointers from both ends on a palindrome check?

Q1How do you choose between the three two-pointer patterns?

Q2Why are two-pointer solutions usually O(n) or O(n squared)?

Q3When would you not use two pointers?

Q4What do you say about space in an interview answer?

Q5Why does the loop condition use left < right for pair problems?

In which case is `values[len(values) // 2]` better than fast and slow pointers?

In which case is `values[len(values) // 2]` better than fast and slow pointers?