Arrays & Strings: 12 problems from brute force to optimal

All complexities use n for the input length. “Space” means extra space beyond the input and the required output.

#	Problem	Brute force	Optimal	Optimal space
1	Two Sum	`O(n²)`	`O(n)`	`O(n)`
125	Valid Palindrome	`O(n)`, `O(n)` space	`O(n)`	`O(1)`
242	Valid Anagram	`O(n²)`	`O(n)`	`O(1)`
121	Best Time to Buy and Sell Stock	`O(n²)`	`O(n)`	`O(1)`
238	Product of Array Except Self	`O(n²)`	`O(n)`	`O(1)`
27	Remove Element	`O(n²)`	`O(n)`	`O(1)`
283	Move Zeroes	`O(n)`, `O(n)` space	`O(n)`	`O(1)`
189	Rotate Array	`O(n·k)`	`O(n)`	`O(1)`
344	Reverse String	`O(n)`, `O(n)` space	`O(n)`	`O(1)`
14	Longest Common Prefix	`O(n·m²)`	`O(S)`	`O(1)`
567	Permutation in String	`O(n·m log m)`	`O(n)`	`O(1)`
3	Longest Substring Without Repeating Characters	`O(n³)`	`O(n)`	`O(k)`

1. Two Sum

Return the indices of the two numbers that add up to target. Exactly one answer exists.

Approach	Time	Space
Brute force: try every pair	`O(n²)`	`O(1)`
Better: sort the indices, then two pointers	`O(n log n)`	`O(n)`
Optimal: one pass with a hash map	`O(n)`	`O(n)`

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

def two_sum_sorted(nums, target):
    order = sorted(range(len(nums)), key=nums.__getitem__)  # indices, sorted by value
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[order[lo]] + nums[order[hi]]
        if s == target:
            return sorted([order[lo], order[hi]])
        if s < target:
            lo += 1
        else:
            hi -= 1
    return []

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

Key insight: for each number, the partner it needs is fixed (target - x). A hash map answers “have I seen it?” in O(1), so one pass is enough. Sorting would lose the original indices, which is why the sorted version sorts indices by value.

125. Valid Palindrome

Is the string a palindrome after lowercasing and dropping non-alphanumeric characters?

Approach	Time	Space
Brute force: build the cleaned string, compare with its reverse	`O(n)`	`O(n)`
Optimal: two pointers that skip junk	`O(n)`	`O(1)`

def is_palindrome_brute(s):
    cleaned = [c.lower() for c in s if c.isalnum()]
    return cleaned == cleaned[::-1]

def is_palindrome(s):
    lo, hi = 0, len(s) - 1
    while lo < hi:
        while lo < hi and not s[lo].isalnum():
            lo += 1
        while lo < hi and not s[hi].isalnum():
            hi -= 1
        if s[lo].lower() != s[hi].lower():
            return False
        lo += 1
        hi -= 1
    return True

Key insight: the time is already linear; the improvement is space. Compare from both ends and skip characters that don’t count, instead of materializing a cleaned copy.

242. Valid Anagram

Do s and t contain exactly the same letters with the same counts? (Lowercase English letters.)

Approach	Time	Space
Brute force: remove each letter of `s` from a list of `t`	`O(n²)`	`O(n)`
Better: sort both and compare	`O(n log n)`	`O(n)`
Optimal: one count array of 26	`O(n)`	`O(1)`

def is_anagram_brute(s, t):
    if len(s) != len(t):
        return False
    remaining = list(t)
    for c in s:
        if c not in remaining:
            return False
        remaining.remove(c)  # O(n) search and shift
    return True

def is_anagram_sorted(s, t):
    return sorted(s) == sorted(t)

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26
    for a, b in zip(s, t):
        counts[ord(a) - ord("a")] += 1
        counts[ord(b) - ord("a")] -= 1
    return all(c == 0 for c in counts)

Key insight: an anagram is a multiset comparison, and a fixed alphabet makes the multiset a 26-slot array. Increment for s, decrement for t, and check for all zeros. For Unicode input, a dictionary (collections.Counter) gives O(n) time and O(k) space for k distinct characters.

121. Best Time to Buy and Sell Stock

Buy on one day and sell on a later day; return the maximum profit, or 0.

Approach	Time	Space
Brute force: every buy/sell pair	`O(n²)`	`O(1)`
Optimal: track the lowest price so far	`O(n)`	`O(1)`

def max_profit_brute(prices):
    best = 0
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            best = max(best, prices[j] - prices[i])
    return best

def max_profit(prices):
    best, low = 0, float("inf")
    for p in prices:
        low = min(low, p)  # cheapest day to have bought, up to today
        best = max(best, p - low)  # sell today
    return best

Key insight: for each selling day, the only buy day that matters is the cheapest one before it. Carry that minimum forward instead of searching for it.

238. Product of Array Except Self

Return out[i] = the product of every element except nums[i], without using division, in O(n).

