Arrays & Strings

You're given a list of numbers and need to flip the order without creating a new list.

Start here in Foundations →

In plain English: You're given a list of numbers and need to flip the order without creating a new list.

Two pointers converging from opposite ends is the go-to for symmetric array operations — each swap brings both ends closer to the center.

def reverse(a):
    l, r = 0, len(a) - 1
    # converge from both ends
    while l < r:
        a[l], a[r] = a[r], a[l]
        l += 1
        r -= 1
    return a

# Test: reverse([1,2,3,4,5]) == [5,4,3,2,1]

In plain English: In a sorted list, find two numbers that add up to a specific target.

In a sorted array, the sum of two pointers tells you which direction to move — too small means the left should increase, too big means the right should decrease.

def two_sum_sorted(a, t):
    l, r = 0, len(a) - 1
    while l < r:
        s = a[l] + a[r]
        # sum tells us which pointer to move
        if s == t:
            return [l, r]
        elif s < t:
            l += 1
        else:
            r -= 1
    return []

# Test: two_sum_sorted([1,2,3,5,8], 10) == [2, 4]

In plain English: Check whether a word or phrase reads the same forwards and backwards.

A palindrome is symmetric, so comparing from both ends toward the center catches any mismatch in O(n/2) comparisons.

def is_palindrome(s):
    l, r = 0, len(s) - 1
    while l < r:
        if s[l] != s[r]:  # mismatch = not palindrome
            return False
        l += 1; r -= 1
    return True

# Test: is_palindrome("racecar") == True

In plain English: Combine two already-sorted lists into a single sorted list.

Both arrays are sorted, so the smallest unprocessed element is always at one of the two front pointers — just pick the smaller one.

def merge(a, b):
    res, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:  # always pick the smaller front
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
    res.extend(a[i:])
    res.extend(b[j:])
    return res

# Test: merge([1,3,5], [2,4,6]) == [1,2,3,4,5,6]

In plain English: Shift every element k positions to the left, wrapping elements from the front to the back.

The 3-reverse trick works because reversing segments then the whole array is equivalent to a cyclic shift — no extra space needed.

def left_rotate(a, k):
    k = k % len(a)  # handle wrap-around
    return a[k:] + a[:k]

# Test: left_rotate([1,2,3,4,5], 2) == [3,4,5,1,2]

# In-place variant (3 reverses):
def left_rotate_inplace(a, k):
    k = k % len(a)
    def rev(lo, hi):
        while lo < hi:
            a[lo], a[hi] = a[hi], a[lo]
            lo += 1; hi -= 1
    rev(0, k - 1)
    rev(k, len(a) - 1)
    rev(0, len(a) - 1)

In plain English: Find the consecutive chunk of numbers in an array that adds up to the largest possible sum.

At each position, decide: extend the current subarray or start fresh. If the running sum goes negative, starting over is always better.

def max_subarray(a):
    cur_max = global_max = a[0]
    for x in a[1:]:
        cur_max = max(x, cur_max + x)  # extend or restart
        global_max = max(global_max, cur_max)
    return global_max

# Test: max_subarray([-2,1,-3,4,-1,2,1,-5,4]) == 6

In plain English: Find which group of k consecutive elements in an array has the biggest total.

Instead of recalculating the sum from scratch, subtract the leaving element and add the entering one — O(1) per slide.

def max_sum_k(a, k):
    window = sum(a[:k])
    best = window
    for i in range(k, len(a)):
        window += a[i] - a[i - k]  # slide: add right, drop left
        best = max(best, window)
    return best

# Test: max_sum_k([1,4,2,10,2,3,1,0,20], 4) == 24

In plain English: Pre-process an array so you can instantly answer 'what is the sum between index l and r?'

Prefix sums turn any range-sum query into a subtraction of two precomputed values — trade O(n) setup for O(1) per query.

def build_prefix(a):
    p = [0] * (len(a) + 1)
    for i in range(len(a)):
        p[i + 1] = p[i] + a[i]  # p[i] = sum of a[0..i-1]
    return p

def range_sum(p, l, r):
    return p[r + 1] - p[l]

# a = [1,3,5,7,9]; p = build_prefix(a)
# range_sum(p, 1, 3) == 15  (3+5+7)

In plain English: For each number in the array, compute the product of all the other numbers without using division.

Build prefix products left-to-right, then suffix products right-to-left. result[i] = prefix[i] * suffix[i]. Can be done in one array with two passes to stay O(1) extra space.

def product_except_self(nums):
    n = len(nums)
    result = [1] * n
    # left pass: prefix products
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    # right pass: suffix products
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

# Test: product_except_self([1,2,3,4]) == [24,12,8,6]
# Test: product_except_self([-1,1,0,-3,3]) == [0,0,9,0,0]

Given an array a, reverse it in-place.

Signals

• 'In-place' → O(1) extra space, must modify the array directly
• 'Reverse' → symmetric operation, work from both ends

Given array a and integer k, return the left-rotated array.

Signals

• 'Rotate by k' → cyclic shift, elements wrap around
• Can be done in-place with the 3-reverse trick

Given array a, find the contiguous subarray with the largest sum.

Signals

• 'Contiguous subarray' → must be consecutive elements
• 'Maximum sum' → optimization over all possible subarrays
• At each position: extend current window or start fresh

Given sorted array a and target t, return indices of the pair that sums to t.

Signals

• 'Sorted' → exploit ordering, don't need a hash map
• 'Pair that sums to target' → classic two-sum variant
• Sum too small → move left pointer right; too big → move right pointer left

Given string s, return True if it's a palindrome.

