Arrays and Strings Problem Set

Arrays and strings are where two pointers, sliding windows, and prefix sums earn their keep. This set climbs from a warm-up sorted two-sum all the way to Minimum Window Substring — a problem that shows up in interviews specifically because it forces you to combine a window with a character-count map correctly.

What you’ll learn

Recognizing when a sorted input means you should reach for two pointers instead of a hash map.
Extending two pointers to three numbers (3Sum) without producing duplicate triplets.
Prefix/suffix products as an alternative to prefix sums.
Sliding windows that track a count map instead of just a running total or length.

How to use this set

Same loop as the Getting Started set: read the problem, open the stub, find the # TODO, press Run, and match the printed output to the # expect comments. Each problem ends with a collapsed Show solution containing a complete, annotated answer and its complexity.

Problems

1. Two Sum II (Input Array Is Sorted) — LC 167 — Medium

Open LC 167 on LeetCode

Pattern: Two Pointers (opposite ends) — see Two Pointers.

Problem. Given a 1-indexed array numbers sorted in non-decreasing order, return the 1-indexed positions [index1, index2] of the two numbers that add up to target. Exactly one solution exists.

two_sum_sorted.py

def two_sum_sorted(numbers, target):
    # TODO: return the 1-indexed positions of the two numbers that add to target
    pass
 
 
# Sample tests (press Run):
print(two_sum_sorted([2, 7, 11, 15], 9))   # expect [1, 2]
print(two_sum_sorted([2, 3, 4], 6))        # expect [1, 3]

Show solution

python

def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]     # LeetCode wants 1-indexed
        elif total < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]
 
 
print(two_sum_sorted([2, 7, 11, 15], 9))   # [1, 2]
print(two_sum_sorted([2, 3, 4], 6))        # [1, 3]

Sorted input is the cue: no hash set needed, opposite-end pointers solve it in $O(1)$ extra space. Time: $O(n)$ . Space: $O(1)$ .

2. 3Sum — LC 15 — Medium

Open LC 15 on LeetCode

Pattern: Sort + Two Pointers — see Two Pointers.

Problem. Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] (distinct indices) whose values sum to 0. The result must not contain duplicate triplets.

three_sum.py

def three_sum(nums):
    # TODO: return all unique triplets that sum to zero
    pass
 
 
# Sample tests (press Run):
print(three_sum([-1, 0, 1, 2, -1, -4]))   # expect [[-1, -1, 2], [-1, 0, 1]]
print(three_sum([0, 1, 1]))                 # expect []
print(three_sum([0, 0, 0]))                 # expect [[0, 0, 0]]

Show solution

python

def three_sum(nums):
    nums.sort()
    result = []
    n = len(nums)
    for i in range(n):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                          # skip duplicate "first" values
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 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 duplicate "second" values
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1                 # skip duplicate "third" values
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result
 
 
print(three_sum([-1, 0, 1, 2, -1, -4]))   # [[-1, -1, 2], [-1, 0, 1]]
print(three_sum([0, 1, 1]))                 # []
print(three_sum([0, 0, 0]))                 # [[0, 0, 0]]

Sort once, then fix each index i in turn and run the opposite-ends two-pointer scan on the remainder for a target of -nums[i]. Skipping over equal neighbors at all three positions is what keeps the result duplicate-free. Time: $O(n^2)$ . Space: $O(1)$ extra (ignoring the sort and the output).

3. Container With Most Water — LC 11 — Medium

Open LC 11 on LeetCode

Pattern: Two Pointers (opposite ends) — see Two Pointers.

Problem. Given height, an array where height[i] is the height of a vertical line at position i, find two lines that together with the x-axis form a container holding the most water. Return the max area.

max_area.py

def max_area(height):
    # TODO: return the maximum amount of water the container can hold
    pass
 
 
# Sample tests (press Run):
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))   # expect 49
print(max_area([1, 1]))                          # expect 1

Show solution

python

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        width = right - left
        best = max(best, width * min(height[left], height[right]))
        if height[left] < height[right]:
            left += 1     # the shorter wall is the bottleneck -- move it
        else:
            right -= 1
    return best
 
 
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))   # 49
print(max_area([1, 1]))                          # 1

Start as wide as possible and always move the pointer at the shorter wall inward — moving the taller wall could only shrink the width without any chance of increasing the limiting height. Time: $O(n)$ . Space: $O(1)$ .

4. Product of Array Except Self — LC 238 — Medium

Open LC 238 on LeetCode