Approach	Time	Space
Brute force: multiply everything else for each `i`	`O(n²)`	`O(1)`
Better: prefix-product and suffix-product arrays	`O(n)`	`O(n)`
Optimal: prefix products in the output, suffix as a running variable	`O(n)`	`O(1)`

def product_except_self_brute(nums):
    out = []
    for i in range(len(nums)):
        p = 1
        for j, x in enumerate(nums):
            if j != i:
                p *= x
        out.append(p)
    return out

def product_except_self_arrays(nums):
    n = len(nums)
    prefix, suffix = [1] * n, [1] * n
    for i in range(1, n):
        prefix[i] = prefix[i - 1] * nums[i - 1]  # product of everything left of i
    for i in range(n - 2, -1, -1):
        suffix[i] = suffix[i + 1] * nums[i + 1]  # product of everything right of i
    return [prefix[i] * suffix[i] for i in range(n)]

def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    for i in range(1, n):
        out[i] = out[i - 1] * nums[i - 1]  # prefix products
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right  # times the product of everything to the right
        right *= nums[i]
    return out

Key insight: “everything except i” is “everything left of i” times “everything right of i”, and both are running products. Dividing the total product by nums[i] looks simpler but breaks on zeros, and the problem forbids it.

27. Remove Element

Remove every occurrence of val in place and return the count k of remaining elements, which must occupy the first k slots in any order.

Approach	Time	Space
Brute force: shift everything left on each match	`O(n²)`	`O(1)`
Optimal: read/write pointers	`O(n)`	`O(1)`
Optimal, fewer writes: swap matches with the end	`O(n)`	`O(1)`

def remove_element_brute(nums, val):
    n, i = len(nums), 0
    while i < n:
        if nums[i] == val:
            for j in range(i + 1, n):
                nums[j - 1] = nums[j]
            n -= 1
        else:
            i += 1
    return n

def remove_element(nums, val):
    k = 0  # next slot to write
    for x in nums:
        if x != val:
            nums[k] = x
            k += 1
    return k

def remove_element_swap(nums, val):
    i, n = 0, len(nums)
    while i < n:
        if nums[i] == val:
            n -= 1
            nums[i] = nums[n]  # overwrite with the last live element; recheck i
        else:
            i += 1
    return n

Key insight: a fast “read” index scans everything, a slow “write” index marks where the next keeper goes. Each element moves at most once.

283. Move Zeroes

Move all zeros to the end in place, keeping the order of the non-zero elements.

Approach	Time	Space
Brute force: copy non-zeros to a new list, pad with zeros	`O(n)`	`O(n)`
Optimal: swap non-zeros forward with a write pointer	`O(n)`	`O(1)`

def move_zeroes_brute(nums):
    non_zero = [x for x in nums if x != 0]
    nums[:] = non_zero + [0] * (len(nums) - len(non_zero))

def move_zeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1

Key insight: the same read/write pattern as Remove Element. Swapping instead of overwriting leaves the zeros behind automatically, so no second pass is needed to fill them in.

189. Rotate Array

Rotate the array to the right by k steps, in place.

Approach	Time	Space
Brute force: rotate by one, `k` times	`O(n·k)`	`O(1)`
Better: place each element at `(i + k) % n` in a new array	`O(n)`	`O(n)`
Optimal: three reversals	`O(n)`	`O(1)`

def rotate_brute(nums, k):
    n = len(nums)
    for _ in range(k % n):
        last = nums[-1]
        for i in range(n - 1, 0, -1):
            nums[i] = nums[i - 1]
        nums[0] = last

def rotate_extra(nums, k):
    n = len(nums)
    rotated = [0] * n
    for i, x in enumerate(nums):
        rotated[(i + k) % n] = x
    nums[:] = rotated

def rotate(nums, k):
    def reverse(lo, hi):
        while lo < hi:
            nums[lo], nums[hi] = nums[hi], nums[lo]
            lo += 1
            hi -= 1

    n = len(nums)
    k %= n  # rotating by n is a no-op
    reverse(0, n - 1)  # [1 2 3 4 5 6 7], k=3 -> [7 6 5 4 3 2 1]
    reverse(0, k - 1)  #                       -> [5 6 7 4 3 2 1]
    reverse(k, n - 1)  #                       -> [5 6 7 1 2 3 4]

Key insight: rotation moves the last k elements to the front without changing order inside either block. Reversing the whole array puts the blocks in the right places but backwards; reversing each block fixes them. Always reduce k modulo n first.

344. Reverse String

Reverse a list of characters in place.

Approach	Time	Space
Brute force: build a reversed copy, write it back	`O(n)`	`O(n)`
Optimal: swap from both ends	`O(n)`	`O(1)`

def reverse_string_brute(s):
    s[:] = s[::-1]

def reverse_string(s):
    lo, hi = 0, len(s) - 1
    while lo < hi:
        s[lo], s[hi] = s[hi], s[lo]
        lo += 1
        hi -= 1

