Foundation: Arrays & Strings

A fast solution is a slow solution that stopped repeating itself

Suppose you are given 100,000 numbers and asked whether any two of them are equal. The obvious plan compares every pair: n(n−1)/2 checks. For n = 100 that is 4,950 checks. For n = 100,000 it is 4,999,950,000, close to five billion. A typical judge gives you a second or two.

The fix is not a cleverer comparison. It is noticing that the slow version keeps asking a question it has already answered: "have I seen this value before?" Remember the answer instead of recomputing it, and five billion checks become 100,000.

That is the whole lesson in one sentence. Almost every array and string optimization you will meet on LeetCode is one of a handful of ways to stop repeating work. This lesson teaches six of them. Each one starts with a smell: something in the slow code that tells you which move to reach for.

This lesson assumes you can write Python loops and functions. Deeper two-pointer, sliding-window and hashing families have their own lessons later in this roadmap. Here you learn the reasoning those patterns are built from.

Before any move: read the contract

Two solutions can print the same values and still get different verdicts. One changes the caller's array and the other builds a new one. One returns original positions, the other returns positions after sorting. So before choosing a trick, decide exactly what the judge will observe. This is the problem's output contract: what your function must change and what it must return.

LeetCode 27: Remove Element is a good example. Given nums = [3, 2, 2, 3], remove every 3. The contract says to put the kept values at the front of the same list and return how many there are. It does not say to shorten the list or clear anything.

Return 2. The judge reads only the first two cells, so the stale 2 and 3 at the end are fine. The list still has four cells; two of them are meaningful. That gap between buffer length and valid length returns several times in this lesson. Returning a brand-new list [2, 2] has the right values in the wrong form, and it fails.

Four questions to ask before writing the first loop:

Order is information. If stock prices are [8, 2, 5], sorting them to [2, 5, 8] invents a profitable future that never happened. If a problem asks for original indices, sorting bare values loses those positions unless you carry them along. Sorting is a tool with preconditions, not a harmless cleanup step.

Contiguous is not the same as in order. In [4, 1, 7, 2], [1, 7] is a subarray, because its elements sit next to each other. [4, 7] is only a subsequence, because it skips the 1 while keeping order. A substring is contiguous, like a subarray. "Any pair" allows a gap; "adjacent pair" does not. Underline that word in the statement before you pick a method.

What costs what. In the usual array model, indexing is O(1), a full scan is O(n), and inserting or deleting near the front shifts many entries. Python lists follow this model. A slice such as nums[1:] builds a new list, so it costs time and memory proportional to its length. Appending is amortized O(1): occasional resizes are spread across many appends. Complexity claims in this lesson use the usual model where one integer operation costs O(1).

💡 Habit worth building: write the slow version first, then circle the work it repeats. The smell tells you the move.

Move 1: Carry a running summary

Smell: for each position, the slow code loops back over everything before it.

The hindsight trader

You get daily prices [7, 1, 5, 3, 6, 4]. Buy on one day, sell on a later day, and maximize profit. If no trade makes money, you may skip trading and take profit 0. This is LeetCode 121: Best Time to Buy and Sell Stock. Traces use zero-based indices.

Predict first: on [8, 2, 5, 1, 4], is the best profit 7, because the minimum is 1 and the maximum is 8?

The slow method tries every buy/sell pair with buy < sell, which is O(n²). Look at what it repeats. For each selling day it asks the same question: what was the cheapest price before today? Then it answers that question from scratch by rescanning the past.

The answer to that question changes by at most one comparison per day. So carry it forward in one variable:

def max_profit(prices):
    if len(prices) < 2:
        return 0
    cheapest = prices[0]
    best = 0
    for day in range(1, len(prices)):
        price = prices[day]
        best = max(best, price - cheapest)   # today as a selling day
        cheapest = min(cheapest, price)      # today as a future buying day
    return best

The order of those two lines matters. The loop treats today as a selling day before it lets today become a buying price. Swap them and you could "buy and sell" on the same day. With these rules that only adds a harmless zero-profit trade, but in variants that forbid a zero-gain trade, such as returning −1 when no later price is higher, the wrong order becomes a bug.