Pattern: Prefix/suffix accumulation — see Prefix Sums and Difference Arrays.

Problem. Given an integer array nums, return answer where answer[i] equals the product of every element in nums except nums[i], without using division, in $O(n)$ time.

product_except_self.py

def product_except_self(nums):
    # TODO: return an array where each element is the product of all the others
    pass
 
 
# Sample tests (press Run):
print(product_except_self([1, 2, 3, 4]))        # expect [24, 12, 8, 6]
print(product_except_self([-1, 1, 0, -3, 3]))   # expect [0, 0, 9, 0, 0]

Show solution

python

def product_except_self(nums):
    n = len(nums)
    answer = [1] * n
 
    prefix = 1
    for i in range(n):
        answer[i] = prefix          # product of everything to the left of i
        prefix *= nums[i]
 
    suffix = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix         # fold in the product of everything to the right
        suffix *= nums[i]
 
    return answer
 
 
print(product_except_self([1, 2, 3, 4]))        # [24, 12, 8, 6]
print(product_except_self([-1, 1, 0, -3, 3]))   # [0, 0, 9, 0, 0]

Two passes, no division: the first pass fills each slot with the running product of everything to its left; the second pass multiplies in the running product of everything to its right. This is a prefix-sum idea applied to products instead of sums. Time: $O(n)$ . Space: $O(1)$ extra (the output array doesn’t count against most interviewers’ bar).

5. Longest Substring Without Repeating Characters — LC 3 — Medium

Open LC 3 on LeetCode

Pattern: Variable-size Sliding Window — see Sliding Window.

Problem. Given a string s, find the length of the longest substring without repeating characters.

longest_unique_substring.py

def length_of_longest_substring(s):
    # TODO: return the length of the longest substring without repeating characters
    pass
 
 
# Sample tests (press Run):
print(length_of_longest_substring("abcabcbb"))   # expect 3
print(length_of_longest_substring("bbbbb"))      # expect 1
print(length_of_longest_substring(""))           # expect 0

Show solution

python

def length_of_longest_substring(s):
    seen = {}          # char -> last index seen
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1     # jump left past the earlier duplicate
        seen[ch] = right
        best = max(best, right - left + 1)
    return best
 
 
print(length_of_longest_substring("abcabcbb"))   # 3
print(length_of_longest_substring("bbbbb"))      # 1
print(length_of_longest_substring(""))           # 0

right always expands the window; whenever it lands on a character already inside the current window, left jumps to one past that character’s earlier position instead of shrinking one step at a time. Time: $O(n)$ . Space: $O(\min(n, \text{alphabet size}))$ .

6. Group Anagrams — LC 49 — Medium

Open LC 49 on LeetCode

Pattern: Hash Map keyed by a canonical form — see Hash Tables.

Problem. Given an array of strings strs, group the anagrams together. You can return the groups in any order.

group_anagrams.py

def group_anagrams(strs):
    # TODO: group strings that are anagrams of each other
    pass
 
 
# Sample tests (press Run):
result = group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
# Groups can come back in any order, so sort everything before printing:
print(sorted(sorted(group) for group in result))
# expect [['ate', 'eat', 'tea'], ['bat'], ['nat', 'tan']]

Show solution

python

from collections import defaultdict
 
 
def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))    # anagrams share the same sorted form
        groups[key].append(s)
    return list(groups.values())
 
 
result = group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
print(sorted(sorted(group) for group in result))
# [['ate', 'eat', 'tea'], ['bat'], ['nat', 'tan']]

Every anagram of a word shares the same sorted-character key, so sorting each string gives you a free hash-map bucket key. Time: $O(n \cdot k \log k)$ for n strings of max length k. Space: $O(n \cdot k)$ .

7. Trapping Rain Water — LC 42 — Hard

Open LC 42 on LeetCode

Pattern: Two Pointers with running max walls — see Two Pointers.

Problem. Given n non-negative integers height representing an elevation map where each bar has width 1, compute how much water it can trap after raining.

trap.py

def trap(height):
    # TODO: return the total units of water trapped
    pass
 
 
# Sample tests (press Run):
print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))   # expect 6
print(trap([4, 2, 0, 3, 2, 5]))                       # expect 9

Show solution

python

def trap(height):
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            water += left_max - height[left]    # left_max is the real bound here
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]  # right_max is the real bound here
            right -= 1
    return water
 
 
print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))   # 6
print(trap([4, 2, 0, 3, 2, 5]))                       # 9