Key insight: the simplest two-pointer pattern: pointers start at opposite ends and swap until they meet, n / 2 swaps in total.

14. Longest Common Prefix

Return the longest prefix shared by every string in the list. Below, n is the number of strings, m the length of the shortest one, L the length of the longest, and S the total number of characters.

Approach	Time	Space
Brute force: try every prefix length, check all strings	`O(n·m²)`	`O(m)`
Better: sort, compare only the first and last	`O(L·n log n)`	`O(n)`
Optimal: vertical scan, column by column	`O(S)`	`O(1)`

def longest_common_prefix_brute(strs):
    best = ""
    for length in range(1, len(strs[0]) + 1):
        prefix = strs[0][:length]
        if all(s.startswith(prefix) for s in strs):
            best = prefix
        else:
            break
    return best

def longest_common_prefix_sorted(strs):
    ordered = sorted(strs)
    first, last = ordered[0], ordered[-1]  # the two most different strings
    i = 0
    while i < min(len(first), len(last)) and first[i] == last[i]:
        i += 1
    return first[:i]

def longest_common_prefix(strs):
    for i, ch in enumerate(strs[0]):
        for s in strs[1:]:
            if i == len(s) or s[i] != ch:
                return strs[0][:i]
    return strs[0]

Key insight: compare one column at a time across all strings and stop at the first mismatch, so no character past the answer is read more than once. The sorting trick works because, in lexicographic order, the prefix shared by the first and last strings is shared by everything between them.

567. Permutation in String

Does s2 contain a substring that is a permutation of s1? Here m = len(s1), n = len(s2), lowercase letters only.

Approach	Time	Space
Brute force: sort every window of length m, compare with sorted `s1`	`O(n·m log m)`	`O(m)`
Better: slide a 26-count window, compare whole count arrays	`O(26·n)`	`O(1)`
Optimal: slide the window and track how many letters match	`O(n)`	`O(1)`

def check_inclusion_brute(s1, s2):
    target, m = sorted(s1), len(s1)
    return any(sorted(s2[i : i + m]) == target for i in range(len(s2) - m + 1))

def check_inclusion_counts(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need, window = [0] * 26, [0] * 26
    for c in s1:
        need[ord(c) - 97] += 1
    for i, c in enumerate(s2):
        window[ord(c) - 97] += 1
        if i >= m:
            window[ord(s2[i - m]) - 97] -= 1  # drop the char that left the window
        if window == need:  # 26 comparisons per step
            return True
    return False

def check_inclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    diff = [0] * 26  # window count minus s1 count, per letter
    for c in s1:
        diff[ord(c) - 97] -= 1
    zeros = sum(d == 0 for d in diff)  # letters whose counts already agree

    def update(c, delta):
        nonlocal zeros
        i = ord(c) - 97
        zeros -= diff[i] == 0
        diff[i] += delta
        zeros += diff[i] == 0

    for i, c in enumerate(s2):
        update(c, +1)
        if i >= m:
            update(s2[i - m], -1)
        if zeros == 26:
            return True
    return False

Key insight: “is a permutation of” means “has the same letter counts”. Moving the window changes only two counts, so update them instead of recounting. The optimal version goes one step further and maintains how many of the 26 counts agree, making each step O(1) instead of O(26).

3. Longest Substring Without Repeating Characters

Return the length of the longest substring with no repeated character. k is the alphabet size.

Approach	Time	Space
Brute force: check every substring for duplicates	`O(n³)`	`O(k)`
Better: from each start, extend until a repeat	`O(n²)`	`O(k)`
Optimal: sliding window that jumps past the previous occurrence	`O(n)`	`O(k)`

def length_of_longest_substring_brute(s):
    best = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            if len(set(s[i:j])) == j - i:  # O(n) check per substring
                best = max(best, j - i)
    return best

def length_of_longest_substring_extend(s):
    best = 0
    for i in range(len(s)):
        seen = set()
        for j in range(i, len(s)):
            if s[j] in seen:
                break
            seen.add(s[j])
        best = max(best, len(seen))
    return best

def length_of_longest_substring(s):
    last = {}  # char -> index of its latest occurrence
    best = start = 0
    for i, c in enumerate(s):
        if last.get(c, -1) >= start:
            start = last[c] + 1  # jump the window start past the repeat
        last[c] = i
        best = max(best, i - start + 1)
    return best

Key insight: when a repeat appears, every window starting at or before its previous occurrence is also invalid, so the start can jump straight past it. Both ends only move forward, so the whole scan is linear.

Patterns to remember

Seen a nested loop searching for a partner? Try a hash map of what you need.
Re-computing a sum, product, or minimum over a prefix? Carry it in a variable.
“In place” plus “keep order”? A read index and a write index.
“Substring with some property” plus “only counts matter”? A sliding window with incremental counts.