At index 1 the candidate profit is negative, and best = 0 keeps "no trade" as an option. By index 4, buying at 1 gives 5. The result is one pass, O(n) time and O(1) extra space.

Why one number is enough

Fix a selling price p. Among all earlier buying prices b, the largest p − b comes from the smallest b. Every other earlier price is irrelevant to this decision. A sentence like that, true at a specific moment, is a loop invariant: before checking a day, cheapest is the minimum of all earlier days. Each update makes the sentence true again for the next day.

🧠 The notebook model. Before each step, ask: what question will the next step ask about the past? Write down only what answers it. This notebook needs one minimum and one best result, not the whole price history.

The notebook follows the contract. If the problem asked for the actual buy and sell days, the minimum value alone would no longer be enough. You would also record where the minimum occurred, and save the pair of days whenever best improves.

Same move, different notebook

Now find the longest run of consecutive 1s in a binary array. A total count of 1s does not help: on [1, 1, 0, 1, 1, 1] the total is 5 but the longest run is 3. Here the next step asks about the current streak, not the cheapest past value.

Your turn: write it in one pass with O(1) extra space. Predict the results for [], [0, 0], [1, 1] and [1, 0, 1, 1]. Which line stops the count from continuing across a zero?

def longest_ones(nums):
    current = 0
    best = 0
    for x in nums:
        if x == 1:
            current += 1
        else:
            current = 0          # a zero breaks the streak
        best = max(best, current)
    return best

Try to break your invariant. Test the edge cases on purpose instead of hoping random inputs find the bug. Prices that only fall should give 0. Two equal prices should give 0. A new minimum on the very last day comes too late for any sale.

Move 2: Remember identities, then counts

Smell: the slow code searches the past for a specific value.

A single number worked for the stock problem, but it cannot answer "have I seen this value before?" Different histories can share the same minimum, maximum and total while containing different values. The notebook has to store membership.

A set: "have I met you before?"

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

Invariant: before each check, seen holds exactly the earlier values. The order inside the loop matters. Check first, then add. If you add first, every value looks like a duplicate of itself.

Set lookups and inserts are O(1) on average, so the whole scan takes expected O(n) time and O(n) space. Inputs built to force hash collisions can make it slower. Compare that with the alternatives:

None of these wins everywhere. The contract and the limits decide.

Predict: what is in seen just before the function returns on [5, 2, 7, 2]? Why would remembering only the previous value fail?

From "who" to "how many": the count vector

A set cannot tell aab from abb, because both contain just {a, b}. When repetitions matter, store counts. And when the possible characters form a small fixed alphabet, a plain array works as the table.

For lowercase English letters, define a 26-slot count vector in which slot i counts the letter chr(ord('a') + i). So C[0] counts 'a' and C[25] counts 'z'. Two strings are anagrams exactly when their count vectors are equal. The vector is an exact signature of the letters: it forgets their order and nothing else.

Every other slot is 0 in both, so they are anagrams. Now subtract the vectors of "rat" and "car":

a:  1 - 1 =  0
r:  1 - 1 =  0
t:  1 - 0 = +1     <- rat has a 't', car does not
c:  0 - 1 = -1     <- car has a 'c', rat does not
every other letter: 0

The difference does more than say "no". It points at the exact letters that disagree.

One array, plus and minus

You don't need two vectors. Add 1 for each letter of s, subtract 1 for each letter of t, and check that everything lands back on zero:

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    counts = [0] * 26              # slot i <-> chr(ord('a') + i)
    for ch in s:
        counts[ord(ch) - ord('a')] += 1
    for ch in t:
        counts[ord(ch) - ord('a')] -= 1
    return all(c == 0 for c in counts)

Slot i ends as (count in s) − (count in t). Equal lengths alone are not enough, because a +1 and a −1 can cancel in the total. Once the lengths match, you can also stop early: the first time a decrement goes negative, t has used more of a letter than s supplied.

Trace s = "aab", t = "abb" with that early exit:

