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# TODO, press Run, and match the printed output to the # expect# 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 numbersnumbers sorted in non-decreasing order, return the 1-indexed positions [index1, index2][index1, index2] of the two numbers that add up to targettarget. 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]

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]

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 numsnums, return all unique triplets [nums[i], nums[j], nums[k]][nums[i], nums[j], nums[k]] (distinct indices) whose values sum to 00. 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]]

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]]

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 ii in turn and run the opposite-ends two-pointer scan on the remainder for a target of -nums[i]-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 heightheight, an array where height[i]height[i] is the height of a vertical line at position ii, 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

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

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 numsnums, return answeranswer where answer[i]answer[i] equals the product of every element in numsnums except nums[i]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]

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]

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 ss, 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

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

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

rightright always expands the window; whenever it lands on a character already inside the current window, leftleft 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 strsstrs, 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']]

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']]

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 nn strings of max length kk. 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 nn non-negative integers heightheight 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

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

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 ss and tt, return the smallest substring of ss that contains every character of tt (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 ''

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")))                # ''

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")))                # ''

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

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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

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

Recap

Was this page helpful?