The water trapped above any bar is bounded by the shorter of the tallest wall to its left and the tallest wall to its right. Whichever side’s current wall is shorter, that side’s bound is already fully determined, so you can safely account for it and move that pointer inward. Time: $O(n)$ . Space: $O(1)$ .

8. Minimum Window Substring — LC 76 — Hard

Open LC 76 on LeetCode

Pattern: Sliding Window + character-count map — see Sliding Window.

Problem. Given strings s and t, return the smallest substring of s that contains every character of t (including duplicates). Return "" if no such substring exists.

min_window.py

def min_window(s, t):
    # TODO: return the smallest substring of s containing all characters of t
    pass
 
 
# Sample tests (press Run):
print(repr(min_window("ADOBECODEBANC", "ABC")))   # expect 'BANC'
print(repr(min_window("a", "a")))                 # expect 'a'
print(repr(min_window("a", "aa")))                # expect ''

Show solution

python

from collections import Counter
 
 
def min_window(s, t):
    if not s or not t:
        return ""
 
    need = Counter(t)          # how many of each character we still need
    missing = len(t)           # total characters still missing from the window
    left = 0
    best_left, best_right = 0, 0
 
    for right, ch in enumerate(s, 1):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
 
        if missing == 0:
            # Shrink from the left while it stays valid.
            while left < right and need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if best_right == 0 or right - left < best_right - best_left:
                best_left, best_right = left, right
            # Kick the window forward by one and keep scanning.
            need[s[left]] += 1
            missing += 1
            left += 1
 
    return s[best_left:best_right]
 
 
print(repr(min_window("ADOBECODEBANC", "ABC")))   # 'BANC'
print(repr(min_window("a", "a")))                 # 'a'
print(repr(min_window("a", "aa")))                # ''

need counts how many of each character are still owed; missing is the total still owed across all characters. right always expands the window; the moment missing hits zero every needed character is covered, so shrink left as far as possible before recording a candidate answer. Time: $O(|s| + |t|)$ . Space: $O(|t|)$ .

Complexity

#	Problem	Naive	Intended	Space	What buys it
1	Two Sum II (sorted)	$O(n^2)$	$O(n)$	$O(1)$	Two pointers — sortedness tells you which end to move
2	3Sum	$O(n^3)$	$O(n^2)$	$O(1)$ beyond the sort	Fix one anchor, two-pointer the rest
3	Container With Most Water	$O(n^2)$	$O(n)$	$O(1)$	Move the shorter wall — the taller one can never improve this pair
4	Product of Array Except Self	$O(n^2)$ , or $O(n)$ with division	$O(n)$ , no division	$O(1)$ extra (output aside)	Prefix pass, then suffix pass in place
5	Longest Substring Without Repeating	$O(n^2)$	$O(n)$	$O(k)$ , `k` distinct chars	Sliding window with last-seen indices
6	Group Anagrams	$O(n^2 k)$ pairwise	$O(nk \log k)$	$O(nk)$	A canonical key per word (sorted, or a 26-count tuple)
7	Trapping Rain Water	$O(n^2)$ per-column scan	$O(n)$	$O(1)$ with two pointers	Water depends only on the smaller of the two running maxima
8	Minimum Window Substring	$O(n^2 m)$	$O(n + m)$	$O(m)$	Window plus a `have`/`need` match counter

Four bounds that get quoted wrongly:

3Sum is $O(n^2)$ , and the sort is not the dominant term. $O(n \log n) + O(n^2) = O(n^2)$ . People sometimes report $O(n^2 \log n)$ by multiplying instead of adding.
Group Anagrams is $O(nk \log k)$ , where k is the word length — the per-word sort dominates. A 26-slot count tuple as the key makes it $O(nk)$ , which is the improvement to offer when asked.
Trapping Rain Water has three solutions at three space bounds: $O(n)$ time / $O(n)$ space with precomputed prefix maxima, $O(n)$ / $O(n)$ with a monotonic stack, and $O(n)$ / $O(1)$ with two pointers. Same time class — the follow-up is always about space.
Sliding-window space is $O(k)$ , not $O(n)$ , where k is the alphabet or distinct-character count. For lowercase ASCII that is $O(1)$ ; saying so is more precise than $O(n)$ .

Drills

Micro-drills on the three lines that decide these problems, each contrasting the correct version against the plausible wrong one.

Drill 1 — the sliding-window `left` guard

Drill 2 — 3Sum needs two kinds of dedupe

Drill 3 — prefix then suffix, no division

Interview follow-ups