Cost. One pass per string gives O(n) time. The table has 26 slots no matter how long the strings are, which gives O(1) extra space. Sorting both strings instead takes O(n log n) time and builds sorted copies.

⚠️ "O(1) space" holds only because the alphabet is fixed at 26 letters. For arbitrary Unicode, use a dictionary of the characters you actually meet. Its size is O(min(n, alphabet size)).

Plot twist: sometimes counts are too much information

Can the letters of a string be rearranged into a palindrome? Picture one: the left half mirrors the right half, so every letter must pair up, except possibly one letter sitting alone in the middle.

A string can be rearranged into a palindrome iff at most one character has an odd count.

You don't need exact counts here, only whether each count is even or odd (its parity). So flip a bit per letter:

def can_permute_palindrome(s: str) -> bool:
    parity = [0] * 26
    for ch in s:
        parity[ord(ch) - ord('a')] ^= 1   # 0 = even so far, 1 = odd
    return sum(parity) <= 1               # how many letters are odd

That is Move 1's notebook lesson again: store only what the final question needs.

Know the alphabet you are indexing

⚠️ Case matters. These functions assume lowercase a–z. ord('L') - ord('a') is −21. Python accepts that as a negative index and silently updates slot 5 ('f'), which gives a wrong answer with no error. Anything below −26, or above 25, raises an IndexError. Decide the case policy, normalize if the problem allows it, and filter out other characters.

⚠️ Other alphabets. For full ASCII, index by ord(ch) directly into 128 slots; don't keep subtracting ord('a'). For general Unicode, a dictionary is usually simpler.

Your turn — adapt. Is "Tact Coa" a permutation of a palindrome? Spaces and case don't count.

Looking ahead: a count vector turned into a tuple makes a great dictionary key for grouping anagrams. The Hash Maps & Sets branch builds on that.

Move 3: Write behind the reader

Smell: the slow code deletes from the middle of an array, so every deletion shifts the tail left.

Back to Remove Element. Calling nums.remove(val) in a loop searches and shifts the tail each time, which is O(n²) in the worst case. Deleting while you walk forward with an index also skips the element that just slid into the current slot. But the contract never asked us to close the gaps. It only asked for a correct front region.

Two fingers, two jobs

A pointer here is just an integer index. The read/write two-pointer technique gives two indices different jobs:

• read visits every value, left to right, one step per iteration.
• write marks where the next kept value goes. It moves only when we keep something.

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

Trace [3, 2, 2, 3, 4] with val = 3:

Return 3. The full buffer is now [2, 2, 4, 3, 4], and only the first three cells count.

Think in regions, not pointer numbers

Before each iteration:
[ kept values | consumed, reusable | current + unread values ]
                ^ write              ^ read

• The kept region is the answer so far.
• The consumed region holds values already inspected, so it is free workspace.
• The unread region is protected, and nothing may overwrite it.

Why no value is ever lost. Before each iteration, write <= read. A write lands either in the consumed region or on read itself. Writing to read is a harmless self-assignment, because the right-hand side is evaluated before it is stored. No write ever reaches past read. Each value is examined once and kept values are written in their original order, so the result is also stable: relative order is preserved. That is O(n) time and O(1) extra space.

Is this swapping? No. nums[write] = nums[read] copies. The value it overwrites is either a discarded value or one that was already copied forward, so nothing needs to be saved. "Two pointers" describes the positions you track; it doesn't require swaps. Move 4 is where swapping becomes necessary.

Your turn: remove every 1 from [1, 4, 1, 5]. After the first three values, what is write, and where does the final 5 go? Then pick the result that meets the contract:

• A. Return 2; the same list is now [4, 5, 1, 5].
• B. Return a new list [4, 5] and leave the original unchanged.
• C. Return 4, because the list still has four cells.

Edge cases: predict the return value for an empty list, a list containing only val, and a list with no val at all.

A Python trap: rebinding is not mutating

Inside a function, nums = kept only changes what the local name points to, and the caller's list is untouched. nums[:] = kept does replace the caller's contents, but building kept already used O(n) extra space. "The caller sees the change" and "the algorithm uses O(1) space" are two separate claims, and you must meet both.

