PYTHON DSA
The Problem Solving Playbook

Given a non-empty list of numbers, return the largest value. (Python's built-in max() does this — but the point is to build the pattern by hand once.)

nums = [3, 9, 2, 9, 5] → 9

You do not need to compare every pair. If you know the largest of the first k elements, one comparison against element k+1 updates your knowledge. One pass suffices.

Compare every element with every other element, O(n²) — checking whether some value beats all others. It works, but each element gets re-examined many times.

Keep a champion best. Walk the list once; if the current element beats the champion, crown it. The repeated work that disappears: re-comparing already-seen elements against each other.

def find_max(nums):
    best = nums[0]          # assume the first element is the champion
    for x in nums:
        if x > best:        # challenger wins
            best = x
    return best

start : best = 3
x = 3 : 3 > 3?  ❌   best = 3
x = 9 : 9 > 3?  ✅   best = 9
x = 2 : 2 > 9?  ❌   best = 9
x = 9 : 9 > 9?  ❌   best = 9   (equal does not beat the champion)
x = 5 : 5 > 9?  ❌   best = 9
return 9

Time O(n) — each element is challenged once · Space O(1) — one variable.

• All-negative list, e.g. [-8, -3, -5] → -3. This is why we start best = nums[0], not best = 0.
• Single element → that element (the loop simply never updates).
• Empty list → undefined; either raise an error or return None deliberately.

• Initializing best = 0 — silently wrong for all-negative input.
• Starting the loop at index 0 with best = nums[0] is fine, but if you start best at index 0 you may also begin the loop at index 1 — a micro-optimization, not a correctness issue.
• Using >= instead of > — same answer here, but the habit breaks "first index of maximum" style variants.

Return the second largest distinct value in the list. If it does not exist (fewer than two distinct values), return None.

nums = [3, 9, 2, 9, 5] → 5  ·  nums = [7, 7, 7] → None

Sorting is tempting but fragile: sorted([9, 9, 2])[-2] is 9, not 2 — duplicates betray you. What you really need is to track two champions: the best and the best among the rest.

Sort a copy and walk backwards from the end until the value differs from the maximum. O(n log n), plus a subtle loop most people get wrong on the first try.

Two passes: pass 1 finds the maximum; pass 2 finds the largest value strictly smaller than it. O(n) time, and the "distinct" requirement is handled by x != best.

def second_largest(nums):
    best = None
    second = None
    for x in nums:
        if best is None or x > best:
            second = best        # old champion is demoted to runner-up
            best = x
        elif x != best and (second is None or x > second):
            second = x           # new runner-up
    return second

def second_largest_two_pass(nums):
    best = nums[0]
    for x in nums:
        if x > best:
            best = x
    second = None
    for x in nums:
        if x != best and (second is None or x > second):
            second = x
    return second

x = 3 : best is None      → second = None, best = 3
x = 9 : 9 > 3             → second = 3,    best = 9
x = 2 : 2 != 9, 2 > 3?    ❌  (no change)
x = 9 : 9 > 9? ❌; 9 != 9? ❌  (duplicate champion ignored)
x = 5 : 5 != 9, 5 > 3     → second = 5
return 5  ✅

One-pass version: Time O(n) · Space O(1). Two-pass: O(2n) = O(n) · O(1).

• [7, 7, 7] → None (only one distinct value).
• Two elements [1, 2] → 1.
• Negatives [-5, -2, -9] → -5; using None sentinels (not 0!) is what makes this safe.

• Initializing second = 0 or second = -1 — breaks on negative input.
• Forgetting the x != best guard, so duplicates of the maximum become the runner-up.
• Updating second before best when a new champion arrives — you lose the old champion.

Given a list, return a new list containing each distinct value once, in the order the value first appeared.

nums = [4, 2, 4, 7, 2, 9] → [4, 2, 7, 9]

For each element the question is "have I seen this before?" — a membership test. A list membership test is O(n); a set membership test is O(1). Same logic, radically different total cost.

Append x only if x not in result. Correct, but in on a list scans it, giving O(n²) overall — fine for 1,000 elements, painful for 1,000,000.

Keep a seen set alongside the result list. The repeated work that disappears: scanning the output to test membership.

def remove_duplicates(nums):
    seen = set()
    result = []
    for x in nums:
        if x not in seen:      # first time we meet x
            seen.add(x)
            result.append(x)
    return result

# Brute force for contrast — same output, O(n^2):
# if x not in result: result.append(x)

x = 4 : 4 in seen? ❌ → seen={4}      result=[4]
x = 2 : 2 in seen? ❌ → seen={2, 4}   result=[4, 2]
x = 4 : 4 in seen? ✅ skip
x = 7 : 7 in seen? ❌ → seen={2, 4, 7} result=[4, 2, 7]
x = 2 : 2 in seen? ✅ skip
x = 9 : 9 in seen? ❌ → seen={2, 4, 7, 9} result=[4, 2, 7, 9]

Time O(n) · Space O(n) for the set and result.

• Empty list → [].
• All duplicates [5, 5, 5] → [5].
• Already unique → returned unchanged, in the same order.

• Using list(set(nums)) — it destroys the required first-occurrence order.
• Mutating nums while looping over it (see Pitfalls below) instead of building a separate result.

Move all 0s to the end of the list while keeping the relative order of the non-zero elements. Modify the list in place; do not return a new list.

nums = [0, 1, 0, 3, 12] → [1, 3, 12, 0, 0]

Non-zero elements keep their order — so imagine writing the keepers to the front one by one, then padding the tail with zeros. A write pointer (left) marks the next free front slot; a read pointer (right) scans every element.

Build [x for x in nums if x != 0], then append zeros to match the original length and copy back. O(n) time but O(n) extra space — the statement demands in-place, so this only qualifies as a stepping stone.

def move_zeroes_fill(nums):
    insert_pos = 0
    for x in nums:
        if x != 0:
            nums[insert_pos] = x   # write the keeper forward
            insert_pos += 1
    for i in range(insert_pos, len(nums)):
        nums[i] = 0                # pad the tail with zeroes

The fill version makes two passes. A single pass can swap each keeper directly into its final slot — after every swap, everything before left is exactly the non-zero elements seen so far, in order.

def move_zeroes(nums):
    left = 0                        # next slot for a non-zero
    for right in range(len(nums)):
        if nums[right] != 0:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1

right=0: nums[0]=0  → skip            [0, 1, 0, 3, 12]  left=0
right=1: nums[1]=1  → swap 0,1        [1, 0, 0, 3, 12]  left=1
right=2: nums[2]=0  → skip            [1, 0, 0, 3, 12]  left=1
right=3: nums[3]=3  → swap 0,3        [1, 3, 0, 0, 12]  left=2
right=4: nums[4]=12 → swap 0,12       [1, 3, 12, 0, 0]  left=3
✅ done — non-zero order preserved (1, 3, 12)

Time O(n) — each element visited once · Space O(1) — true in-place.

• No zeros → the swaps are self-swaps; the list is unchanged.
• All zeros → left never moves; nothing to do.
• Zeros already at the end → also unchanged.

• Swapping when nums[right] == 0 — you would shuffle zeros into the front.
• Forgetting left += 1 after a swap, overwriting the same slot forever.
• Using nums.remove(0) in a loop: O(n) per call and it mutates the list you are iterating.

A list holds n distinct numbers taken from 0, 1, …, n. Exactly one of them is missing. Find it.

nums = [3, 0, 1] → 2  ·  nums = [9, 6, 4, 2, 3, 5, 7, 0, 1] → 8

The list is almost the full set 0…n. The sum of the full set is n·(n+1)/2 (Gauss's formula). Whatever the sum of the list falls short by is exactly the missing value. No searching, no sorting — arithmetic.

For each candidate v in 0…n, check v not in nums. Correct, but every membership check is O(n) — O(n²) total.

Sort a copy, then report the first index i where s[i] != i. O(n log n) — sorting buys order but costs more than we need.

def missing_number(nums):
    n = len(nums)                    # values run from 0 to n
    expected = n * (n + 1) // 2      # 0 + 1 + ... + n
    actual = sum(nums)
    return expected - actual

# Sorting version for contrast:
# s = sorted(nums)
# for i in range(len(s)):
#     if s[i] != i:
#         return i
# return len(s)

n        = 9            (so values should span 0..9)
expected = 9·10/2 = 45
actual   = 9+6+4+2+3+5+7+0+1 = 37
missing  = 45 - 37 = 8  ✅

Time O(n) — one sum() pass · Space O(1).

• Missing value is 0: nums = [1] → n = 1, expected = 1·2/2 = 1, sum(nums) = 1 → 1 − 1 = 0 ✅.
• Missing value is n itself: [0, 1] → expected 3, actual 1 → 2 ✅.
• The repeated work that disappears versus brute force: every per-candidate membership scan — replaced by one subtraction.

• Using n(n+1)/2 with / instead of // — you get a float like 2.0, and the return type is wrong.
• Setting n = len(nums) - 1: the list has n elements but the range spans n+1 values (one is missing!).
• Integer overflow — a real concern in C/Java, a non-issue in Python (arbitrary precision integers). Know why you get away with it here.

Rotate the list to the right by k steps, in place: each element moves k slots forward, and elements that fall off the end re-enter at the front.

nums = [1, 2, 3, 4, 5, 6, 7], k = 3 → [5, 6, 7, 1, 2, 3, 4]

Rotating right by k means: the last k elements jump to the front. Look at the answer in two blocks: [5, 6, 7] + [1, 2, 3, 4]. Both blocks are in their original internal order — they were just cut and swapped. And a cut-and-swap is exactly what three reversals produce.

Rotate one step at a time, k times: pop the last element and insert it at the front. Each step costs O(n) because insert(0, …) shifts everything — O(n·k) total. For n = 100,000 and k = 99,999 that is about ten billion moves.

def rotate_naive(nums, k):
    n = len(nums)
    if n == 0:
        return nums
    k = k % n                     # k full cycles change nothing
    for _ in range(k):
        last = nums.pop()         # O(1)  — take from the end
        nums.insert(0, last)      # O(n)! — shift the whole list
    return nums

def rotate_extra(nums, k):
    n = len(nums)
    if n == 0:
        return nums
    k = k % n
    nums[:] = nums[-k:] + nums[:-k]   # last k block + first block
    return nums

def rotate(nums, k):
    n = len(nums)
    if n == 0:
        return nums
    k = k % n

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

    reverse(0, n - 1)     # step 1: flip everything
    reverse(0, k - 1)     # step 2: flip the first k back
    reverse(k, n - 1)     # step 3: flip the rest back
    return nums

k = 3 % 7 = 3
reverse(0, 6):  [7, 6, 5, 4, 3, 2, 1]
reverse(0, 2):  [5, 6, 7, 4, 3, 2, 1]
reverse(3, 6):  [5, 6, 7, 1, 2, 3, 4]  ✅

Reversal trick: Time O(n) · Space O(1). Extra-array: Time O(n) · Space O(n). Naive: Time O(n·k) · Space O(1).

• k > n: rotating 7 slots on a 7-element list restores the original — so always k = k % n first. k = 10 on the array above behaves exactly like k = 3.
• k = 0 or k % n == 0 → array unchanged: the middle call reverse(0, k - 1) becomes reverse(0, -1), a no-op when lo > hi, and the first and last calls each flip the whole array — two full reversals cancel out.
• Single element → any k leaves it as is.

• Forgetting k %= n — wasted work at best, and index trouble in some variants.
• Reversing segments in the wrong order (first-k then tail then whole — gives a different, wrong result).
• Confusing "rotate right" with "rotate left": left by k is the mirror image — reverse the first n−k, then the last k, then the whole.

prices[i] is a stock's price on day i. Choose one day to buy and one later day to sell. Return the maximum profit; if no profit is possible, return 0.

prices = [7, 1, 5, 3, 6, 4] → 5 (buy at 1, sell at 6)  ·  prices = [7, 6, 4, 3, 1] → 0

The best profit selling on day i is prices[i] − (cheapest price before day i). So if you always know the minimum price seen so far, each day needs only one comparison. That "so far" quantity is the running-minimum idea from the prefix/suffix toolbox.

Try every buy day i with every sell day j > i and keep the best difference — every pair, O(n²). What repeats: for each buy day, we rescan the whole future to find its best sell day.

Flip the question: for each sell day, what is the best buy day? It is always "the cheapest day before it". Maintain min_so_far in one pass — the rescan of the past disappears.

def max_profit(prices):
    min_so_far = prices[0]   # cheapest price seen up to today
    best = 0                 # best profit achievable so far
    for price in prices:
        if price < min_so_far:
            min_so_far = price            # a cheaper buy day appeared
        elif price - min_so_far > best:
            best = price - min_so_far     # selling today beats the record
    return best

start:     min_so_far = 7, best = 0
price = 7: 7 < 7? ❌ → profit 7-7 = 0;  best = 0
price = 1: 1 < 7? ✅ → min_so_far = 1
price = 5: 5 < 1? ❌ → profit 5-1 = 4 → best = 4
price = 3: 3 < 1? ❌ → profit 3-1 = 2;  best stays 4
price = 6: 6 < 1? ❌ → profit 6-1 = 5 → best = 5
price = 4: 4 < 1? ❌ → profit 4-1 = 3;  best stays 5
return 5  ✅  (buy day index 1 at 1, sell day index 4 at 6)

Time O(n) — one pass · Space O(1) — two variables. The O(n²) pair loop is reduced to O(n) because the history of prices collapses into one number: its minimum.

• Strictly falling prices [7, 6, 4, 3, 1] → 0 (never a negative profit — we simply never sell).
• Single price → 0 (you cannot buy and sell on the same day for profit).
• Best buy is the last day, best sell the first — impossible ordering; the code never sells before buying because min_so_far only knows the past.

• Updating min_so_far after computing the profit for the same day — then you could "buy and sell on the same day". Here the if/elif order makes buying on day i and selling on day i mutually exclusive, which is what we want.
• Initializing best = -1 or min_so_far = 0.
• Trying to track both the min and its index when the problem only asks for the profit.

Find the contiguous subarray with the largest sum and return that sum (the subarray must contain at least one element).

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6 (the window [4, -1, 2, 1])

Every subarray ends somewhere. So the answer is the best of the question "what is the best subarray that ends exactly here?" asked at each position — n sub-questions instead of n² windows. And each sub-question is answerable from the previous one in O(1).

Score every window: for each start i, extend the end j while accumulating the total. O(n²) with a running total (O(n³) if you re-sum each window from scratch).

Keep current = the best sum of a subarray that ends at the element we are standing on. When the next element x arrives there are only two choices, and one of them is always best:

• Extend the previous run: current + x — worth it when the previous run helps, i.e. current is positive enough.
• Restart here: just x — better when the previous run is a liability (its sum is so low that carrying it hurts).

So: current = max(x, current + x), and the global answer best = max(best, current). The repeated work that disappears: re-summing overlapping windows — each ending position keeps exactly one number.

def max_subarray_sum(nums):
    current = nums[0]   # best subarray sum ENDING at the current element
    best = nums[0]      # best ending anywhere so far
    for i in range(1, len(nums)):
        current = max(nums[i], current + nums[i])  # restart, or extend
        best = max(best, current)
    return best

# Brute force for contrast — O(n^2):
# best = nums[0]
# for i in range(len(nums)):
#     total = 0
#     for j in range(i, len(nums)):
#         total += nums[j]          # window nums[i..j]
#         best = max(best, total)

start:         current = -2, best = -2
i=1, x =  1 :  current = max( 1, -2+1) = max( 1, -1) =  1  → restart   best = 1
i=2, x = -3 :  current = max(-3,  1-3) = max(-3, -2) = -2  → extend    best = 1
i=3, x =  4 :  current = max( 4, -2+4) = max( 4,  2) =  4  → restart   best = 4
i=4, x = -1 :  current = max(-1,  4-1) = max(-1,  3) =  3  → extend    best = 4
i=5, x =  2 :  current = max( 2,  3+2) = max( 2,  5) =  5  → extend    best = 5
i=6, x =  1 :  current = max( 1,  5+1) = max( 1,  6) =  6  → extend    best = 6
i=7, x = -5 :  current = max(-5,  6-5) = max(-5,  1) =  1  → extend    best = 6
i=8, x =  4 :  current = max( 4,  1+4) = max( 4,  5) =  5  → extend    best = 6
return 6  ✅

index      0     1     2     3     4     5     6     7     8
value     -2     1    -3     4    -1     2     1    -5     4
end-here  -2     1    -2     4     3     5     6     1     5
best      -2     1     1     4     4     5     6     6     6

Read the end-here row left to right: it only "accepts" the past when the past is not a burden. At index 2 the run is dragging (-2), so index 3 drops it and restarts at 4.

Time O(n) — one pass, O(1) work per element · Space O(1) — two variables. The O(n²) brute force collapses because each ending position compresses all windows ending there into a single number.

• All negative [-3, -1, -7] → -1: the best "window" is the single least-negative element. This is why both current and best start at nums[0] — never 0.
• Single element → that element.
• All positive → the whole array (extending always wins).

• Initializing best = 0 — returns 0 on all-negative input instead of the best single element.
• Swapping the two maxes: current = max(current, best + x) mixes up the two meanings and silently produces wrong answers.
• Allowing an empty window when the problem demands at least one element.

Decide whether a string is a palindrome, considering only alphanumeric characters and ignoring case. Examples: "race a car" → False; "A man, a plan, a canal: Panama" → True.

s = "race a car" → False  ·  s = "Madam" → True

Two independent questions tangled together: which characters count (letters and digits, lowercased) and is the sequence symmetric. Solve the first by cleaning (or by skipping while scanning), then the second with the inward two-pointer sweep.

Clean the string into a new one, then compare it with its reverse (cleaned == cleaned[::-1]). Simple and O(n) time — but it allocates two extra strings of size n.

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

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1                  # skip punctuation on the left
        while left < right and not s[right].isalnum():
            right -= 1                 # skip punctuation on the right
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

indices:      0:'r' 1:'a' 2:'c' 3:'e' 4:' ' 5:'a' 6:' ' 7:'c' 8:'a' 9:'r'
left=0, right=9: 'r' vs 'r' ✅ → left=1, right=8
left=1, right=8: 'a' vs 'a' ✅ → left=2, right=7
left=2, right=7: 'c' vs 'c' ✅ → left=3, right=6
left=3, right=6: s[6]=' ' not alnum → right=5
left=3, right=5: 'e' vs 'a' ❌ → return False

Time O(n) — each pointer only moves forward · Space O(1) for the two-pointer version, O(n) for the clean-and-compare version.

• Empty string "" → True (vacuously a palindrome; the loop never runs).
• Punctuation only ".,!" → True — after skipping there is nothing left to compare.
• Single character → True.
• Mixed case "Madam" → lowercase before comparing, always.

• Forgetting .lower() — "Madam" wrongly fails ('M' vs 'm').
• Advancing past punctuation without re-checking left < right in the skip loops — pointers can cross and compare garbage.
• Using strip() and expecting it to remove interior spaces (it only trims the ends).

Return True if t is an anagram of s — same characters with exactly the same multiplicities, order irrelevant.

s = "listen", t = "silent" → True  ·  s = "rat", t = "car" → False

"Same characters, same counts" is a statement about frequency tables, not about order. Count one string, then walk the other and un-count; any mismatch — a character missing, or a count going below zero — settles it immediately.

For each character of t, search for and remove one matching character from a copy of s. Every removal is an O(n) scan — O(n²) overall.

One frequency dictionary does both jobs: increments for s, decrements for t. The repeated work that disappears: searching for a matching character for every position. One caveat first: if the lengths differ, no counting is needed at all — fail fast.

def is_anagram(s, t):
    if len(s) != len(t):
        return False                 # different sizes can never match

    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1

    for ch in t:
        if counts.get(ch, 0) == 0:   # t needs a character s can't supply
            return False
        counts[ch] -= 1
    return True                      # every count hit exactly zero

after counting s: {l:1, i:1, s:1, t:1, e:1, n:1}
consume 's': 1 → 0
consume 'i': 1 → 0
consume 'l': 1 → 0
consume 'e': 1 → 0
consume 'n': 1 → 0
consume 't': 1 → 0
all counts exactly zero → True ✅

is_anagram("rat", "car"):
counts {r:1, a:1, t:1}; consume 'c': counts.get('c', 0) == 0 → False ✅

Time O(n) — two linear passes · Space O(k) for the counts, where k is the number of distinct characters (at most 26 for lowercase letters, so effectively O(1) for a fixed alphabet).

• Different lengths → False before any counting.
• Empty vs empty → True.
• Repeated letters "aab" vs "aba" → True; "aab" vs "ab" → length check catches it.

• Skipping the length check — it is a free O(1) early exit.
• Counting both strings in separate dictionaries and comparing — also correct, but the one-dictionary increment/decrement version exits early on the first mismatch.
• Forgetting that equality of sets is not enough: "aabb" and "ab" share the same letter set but are not anagrams. Counts, not membership, decide.

Return the index of the first character that appears exactly once in the string; return -1 if there is none.

s = "swiss" → 1 (the 'w')  ·  s = "aabb" → -1

Two questions, two different orders: how often does each character appear (any order works — count in one pass) and which is the first with count 1 (must scan in the original order). This is the classic two-pass pattern: preprocess, then query.

For each character, count its occurrences with s.count(ch) — an O(n) scan per character, O(n²) total. What repeats: recounting the same characters over and over.

def first_unique_char(s):
    counts = {}
    for ch in s:                          # pass 1: count everything
        counts[ch] = counts.get(ch, 0) + 1

    for i, ch in enumerate(s):            # pass 2: first with count 1
        if counts[ch] == 1:
            return i
    return -1

pass 1: counts = {s:3, w:1, i:1}
pass 2:
  i=0, ch='s' → count 3  ❌
  i=1, ch='w' → count 1  ✅ return 1

Time O(n) — two passes · Space O(k) distinct characters, O(1) for a fixed alphabet. The O(n²) brute force collapses because counting happens once, not once per position.

• No unique character ("aabb") → -1.
• Single character "z" → 0.
• The unique characters must be reported by position, not by frequency — that is why pass 2 walks the string, not the dictionary (dicts preserve insertion order in modern Python, but relying on that here makes the logic harder to reason about).

• Returning the character instead of its index.
• Scanning the dictionary in pass 2 — you get "first-inserted", which equals string order only by coincidence of implementation; iterating enumerate(s) is explicit and safe.
• Doing s.count(ch) inside the second loop — quietly O(n²) again.

Reverse the order of the words (not the letters), with single spaces between them. Leading/trailing/multiple spaces collapse to one.

s = "the sky is blue" → "blue is sky the"  ·  s = " hello world " → "world hello"

Words are the atoms here, so first split the string into its word list, then reverse the list, then glue it back. Python's split() with no arguments splits on runs of whitespace and drops the empties — the space normalization comes for free.

Walk the string manually, spotting word boundaries, pushing characters onto stacks of stacks… doable, error-prone, and unnecessary: split already tokenizes correctly.

def reverse_words(s):
    words = s.split()        # ['the', 'sky', 'is', 'blue']
    words.reverse()          # ['blue', 'is', 'sky', 'the']
    return " ".join(words)   # 'blue is sky the'

s.split()      → ['the', 'sky', 'is', 'blue']
words.reverse() → ['blue', 'is', 'sky', 'the']
" ".join(words) → "blue is sky the"  ✅

reverse_words("  hello   world  "):
s.split() → ['hello', 'world']   (extra spaces vanish)
→ "world hello"  ✅

Time O(n) — split, reverse, and join each touch every character once · Space O(n) for the word list (unavoidable: the output string is new anyway, because strings are immutable).

• All spaces " " → "" (split returns an empty list).
• One word → returned unchanged, trimmed.
• Tabs and newlines count as whitespace for split().

• Using s.split(" ") — splitting on a single space keeps empty strings for consecutive spaces: "a b".split(" ") is ['a', '', 'b'], and your output grows phantom gaps.
• Reversing letters of the whole string first and getting confused — reverse the word list, not the characters.
• Building the result with += inside a loop instead of join (see the benchmark above).

Given a list of strings, return the longest string that every string starts with. If there is none, return the empty string.

strs = ["flower", "flow", "flight"] → "fl"  ·  strs = ["dog", "racecar", "car"] → ""

Column by column: the prefix can only contain column c if every string has the same character there. Scan the first string's characters top-to-bottom across all words — the first column disagreement (or the shortest word running out) marks the end of the prefix.

Compare every pair of strings to find their common prefix, then intersect those results — O(n·m²) in the worst case, with lots of repeated comparisons.

def longest_common_prefix(strs):
    if not strs:
        return ""
    for i, ch in enumerate(strs[0]):
        for word in strs[1:]:
            if i >= len(word) or word[i] != ch:
                return strs[0][:i]   # everything before column i matched
    return strs[0]                   # the first word IS the prefix

column 0: 'f' — "flow" has 'f' ✅, "flight" has 'f' ✅
column 1: 'l' — "flow" has 'l' ✅, "flight" has 'l' ✅
column 2: 'o' — "flow"  has 'o' ✅, "flight" has 'i' ❌
          → return strs[0][:2] = "fl" ✅

longest_common_prefix(["dog", "racecar", "car"]):
column 0: 'd' — "racecar" has 'r' ❌ → return strs[0][:0] = "" ✅

Time O(n·m) — n strings, up to m columns checked (worst case: all strings identical) · Space O(1) beyond the returned slice.

• Empty list → "".
• One string → itself (the loop over the other words never runs).
• A word shorter than the prefix candidate, e.g. ["flower", "flow"] — the i >= len(word) guard returns "flow" exactly when the short word runs out.
• Empty string in the list, ["", "b"] → the outer loop body never executes (strs[0] is empty) → "".

• Indexing word[i] without the length guard — IndexError on the shortest word.
• Returning strs[0][:i] at the right place but forgetting the final return strs[0] when every column matches.
• Sorting-based tricks (compare only first and last after sorting) — clever but harder to justify; the vertical scan is the version to master first.

Given a list of integers, return True if any value appears at least twice, otherwise False.

[1, 2, 3, 1] → True · [1, 2, 3, 4] → False

For each element the question is pure membership: "have I seen this value before?". That is precisely the one job a set does in O(1) average — no counts needed, so no dictionary needed.

Compare every pair with nested loops — O(n²). At n = 100,000 that is the ~5 billion comparisons we counted above. The repeated work: re-checking all previous elements by hand.

Walk the list once, carrying a seen set. Each element asks the set one question. First repeat → True. Never a repeat → False.

def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:          # ask BEFORE adding
            return True
        seen.add(x)
    return False

x = 1  → 1 in seen? seen = {}        → no   → seen = {1}
x = 2  → 2 in seen? seen = {1}       → no   → seen = {1, 2}
x = 3  → 3 in seen? seen = {1, 2}    → no   → seen = {1, 2, 3}
x = 1  → 1 in seen? seen = {1,2,3}   → YES ✅  return True

Time O(n) average · Space O(n) for the set.

• Empty list or single element → False (no pair can exist).
• All elements equal, e.g. [7, 7, 7] → True on the second element.

• Using a list as seen — membership in a list is O(n), so the "fix" is still O(n²).
• Adding to the set before checking: then [1] would wrongly return True because the element meets itself.

Given a list of integers and a target, return the indices of the two numbers that add up to the target. Exactly one solution exists; the same element may not be used twice.

nums = [2, 7, 11, 15], target = 9 → [0, 1] (2 + 7)

Standing on value x, the partner you need is fixed: need = target − x. So the vague question "is there a pair?" becomes a precise lookup: "have I already seen need?" — a job for Complement Lookup with a value → index dictionary (Pattern 3 + Pattern 4 combined).

Try every pair — O(n²). For each element you re-search the whole rest of the list; that repeated search is what the dictionary removes.

One pass. Before storing x, ask the dictionary for target − x. Found → return both indices. Not found → remember x → i and move on.

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

def two_sum(nums, target):
    seen = {}                     # value -> index where we saw it
    for i, x in enumerate(nums):
        need = target - x         # the partner that completes the pair
        if need in seen:
            return [seen[need], i]
        seen[x] = i               # remember this value's position
    return []

i = 0  x = 2   need = 9 - 2 = 7    seen = {}          → 7 not in seen → store {2: 0}
i = 1  x = 7   need = 9 - 7 = 2    seen = {2: 0}      → 2 IS in seen ✅
                                      return [seen[2], 1] = [0, 1]

Time O(n) average · Space O(n) for the dictionary.

• Duplicated values like [3, 3] with target 6: at i = 1, need = 3 is already in seen from i = 0 → returns [0, 1] correctly.
• The answer may use values far apart — the dictionary does not care about distance.

• Storing x before checking need: with nums = [2] and target 4 you would pair the element with itself and return [0, 0]. Check first, store second.
• Returning values instead of the indices the problem asked for.
• Scanning nums again for need with nums.index(need) — that is a hidden O(n) search and breaks the whole point.

Given two strings s and t, return True if t is an anagram of s (same letters, same counts, any order).

s = "anagram", t = "nagaram" → True · s = "rat", t = "car" → False

Order is irrelevant; only the counts of each letter matter. Count one string, subtract the other — a textbook Frequency Map.

sorted(s) == sorted(t) — correct, but O(n log n): it does ordering work the question never asked for.

Count every letter of s into a dictionary. Then walk t, decreasing counts. If a letter is missing or its count is already 0 → False. If every letter subtracts cleanly → True.

def is_anagram(s, t):
    if len(s) != len(t):          # different lengths can never match
        return False
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    for ch in t:
        if counts.get(ch, 0) == 0:   # letter missing or used up
            return False
        counts[ch] -= 1
    return True

count s: {'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1}

subtract t: 'n' → 0   'a' → 2   'g' → 0   'a' → 1   'r' → 0   'a' → 0   'm' → 0
no letter was missing or exhausted → return True ✅

s = "rat", t = "car":  counts = {'r': 1, 'a': 1, 't': 1}
subtract 'c' → counts.get('c', 0) == 0 → return False ✅

Time O(n) · Space O(1) — at most 26 letter keys, whatever the input size.

• Different lengths → early False without touching the counts.
• Empty strings are anagrams of each other → True.

• Subtracting without the get(ch, 0) == 0 guard — counts can go negative and "cancel" wrongly (e.g. "aab" vs "b" would survive a naive subtract-and-check-all-zero).
• Comparing only the set of letters: set("aabb") == set("ab") is True but the strings are not anagrams — counts matter, not membership.

Given a string, return the index of the first character that appears exactly once in the whole string. If there is none, return -1.

s = "swiss" → 1 (the 'w') · s = "aabb" → -1

Two questions hiding in one problem: how often does each letter appear? (needs the whole string → frequency map) and which is the first letter with count 1? (needs the original order → second scan). One pass cannot know a letter is unique until it has seen the whole string.

Pass 1 builds the frequency map. Pass 2 walks the string in order and returns the index of the first character whose count is exactly 1.

def first_unique_char(s):
    counts = {}
    for ch in s:                       # pass 1: count everything
        counts[ch] = counts.get(ch, 0) + 1
    for i, ch in enumerate(s):         # pass 2: keep original order
        if counts[ch] == 1:
            return i
    return -1

pass 1: {'s': 3, 'w': 1, 'i': 1}

pass 2: i = 0  's'  count 3 → skip
        i = 1  'w'  count 1 ✅  return 1

Time O(n) — two passes, still linear · Space O(1) — at most 26 keys for lowercase letters.

• Every letter repeats → the second pass finds nothing → -1.
• Single-character string → that character is unique → index 0.

• Trying to answer in one pass with only a set of "repeated" letters — you lose the counts and the first-unique logic breaks on strings like "aab".
• Returning the character instead of the index.

Given a list where a majority element is guaranteed to exist (it appears more than n/2 times), return that element.

[2, 2, 1, 1, 1, 2, 2] → 2 (appears 4 times, n = 7)

"Appears more than n/2 times" is a counting question. Count everything, then report the value whose count beats len(nums) // 2.

For each element, count its occurrences with an inner loop — O(n²). The inner counting scan is exactly what the frequency map removes.

One pass with a frequency map (or equivalently collections.Counter), then one pass over the map to find the winner.

def majority_element(nums):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
    for value, c in counts.items():
        if c > len(nums) // 2:
            return value
    return -1        # no majority (problem says this won't happen)

counts after each x: {2:1} {2:2} {2:2,1:1} {2:2,1:2} {2:2,1:3} {2:3,1:3} {2:4,1:3}

n = 7 → majority needs more than 3 occurrences
'2' has count 4 > 3 ✅  return 2

Time O(n) · Space O(n) for the map. (A clever O(1)-space vote-counting trick exists — Boyer–Moore — but for a guaranteed majority, counting is the clear beginner answer.)

• Even-length lists: a majority needs strictly more than n/2, e.g. 3 of 4 is not enough — that is why the check is c > len(nums) // 2 and not >=.

• Using >= instead of >: on [1, 1, 2, 2] (no majority exists) it would confidently "return" 1.
• Sorting first and returning the middle element — it works here, but it hides the counting idea you were meant to practice.

Given a sorted (ascending) array and a target, return the indices of the two numbers that add up to the target, or [] if no pair exists.

arr = [1, 2, 4, 7, 11, 15], target = 18 → [3, 4]

A sum that is too small can only be repaired by a bigger first number (move L), a sum that is too big only by a smaller second number (move R). Sortedness turns "which pair next?" into "which end to discard?".

All pairs — O(n²). It re-checks pairs that the sorted order had already ruled out.

Pointers at both ends; each comparison deletes one element from the search space. At most n−1 comparisons.

def pair_sum_brute(arr, target):
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] + arr[j] == target:
                return [i, j]
    return []

def pair_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current = arr[left] + arr[right]
        if current == target:
            return [left, right]
        elif current < target:
            left += 1        # need a bigger sum -> drop the small end
        else:
            right -= 1       # need a smaller sum -> drop the big end
    return []

L = 0, R = 5:  1 + 15 = 16 < 18 → move L →
L = 1, R = 5:  2 + 15 = 17 < 18 → move L →
L = 2, R = 5:  4 + 15 = 19 > 18 → move R ←
L = 2, R = 4:  4 + 11 = 15 < 18 → move L →
L = 3, R = 4:  7 + 11 = 18 ✅  return [3, 4]

Time O(n) — each step removes one element · Space O(1).

• No pair exists → pointers meet → return [].
• Duplicates: [2, 2, 3], target 4 → 2+3=5 too big → R--, then 2+2=4 → [0, 1].
• Two-element array is the smallest valid input; the loop runs exactly once.

• Loop condition left <= right — an element would be paired with itself.
• Moving both pointers after one comparison: you discard two candidates but only proved one discard — you can skip the answer.
• Forgetting the sorted-array requirement (see the [3, 2, 4] failure above).

Given a sorted array, remove the duplicates in place so each value appears once. Return the count k of unique values; the first k slots must hold the result. Order stays.

[1, 1, 2, 2, 3] → returns 3, array begins [1, 2, 3, _, _]

Sorted ⇒ duplicates sit next to each other. An element is "new" exactly when it differs from the last kept value, arr[write - 1]. So read judges, write files.

Build a new list of uniques, then copy it back — O(n) time but O(n) extra space, and it sidesteps the in-place skill this problem exists to teach.

Read/write pointers. The first element is always kept (write = 1). Every read element that differs from the last kept one gets written forward.

def remove_duplicates(arr):
    if not arr:
        return 0
    write = 1                          # slot for the next new unique value
    for read in range(1, len(arr)):
        if arr[read] != arr[write - 1]:   # different from last KEPT value
            arr[write] = arr[read]
            write += 1
    return write

start:  write = 1                     kept prefix: [1]

read=1: arr[1]=1 == arr[write-1]=1 → duplicate, skip
read=2: arr[2]=2 != arr[0]=1  → arr[1]=2, write=2   [1, 2, _, _, _]
read=3: arr[3]=2 == arr[write-1]=2 → duplicate, skip
read=4: arr[4]=3 != arr[1]=2  → arr[2]=3, write=3   [1, 2, 3, _, _]

return 3 — first 3 slots are [1, 2, 3] ✅

Time O(n) · Space O(1) — truly in place.

• Empty array → return 0 (the early guard exists only so write = 1 is safe).
• All identical, e.g. [5, 5, 5] → read never writes → return 1.
• All unique → every read writes → return len(arr), array unchanged.

• Writing to arr[read] instead of arr[write] — the compaction becomes a no-op and duplicates stay exactly where they were.
• Returning write + 1 — write already points at the next free slot, so the count is write.
• Forgetting the array may keep stale values after index k; the contract only guarantees the first k slots.

Move all zeroes in an array to the end in place, keeping the relative order of the non-zero elements.

[0, 1, 0, 3, 12] → [1, 3, 12, 0, 0]

Same invariant as 6.2, different filter: an element is "kept" exactly when it is non-zero. Swapping (rather than overwriting) automatically parks the zeroes behind write — no second pass to fill zeroes.

Read scans all; each non-zero element swaps into the write slot; write advances. Zeroes drift rightward as a side effect.

def move_zeroes(nums):
    write = 0                        # next slot for a non-zero
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1

read=0: 0 → skip                          [0, 1, 0, 3, 12]  write=0
read=1: 1 ≠ 0 → swap nums[0], nums[1]     [1, 0, 0, 3, 12]  write=1
read=2: 0 → skip
read=3: 3 ≠ 0 → swap nums[1], nums[3]     [1, 3, 0, 0, 12]  write=2
read=4: 12 ≠ 0 → swap nums[2], nums[4]    [1, 3, 12, 0, 0]  write=3

done — zeroes sit at the end, non-zeros kept their order ✅

Time O(n) · Space O(1).

• All zeroes → no swaps, array unchanged (which is the answer).
• No zeroes → every element swaps with itself — harmless.

• Using the overwrite version (copy non-zeros forward) and forgetting to zero out the tail.
• Adding a tail-zeroing pass after the swap version — the zeroes are already there, and the extra pass scrambles them.
• Advancing write when the element is zero — that breaks the invariant instantly.

Each element of heights is a vertical line of that height at position i. Pick two lines so that together with the x-axis they hold the most water. Return that maximum area.

[1, 5, 4, 3] → 6 (lines of 5 and 3, width 2)

Area = min of the two heights × width. The shorter wall is the bottleneck; width only shrinks as pointers move inward. So the only move that can ever improve things is replacing the shorter wall.

Every pair of lines, compute the area, keep the max — O(n²). Fine for 4 lines, fatal for 100,000.

Pointers at the ends. Measure, record, then move the shorter side inward. Repeat until they meet.

def max_area(heights):
    left, right = 0, len(heights) - 1
    best = 0
    while left < right:
        width = right - left
        area = min(heights[left], heights[right]) * width
        best = max(best, area)
        if heights[left] < heights[right]:
            left += 1            # shorter wall is on the left
        else:
            right -= 1           # shorter wall on the right (or a tie)
    return best

L=0, R=3: min(1, 3) × 3 = 3   best = 3   h[L] < h[R] → move L →
L=1, R=3: min(5, 3) × 2 = 6   best = 6   h[L] ≥ h[R] → move R ←
L=1, R=2: min(5, 4) × 1 = 4   best = 6   h[L] ≥ h[R] → move R ←
pointers meet → return 6 ✅  (matches checking all 6 pairs)

Time O(n) · Space O(1).

• Ties (h[L] == h[R]): move either — the else branch moving R is fine; the tie wall could not raise the limit either way.
• Strictly increasing heights like [1, 2, 3, 4]: pointer walks L forward each step; brute force agrees the best is (1, 3) with area min(2, 4) × 2 = 4.

• Moving the taller side — it feels active and helpful, and it is exactly the move that can lose the answer.
• Using width = right - left + 1 — water spans between the lines; two adjacent lines hold width 1, not 2.
• Using max(h[L], h[R]) as the height — water above the shorter wall spills.

Given an array and an integer k, return the maximum sum of any k contiguous elements.

[2, 1, 5, 1, 3, 2], k = 3 → 9 (the window [5, 1, 3])

Sum each of the n−k+1 windows from scratch — O(n·k). The repeated work is re-adding the k−2 elements two neighboring windows share.

Compute the first window once; slide with one addition and one subtraction per step.

def max_sum_naive(arr, k):
    best = 0
    for left in range(len(arr) - k + 1):
        best = max(best, sum(arr[left:left + k]))
    return best

def max_sum_k(arr, k):
    window = sum(arr[:k])            # first window, computed once
    best = window
    for right in range(k, len(arr)):
        window += arr[right] - arr[right - k]
        best = max(best, window)
    return best

first window [2, 1, 5]     window = 8                best = 8
right = 3:  8 + 1 - 2 = 7                            best = 8
right = 4:  7 + 3 - 1 = 9 ⭐                         best = 9
right = 5:  9 + 2 - 5 = 6                            best = 9
answer: 9

Time O(n) · Space O(1).

• k = len(arr) → the single window is the whole array; the loop body never runs.
• k larger than n → no valid window; guard with an early check in real code.
• All-negative arrays work fine — the window sum tracks negatives correctly.

• Starting the loop at right = 0 and subtracting arr[right - k] at negative indices — the first window must be built before the loop.
• Updating best before the first window is complete.

Given a string, return the length of the longest substring (contiguous!) in which no character appears more than once.

s = "abcabcbb" → 3 (the substring "abc") · s = "bbbbb" → 1

The window invariant: all characters in s[left..right] are distinct. When the new s[right] is already in the window, left advances (dropping characters) until that duplicate is gone — then the invariant holds again and the length is measured.

Every start index i, extend j until a repeat appears, track the max — O(n²) pairs with a set check each step. It re-checks characters the previous window already knew about.

Expand right every iteration; shrink left only while the newest character is a duplicate inside the window; record the length when valid.

def longest_unique_substring(s):
    in_window = set()      # characters currently inside the window
    left = 0
    best = 0
    for right in range(len(s)):
        while s[right] in in_window:    # duplicate → shrink until gone
            in_window.remove(s[left])
            left += 1
        in_window.add(s[right])         # now safe to admit it
        best = max(best, right - left + 1)
    return best

r=0 'a': not in window → add          window "a"    left=0  best=1
r=1 'b': not in window → add          window "ab"           best=2
r=2 'c': not in window → add          window "abc"          best=3
r=3 'a': IN window → remove s[0]='a', left=1
         'a' no longer in window → add  window "bca"        best=3
r=4 'b': IN window → remove s[1]='b', left=2 → add
                                      window "cab"          best=3
r=5 'c': IN window → remove s[2]='c', left=3 → add
                                      window "abc"          best=3
r=6 'b': IN window → remove s[3]='a', left=4; 'b' still in
         → remove s[4]='b', left=5 → add    window "cb"         best=3
r=7 'b': IN window → remove s[5]='c', left=6; 'b' still in
         → remove s[6]='b', left=7 → add    window "b"          best=3
answer: 3

The same run, watched as a window on a b c a b c b b:

Time O(n) — right moves n times, left moves at most n times in total · Space O(min(n, alphabet size)) for the set.

• Empty string → loop never runs → 0.
• All identical characters, "bbbb" → left always shrinks to right → 1.
• The while-loop can shrink several steps per character — that is expected, and still O(n) overall.

• Using an if instead of while for the shrink: one removal may not clear the duplicate (see r = 6 above — two removals were needed).
• Removing s[right] instead of s[left] while shrinking.
• Measuring the length as right - left and losing one element — inclusive ends need the + 1.
• Answering with the longest subsequence mindset — repeats may be far apart in a subsequence, but a window cannot skip characters.

Given an array of positive numbers and a target k, return the length of the shortest contiguous subarray whose sum is at least k. If none exists, return 0.

[2, 3, 1, 2, 4, 3], k = 7 → 2 (the window [4, 3])

This window answers a minimization, so the recording happens differently: while the window is still valid (sum ≥ k), we record its length and then shrink — every shorter valid window ends at this same right edge, and shrinking finds them all before expanding again.

Every start index, extend until the sum reaches k, record the length — O(n²). It re-sums overlapping stretches over and over.

Expand right always; while sum ≥ k, record the current length and shrink from the left; expand again.

def smallest_subarray_at_least(arr, k):
    left = 0
    cur = 0                       # current window sum
    best = None                   # no valid window seen yet
    for right in range(len(arr)):
        cur += arr[right]         # expand: pull arr[right] in
        while cur >= k:           # valid → record, then shrink
            length = right - left + 1
            if best is None or length < best:
                best = length
            cur -= arr[left]      # drop the left element
            left += 1
    if best is None:
        return 0
    return best

r=0: cur = 2        (2 < 7, keep expanding)
r=1: cur = 5
r=2: cur = 6
r=3: cur = 8  ≥ 7 → record len 4  → shrink: cur = 8-2 = 6,  left=1  (6 < 7 stop)
r=4: cur = 10 ≥ 7 → record len 4 (no change)
                   → shrink: cur = 10-3 = 7, left=2 → 7 ≥ 7 → record len 3 ⭐
                   → shrink: cur = 7-1  = 6, left=3  (stop)
r=5: cur = 9  ≥ 7 → record len 3 (no change)
                   → shrink: cur = 9-2  = 7, left=4 → 7 ≥ 7 → record len 2 ⭐⭐
                   → shrink: cur = 7-4  = 3, left=5  (stop)
answer: 2  — the window [4, 3]

The same run, watched as a window — expand, shrink, expand, shrink:

Time O(n) — right moves n times; left moves forward only, so at most n times in total · Space O(1).

• No window ever reaches k → best stays None → return 0.
• Single element ≥ k → answer 1, found at the first expand.
• Whole array needed → the last recorded window is arr[0..n-1].

• Recording once per right and then shrinking without re-recording — the shorter windows [1, 2, 4] and [4, 3] are discovered while shrinking; the record must live inside the while loop.
• Shrinking before expanding, or shrinking past validity — the while condition cur >= k is the only shrink trigger.
• Using this template when the array contains negatives (see the warning above).

Design a structure built from an array that answers many queries: "sum of nums[left..right]" — each answered instantly. The array may contain negative numbers.

nums = [-2, 0, 3, -5, 2, -1] → sum_range(0, 2) = 1, sum_range(2, 5) = -1

Sum the slice on every query — O(right − left) each. Overlapping queries re-add the same elements again and again; that repeated summation is what disappears.

Build the prefix array once in O(n); every query becomes one subtraction.

class RangeSumNaive:
    def __init__(self, nums):
        self.nums = nums

    def sum_range(self, left, right):
        total = 0
        for i in range(left, right + 1):   # re-adds the overlap every time
            total += self.nums[i]
        return total

class RangeSum:
    def __init__(self, nums):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

    def sum_range(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

prefix = [0, -2, -2, 1, -4, -2, -3]

sum_range(0, 2) = prefix[3] - prefix[0] = 1 - 0     = 1
                  check: -2 + 0 + 3 = 1 ✅
sum_range(2, 5) = prefix[6] - prefix[2] = -3 - (-2) = -1
                  check: 3 + (-5) + 2 + (-1) = -1 ✅

negatives are no problem — prefix sums are just arithmetic

Build O(n) time, O(n) space · each query O(1). With Q queries: O(n + Q) total instead of O(n · Q).

• Single-element range: sum_range(3, 3) = prefix[4] − prefix[3] — exactly nums[3].
• Full-range query: sum_range(0, n-1) = prefix[n].
• Negative values: subtraction handles them naturally, as the dry run shows.

• Using prefix[r] − prefix[l] — drops the last element of the range.
• Forgetting the leading 0 in the prefix array — then ranges starting at index 0 need a special case.
• Rebuilding the prefix after each query — the build is one-time by design.

Given an array, return the running sum: element i of the output is the total of nums[0..i].

[1, 2, 3, 4] → [1, 3, 6, 10]

A running sum is the prefix sum, shifted by one: running[i] = prefix[i + 1]. Where 8.1 stored prefixes to answer queries, this problem simply outputs them.

For each i, sum nums[0..i] from scratch — O(n²). Element 0 gets re-added n times; the repeated work is re-summing the head of the array.

Carry one accumulator; each output is the accumulator after adding the current element.

def running_sum(nums):
    result = []
    total = 0
    for x in nums:
        total += x
        result.append(total)
    return result

print(running_sum([1, 2, 3, 4]))    # [1, 3, 6, 10]

x = 1 → total = 1  → result [1]
x = 2 → total = 3  → result [1, 3]
x = 3 → total = 6  → result [1, 3, 6]
x = 4 → total = 10 → result [1, 3, 6, 10]

Time O(n) · Space O(n) for the output (O(1) beyond it).

• Empty array → empty output.
• Negatives: [2, -1, 3] → [2, 1, 4] — nothing special is needed.

• Appending nums[i] instead of the accumulator.
• Recomputing sum(nums[:i+1]) inside the loop — the O(n²) trap this problem targets.

Find the index where the sum of all elements strictly left equals the sum of all elements strictly right. Return the leftmost such index, or −1.

[1, 7, 3, 6, 5, 6] → 3 (left 1+7+3 = 11, right 5+6 = 11)

You never need two running sums. Keep the total and a running left sum; then right = total − left − nums[i]. One equation replaces re-summing both sides — the pivot condition becomes a simple comparison.

For each index, sum the left side and sum the right side — O(n²). Every index re-adds almost the entire array twice.

One pass with total and left. At each i: compute right by subtraction, compare, then absorb nums[i] into left.

def pivot_index(nums):
    total = sum(nums)
    left = 0
    for i, x in enumerate(nums):
        right = total - left - x     # everything except left side and x
        if left == right:
            return i
        left += x                    # x joins the left side for the next index
    return -1

i=0  x=1: right = 28 - 0  - 1 = 27   left = 0   → no    left → 1
i=1  x=7: right = 28 - 1  - 7 = 20   left = 1   → no    left → 8
i=2  x=3: right = 28 - 8  - 3 = 17   left = 8   → no    left → 11
i=3  x=6: right = 28 - 11 - 6 = 11   left = 11  → 11 == 11 ✅  return 3

Time O(n) · Space O(1) — no prefix array even needed, just two numbers.

• Pivot at index 0: left side is empty (0). [2, 1, -1] → i=0: right = 2−0−2 = 0 = left → returns 0.
• Pivot at the last index: right side is empty (0) — the loop naturally allows it.
• Single element [1] → 0 (both sides empty).

• Starting the loop with left = nums[0] — at i = 0 the left side must be empty.
• Forgetting to subtract nums[i] itself when computing the right side.
• Updating left before the comparison — the pivot element belongs to neither side.