They ask	On which problem	The answer
“Why move the shorter wall?”	Container With Most Water	The area is bounded by the shorter wall, so keeping it and moving the taller one can only reduce the width without ever raising the height — that pair is already maximised. Moving the shorter one is the only move that can improve anything
“Why not divide by the total product?”	Product of Array Except Self	LC 238 forbids division, and for good reason: a single zero makes the total zero and the quotient undefined. You would need separate cases for one zero and for two-plus zeros. The prefix/suffix version needs none
“Is the output array counted as extra space?”	Product of Array Except Self	Conventionally no — so the two-pass version is $O(1)$ extra. State the convention rather than assuming the interviewer shares it
“Can you make Group Anagrams faster?”	Group Anagrams	Replace the sorted-string key with a 26-length count tuple: $O(nk)$ instead of $O(nk \log k)$ . The tuple must be hashable — a `tuple`, not a `list`
“Solve Trapping Rain Water in constant space”	Trapping Rain Water	Two pointers with `left_max` and `right_max`; always advance the side with the smaller maximum, because that side’s water level is already determined. $O(n)$ time, $O(1)$ space — versus the $O(n)$ -space prefix-array and monotonic-stack versions
“What if the window characters can repeat up to twice?”	Longest Substring	The last-seen-index jump no longer applies. Switch to a count map and shrink `left` while any count exceeds the allowance — the general form, which also covers LC 340 and 424
“How do you know when the window is valid?”	Minimum Window Substring	A single `have == need` counter over distinct required characters, incremented only when a character’s count reaches its requirement exactly. Comparing whole dictionaries each step is what turns $O(n)$ into $O(nm)$
“3Sum for a target other than zero?”	3Sum	Identical, comparing `total` against the target. 3Sum Closest tracks the minimum absolute difference instead of exact hits — and then you never break early
“Extend to 4Sum”	3Sum	Two nested anchors plus the two-pointer core: $O(n^3)$ . The general `kSum` recursion bottoms out at the two-pointer case, and the same two-level dedupe applies at every level
“Your 3Sum returns duplicates”	3Sum	Two separate dedupes are needed: skip an anchor equal to the previous anchor, and skip repeated `lo`/`hi` values after recording a hit. Missing either one produces duplicate triplets
“What is the complexity of 3Sum, exactly?”	3Sum	$O(n^2)$ . The sort is $O(n \log n)$ and is added, not multiplied — quoting $O(n^2 \log n)$ is the standard slip

Practice

Every problem on this page, generated from the problem database — so each row carries its sheet membership and reported companies, and the checkboxes remember what you have finished. The walkthroughs above are the teaching; this is the tracker.

8 problems

0 easy6 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

Unsolved onlyImport

3Longest Substring Without Repeating CharactersmediumNeetCode 150Blind 75LeetCode Top Interview 150amazongooglemetamicrosoftbloomberg
153SummediumNeetCode 150Blind 75LeetCode Top Interview 150amazonmetamicrosoftapplebloomberg
11Container With Most WatermediumNeetCode 150Blind 75LeetCode Top Interview 150amazonmetabloomberg
49Group AnagramsmediumNeetCode 150Blind 75LeetCode Top Interview 150amazonmetauberbloomberg
238Product of Array Except SelfmediumNeetCode 150Blind 75LeetCode Top Interview 150amazonmetamicrosoftapple
167Two Sum II - Input Array Is SortedmediumNeetCode 150LeetCode Top Interview 150
42Trapping Rain WaterhardNeetCode 150LeetCode Top Interview 150amazongooglemetabloomberg
76Minimum Window SubstringhardNeetCode 150Blind 75LeetCode Top Interview 150metaamazongoogleuber

Self-check

pch.quizTag pch.quizDefaultTitle

In the sliding-window solution to Longest Substring Without Repeating Characters, why is the guard `last[ch] >= left` needed?

pch.quizShowAnswer

B — A repeat from before the window would otherwise drag `left` backwards, letting duplicates back in — Measured on "abba": correct answer 2, unguarded answer 3. The second b sends left to index 2, then the second a -- last seen at index 0, before the window -- sends it back to 1, so the window spans two a values. Note both versions return 3 on "abcabcbb", the usual sample, which is why this ships.
Container With Most Water: why is moving the shorter wall the correct greedy step?

pch.quizShowAnswer