If order doesn't matter there is another option. Overwrite an unwanted element with the last active element and shrink the active range. Re-check the swapped-in value before moving on: in [2, 3, 2] removing 2, the first replacement is another 2. This can save writes when removals are rare, but it scrambles order.

Move 4: Swap and reverse in place

Smell: the only way you can see to rearrange the array is to build a second one.

Filtering throws values away, so overwriting was safe. A rearrangement has to keep every value. The tool for that is the swap, which reads both values before writing either.

Here is the task. Rotate an array right by k using O(1) extra space. The one-liner nums[:] = nums[-k:] + nums[:-k] is correct once k is normalized, but it builds a new list and uses O(n) memory. It also misbehaves for raw k > n: the negative index gets clamped and the list comes back unchanged. This is the constant-space follow-up of LeetCode 189: Rotate Array.

The primitive: opposite-end pointers

def reverse(nums, lo, hi):        # reverse nums[lo..hi], both ends inclusive
    while lo < hi:
        nums[lo], nums[hi] = nums[hi], nums[lo]
        lo += 1
        hi -= 1

This is a different kind of two pointers. lo starts at the left, hi at the right, and both move on every step, toward each other. Every swap puts one outer pair in its final place, and no value is destroyed.

The magic trick: three reversals make a rotation

Rotate [1,2,3,4,5,6,7] right by k = 3:

[1, 2, 3, 4, 5, 6, 7]      start, k = 3
        ↓ reverse the whole array
[7, 6, 5, 4, 3, 2, 1]
        ↓ reverse the first k = 3
[5, 6, 7, 4, 3, 2, 1]
        ↓ reverse the remaining n − k = 4
[5, 6, 7, 1, 2, 3, 4]      right-rotated by 3 ✓

Why it works. Split the array into two blocks, A B, where B is the last k elements. A right rotation wants B A. Reversing everything gives rev(B) rev(A): the blocks are in the right order, but each one is backwards. Reversing each block again restores its contents. Check one element: the value at index i ends at (i + k) % n, so the 1 at index 0 lands at index 3. ✓

Two details decide whether it crashes or passes:

• Normalize with k %= n. Rotating by k + n is the same as rotating by k, and test cases love k > n.
• Guard n == 0 first, since k % 0 raises. After normalizing, k == 0 means there is nothing to do.

A bonus from Python: when n > 0, k % n is never negative, so a negative k (a left rotation) just works. In C or Java the remainder keeps the sign of k, so add n if it comes out negative.

def rotate_right(nums, k):
    n = len(nums)
    if n == 0:
        return nums          # avoid k % 0
    k %= n                   # rotating by 10 on n = 7 equals rotating by 3
    if k == 0:
        return nums
    reverse(nums, 0, n - 1)  # whole array
    reverse(nums, 0, k - 1)  # first k
    reverse(nums, k, n - 1)  # remaining n - k
    return nums

The three reversals make at most n swaps in total: about n/2 for the whole array, and about n/2 more across the two blocks. That is O(n) time and O(1) extra space.

Your turn: test it like a professional

Check your rotate_right against a simple reference that is allowed to use extra memory. Run many small random cases, including k = 0, k > n and negative k:

import random

def rotate_right_reference(nums, k):
    n = len(nums)
    if n == 0:
        return nums[:]
    k %= n
    return nums[n - k:] + nums[:n - k]    # extra space is fine for a reference

def check(trials=200, max_n=8):
    for _ in range(trials):
        n = random.randint(0, max_n)
        nums = [random.randint(-5, 5) for _ in range(n)]
        k = random.randint(-3, 12)
        got = rotate_right(nums[:], k)
        want = rotate_right_reference(nums[:], k)
        assert got == want, (nums, k, got, want)
    print("all matched")

Success means check() prints all matched. If it fails only for negative k, look at your normalization.

Transfer challenge: reverse the words. A character array holds "the sky is blue". Rearrange it in place into "blue is sky the".

def reverse_words(chars):
    n = len(chars)
    reverse(chars, 0, n - 1)               # step 1: flip everything
    start = 0
    for end in range(n + 1):               # step 2: flip each word back
        if end == n or chars[end] == ' ':
            reverse(chars, start, end - 1)
            start = end + 1
    return chars