Signals

• 'Palindrome' → reads same forwards and backwards → symmetric
• Compare from both ends toward center

Given sorted arrays a and b, return a single merged sorted array.

Signals

• 'Two sorted arrays' + 'merge' → classic merge step
• Both are already sorted → compare front elements

Given array a and window size k, find the maximum sum of any contiguous k elements.

Signals

• 'Contiguous k elements' → fixed-size window
• 'Maximum sum' → slide the window, track max
• Fixed window size → subtract leaving, add entering

Given array a, answer multiple range-sum queries [l, r] efficiently.

Signals

• 'Multiple queries' → precompute something to answer each in O(1)
• 'Range sum' → prefix sum turns this into a subtraction

Given array nums, return an array where each element is the product of all other elements. No division allowed.

Signals

• 'Product of all except self' without division → prefix and suffix products
• 'O(n) without division' → two-pass: left products then right products

Write-pointer compaction for sorted arrays. Returns new length.

w = 1
for i in range(1, len(a)):
    if a[i] != a[i-1]:
        a[w] = a[i]
        w += 1
return w

Write-pointer skips unwanted values. O(1) space removal pattern.

w = 0
for r in range(len(a)):
    if a[r] != val:
        a[w] = a[r]
        w += 1
# a[:w] has val removed

Transpose + reverse-rows rotates 90 degrees clockwise in-place. Classic matrix manipulation.

n = len(m)
for i in range(n):
    for j in range(i+1, n):
        m[i][j], m[j][i] = m[j][i], m[i][j]
for row in m:
    row.reverse()

Left boundary search finds the first occurrence. Key for range queries and count problems.

lo, hi = 0, len(a)
while lo < hi:
    mid = lo + (hi - lo) // 2
    if a[mid] < target: lo = mid + 1
    else: hi = mid
return lo

Array rotation underpins circular buffer logic and modular index arithmetic.

a[-1:] + a[:-1]
# or
a.insert(0, a.pop())

Fixed-size sliding window computes running aggregates in O(n). Core optimization pattern.

mx = cur = sum(a[:k])
for i in range(k, len(a)):
    cur += a[i] - a[i-k]
    mx = max(mx, cur)

At each element: extend current subarray or start fresh. The simplest DP pattern — must be instant.

def maxSubArray(nums):
    cur = res = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        res = max(res, cur)
    return res

Bottom-up DFS. At each node: update global max with left+node+right. Return single branch for parent to use.

def maxPathSum(root):
    res = [float('-inf')]
    def dfs(node):
        if not node: return 0
        left = max(dfs(node.left), 0)   # ignore negative paths
        right = max(dfs(node.right), 0)
        # path through this node as turning point
        res[0] = max(res[0], left + node.val + right)
        # return max single-side path for parent
        return node.val + max(left, right)
    dfs(root)
    return res[0]

Merging sorted lists is the core of merge sort and merge-k-lists.

i = j = 0
merged = []
while i < len(a) and j < len(b):
    if a[i] <= b[j]:
        merged.append(a[i]); i += 1
    else:
        merged.append(b[j]); j += 1
merged.extend(a[i:])
merged.extend(b[j:])

Two-pointer write keeps unique elements in-place with O(1) space. Core array cleanup technique.

# Two-pointer write — keep unique in-place
w = 1
for r in range(1, len(a)):
    if a[r] != a[r - 1]:
        a[w] = a[r]
        w += 1
# a[:w] has unique elements

Converging pointers shrink the search space from both ends. Core of two-sum-sorted and palindrome.

l, r = 0, len(a) - 1
while l < r:
    # process a[l], a[r]
    l += 1; r -= 1

Sortedness check is a precondition guard for binary search and merge operations.

all(a[i] <= a[i+1] for i in range(len(a)-1))

Sort by start, then check if each interval starts before the previous one ends. Foundation for meeting rooms.

intervals.sort()
for i in range(1, len(intervals)):
    if intervals[i][0] < intervals[i-1][1]:
        return True  # overlap
return False

Tracking have/need counts is the matching logic inside minimum-window-substring.

need, have = len(cnt_t), 0
for c in window:
    window_cnt[c] += 1
    if window_cnt[c] == cnt_t[c]:
        have += 1

Sort-then-merge is the standard O(n log n) approach to interval union.

a.sort()
res = [a[0]]
for s, e in a[1:]:
    if s <= res[-1][1]:
        res[-1][1] = max(res[-1][1], e)
    else:
        res.append([s, e])

Fixed-window sliding avoids re-summing by adding the new element and removing the old one.

window = sum(a[:k])
best = window
for i in range(k, len(a)):
    window += a[i] - a[i - k]
    best = max(best, window)

Move-zeroes is remove-element followed by a fill. Classic two-pointer warm-up.

w = 0
for r in range(len(a)):
    if a[r] != 0:
        a[w] = a[r]
        w += 1
while w < len(a):
    a[w] = 0
    w += 1

Prefix sum gives O(1) range queries after O(n) build. p[r+1] - p[l] = sum(a[l..r]). Off-by-one: p has length n+1.

p = [0] * (len(a) + 1)
for i in range(len(a)):
    p[i+1] = p[i] + a[i]
# range sum [l, r] inclusive:
total = p[r+1] - p[l]

Prefix/suffix product arrays avoid division. O(n) time, O(1) extra space with in-place right pass.

n = len(a)
res = [1] * n
for i in range(1, n): res[i] = res[i-1] * a[i-1]
right = 1
for i in range(n-2, -1, -1):
    right *= a[i+1]
    res[i] *= right