B — The area is capped by the shorter wall, so keeping it can only lose width without gaining height -- that pair is already at its best — Every pair involving the current shorter wall is bounded by its height, and width only shrinks as the pointers close. So the best possible area for that wall is the one you just computed -- there is nothing left to find with it, and discarding it is safe. Moving the taller wall keeps the same cap with less width, which can never improve.
Why does LC 238 forbid division, beyond it being an artificial constraint?

pch.quizShowAnswer

B — A single zero makes the total product zero, so the quotient is undefined -- and you would need separate cases for one zero versus two or more — The prefix/suffix version handles [-1,1,0,-3,3] -> [0,0,9,0,0] and [0,0] -> [0,0] with no branches, because each slot only ever multiplies values other than itself. A divide-the-total solution needs to count the zeros first and then special-case both counts. The constraint is pushing you toward the cleaner algorithm.
What is 3Sum's time complexity?

pch.quizShowAnswer

B — O(n^2) -- the sort is O(n log n) and is added, not multiplied — Sort once up front, then n anchors each running an O(n) two-pointer scan: O(n log n) + O(n^2) = O(n^2). Multiplying the sort into the loop is the standard slip. Space is O(1) beyond the sort, since the two-pointer pass allocates nothing per anchor.
Your 3Sum returns [[0,0,0],[0,0,0]] for input [0,0,0,0]. What is missing?

pch.quizShowAnswer

B — Anchor dedupe -- `if i > 0 and nums[i] == nums[i-1]: continue` -- and/or the pointer-value dedupe after recording a hit — Two dedupes do two different jobs. Skipping a repeated anchor stops the same triplet being found from a different i; skipping repeated lo/hi values stops it being found twice within one anchor. [0,0,0,0] must give exactly one triplet, and it is the input that exercises both.
Trapping Rain Water: how do you get O(1) space?

pch.quizShowAnswer

B — Two pointers with left_max and right_max, always advancing the side whose maximum is smaller — The water above any column is decided by the smaller of the two bounding maxima, so whichever side has the smaller max is already determined and can be finalised and advanced. All three listed approaches are O(n) time; the prefix arrays and the stack are O(n) space, and only the two-pointer version is O(1). The space follow-up is the whole point of asking this problem.
Group Anagrams: how would you improve on sorting each word as the key?

pch.quizShowAnswer

B — Use a 26-length tuple of letter counts as the key -- O(nk) instead of O(nk log k) — Counting is linear in the word length where sorting is k log k, so the total drops from O(nk log k) to O(nk). The key must be hashable -- a tuple, not a list, which is the practical detail. A rolling hash risks collisions for no asymptotic gain, and pairwise comparison is O(n^2 k), strictly worse than either.
Minimum Window Substring: how do you check window validity in O(1) per step?

pch.quizShowAnswer

B — Keep a `have` count of distinct characters that have met their requirement, and compare it against `need` — Increment `have` only when a character's count reaches its requirement *exactly*, and decrement when it drops below -- so validity is one integer comparison. Comparing whole dictionaries is O(m) per step, which turns the overall O(n + m) into O(nm) and is the usual reason this problem times out.

Recap

Sorted input almost always means two pointers over a hash set — Two Sum II and 3Sum both lean on that.
Container With Most Water and Trapping Rain Water both use opposite-end pointers, but Trapping Rain Water needs a running max on each side to know how much water each bar can actually hold.
Product of Array Except Self turns a prefix-sum habit into a prefix-product habit.
Sliding windows can track more than a length or a sum — Longest Substring Without Repeating Characters and Minimum Window Substring both carry a character-count map alongside the window.

Next: Trees and Graphs Problem Set — the same run-fix-run loop, applied to binary trees and graphs, from a plain depth check up through BFS shortest paths in Word Ladder.

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading

Arrays and Strings Problem Set

What you’ll learn

How to use this set

Problems

1. Two Sum II (Input Array Is Sorted) — LC 167 — Medium

2. 3Sum — LC 15 — Medium

3. Container With Most Water — LC 11 — Medium

4. Product of Array Except Self — LC 238 — Medium

5. Longest Substring Without Repeating Characters — LC 3 — Medium

6. Group Anagrams — LC 49 — Medium

7. Trapping Rain Water — LC 42 — Hard

8. Minimum Window Substring — LC 76 — Hard

Complexity

Drills

Drill 1 — the sliding-window left guard

Drill 2 — 3Sum needs two kinds of dedupe

Drill 3 — prefix then suffix, no division

Interview follow-ups

Practice

Self-check

Recap

pch.feedbackHeading

Drill 1 — the sliding-window `left` guard