Move 5: Build strings once, or edit a buffer

Smell: the slow code rebuilds a whole string on every step.

Strings are frozen

Every Python str is immutable. "abc"[0] = "z" raises TypeError, and every "edit" produces a new object. So when you build output piece by piece, the real cost is how much copying you trigger.

# Good: collect pieces, join once
parts = []
for token in tokens:
    parts.append(transform(token))
result = "".join(parts)          # one final pass over all characters

# Risky: concatenate in a loop
result = ""
for token in tokens:
    result += transform(token)   # may copy everything built so far

If each += copies the whole prefix, n one-character appends copy 1 + 2 + … + n characters, which is O(n²). CPython can sometimes grow an unshared string in place and avoid the copy, but the language doesn't guarantee that, and other runtimes may not do it. "".join(parts) costs time proportional to the total output length. The rule: collect pieces in a list and join once.

To edit text in place, work on a list of characters and join at the end:

buf = list("hello")        # ['h','e','l','l','o']
buf[0] = "H"
text = "".join(buf)        # 'Hello'

For bytes, bytearray is the mutable counterpart. ⚠️ A list of characters is not a string: comparisons, in checks and hashing all behave differently. Join it back before returning text.

Boss level: run-length compression in place

Run-length encoding is one of the oldest compression ideas. Fax machines use it on long runs of white and black pixels. Here is the interview version, LeetCode 443: String Compression. You get chars, a list of characters. Replace each maximal group of equal characters with the character followed by its count, but write no count for a group of length 1. Do it in the same list and return the new valid length.

['a','a','b','b','c','c','c'] should become ['a','2','b','2','c','3'], returning 6.

This is Move 3's write-behind-the-reader pattern with one twist: the output rate varies. A group of any length becomes one or more output characters, so read jumps a whole group at a time.

def compress(chars: list[str]) -> int:
    n = len(chars)
    write = 0
    read = 0
    while read < n:
        ch = chars[read]           # capture BEFORE any overwrite
        run_end = read
        while run_end < n and chars[run_end] == ch:
            run_end += 1
        count = run_end - read
        chars[write] = ch
        write += 1
        if count > 1:
            for d in str(count):   # 12 -> '1' then '2'
                chars[write] = d
                write += 1
        read = run_end             # jump to the next group
    return write

Index 6 still holds a stale 'c'. That is fine: as in Remove Element, the caller reads only chars[:6].

Why the overwrite is safe

It comes down to one inequality. A group of length c ≥ 2 writes 1 + digits(c) characters, and digits(c) ≤ c − 1 for every c ≥ 2. So the output is at most c. A group of length 1 writes exactly 1. Therefore:

• The output is never longer than the input, and after each group, write <= read.
• Every write lands inside cells the group scan has already consumed. The group's character was saved in ch before the first overwrite.

Change the rule and it breaks. If single characters also had to write a '1', then "abc" would become "a1b1c1", twice as long. A forward pass in place would overwrite characters it hasn't read yet. The no-digit rule for single characters is what makes the in-place pass possible.

            divisor = 1
            while count // divisor >= 10:
                divisor *= 10
            while divisor:
                chars[write] = chr(ord('0') + count // divisor)
                write += 1
                count %= divisor
                divisor //= 10

Your turn. Implement compress and predict the result for each case:

1. ['a']
2. ['a','a','a']
3. ['a','b','c']
4. list('a' * 12)

Move 6: Precompute once, answer many

Smell: the array never changes, but you keep re-adding the same stretches of it.

Every move so far answered one question with one pass. Now the workload changes. The array is fixed and thousands of queries ask, "what is the sum from index l to index r?" Scanning each range costs O(n) per query, so q queries cost O(nq). This is the situation where spending memory up front pays off.

The odometer trick

A car's odometer records total distance since the start. To find the length of one leg of a trip, you don't re-drive it; you subtract two readings. A prefix-sum array records the same kind of running total.

Let prefix[k] be the sum of the first k elements, with prefix[0] = 0 for the empty prefix:

boundary:  0   1   2   3   4
           | 2 | 1 | 4 | 3 |      nums
prefix:    0   2   3   7   10
           ^               ^
      no elements      all four

The readings sit between elements, which is why there are n + 1 of them. For an inclusive range [l, r], prefix[r + 1] covers everything through r and prefix[l] covers everything before l. Subtracting cancels the part you don't want:

sum(l..r) = prefix[r + 1] − prefix[l]

def build_prefix(nums):
    prefix = [0] * (len(nums) + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    return prefix

def range_sum(prefix, l, r):
    # inclusive indices, 0 <= l <= r < len(nums)
    return prefix[r + 1] - prefix[l]

For nums = [2, 1, 4, 3], the query [1, 3] gives prefix[4] − prefix[1] = 10 − 2 = 8, and [2, 2] gives 7 − 3 = 4. Always test a single-element range. If you forget the + 1, the query [2, 2] returns prefix[2] − prefix[2] = 0.

When it's worth it, and when it isn't

Building the table costs O(n) time and O(n) space. After that every query is O(1), so the total is O(n + q). Negative numbers are fine, because subtraction still cancels correctly. Two limits:

• Updates make the table stale. Change nums[i] and every later prefix entry is wrong. With frequent updates and few queries, rebuilding can cost more than just scanning.
• Not every operation subtracts. You can't recover a range maximum from two prefix maxima. If the maximum doesn't change between the two readings, you learn nothing about the maximum inside the range. Addition can be undone by subtraction; max cannot, and the trick depends on that inverse.

Your turn: build the prefix array for [5, −2, 4, 1]. Answer the inclusive queries [0, 3], [1, 2] and [2, 2]. Then: what goes wrong if nums[1] changes to 10 and you keep the old table?

For prefix/suffix products, pivot indices and difference arrays, continue with Prefix, Suffix & Range Updates.

Final round: no label on the problem

Real problems don't say which move they want. Start from the contract, find the smell, then pick the move.

Challenge 1: Move Zeroes

Turn [0, 5, 0, 3, 8] into [5, 3, 8, 0, 0] in the same list. Keep the non-zero values in their original order and use O(1) extra space. This is LeetCode 283: Move Zeroes.

Before peeking, answer these:

1. Which move applies, and why?
2. What must you do beyond what Remove Element required?
3. Why can't your writes destroy a non-zero value you haven't read yet?
4. What should [0, 0], [4, −2] and [1, 0, 2, 0] become?

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

Test the contract, not just the printout. A reference solution may use extra memory even when yours can't:

def check_move_zeroes(values):
    actual = values[:]
    kept = [x for x in values if x != 0]
    expected = kept + [0] * (len(values) - len(kept))
    assert move_zeroes(actual) is None      # mutates, returns nothing
    assert actual == expected

for case in ([], [0], [0, 0], [0, 1], [4, -2], [1, 0, 2, 0]):
    check_move_zeroes(case)

Each case targets a different boundary: a leading zero before a value ([0, 1]), trailing zeros, nothing to keep, nothing to remove. (LeetCode's input is never empty, but testing [] costs nothing.)

Challenge 2: two moves at once

Remove repeated values from an unsorted list in place, keep each value's first occurrence, and return the valid length. [3, 1, 3, 2, 1] should give the front region [3, 1, 2] and return 3. You may use O(n) extra memory. What can the write pointer not tell you?

def keep_first_occurrences(nums):
    seen = set()
    write = 0
    for read in range(len(nums)):
        x = nums[read]
        if x not in seen:
            seen.add(x)
            nums[write] = x
            write += 1
    return write

Cheat sheet: smell → move

Before moving on, pick one problem from this lesson and explain it aloud, from a blank editor: what the contract requires, what the slow version repeats, what each variable means at a specific moment in the loop, why the fast version is correct, and which changed constraint would break it. If you can do that, the later patterns are variations on these moves.

Next: Two Pointer Techniques for systematic pointer movement, Sliding Window Patterns for keeping state over a moving range, and Hash Maps & Sets for lookup and grouping problems.