Arrays: Common Operations and Patterns

The array patterns in this post show up in almost every interview problem and a huge fraction of real-world code. Learning them well means you stop solving problems from scratch and start recognising them.

Traversal

The simplest pattern: visit every element once. O(n) time, O(1) space (no extra collection).

nums = [10, 20, 30, 40, 50]
for x in nums:
    print(x)

When you need the index too:

for i, x in enumerate(nums):
    print(i, x)

Traversing two arrays in lockstep:

a = [1, 2, 3]
b = [10, 20, 30]
for x, y in zip(a, b):
    print(x + y)

Traversing in reverse:

for x in reversed(nums):
    print(x)

Most array algorithms are built by sticking some bookkeeping inside one of these loops.

Linear search

Looking for a value by scanning. O(n) worst case.

def linear_search(nums, target):
    for i, x in enumerate(nums):
        if x == target:
            return i
    return -1

print(linear_search([10, 20, 30, 40], 30))    # 2
print(linear_search([10, 20, 30, 40], 99))    # -1

Linear search is fine when the array is small or unsorted. If the array is sorted and large, binary search (O(log n)) is the right tool — we’ll cover that in its own post.

A useful variant — finding all matches:

def find_all(nums, target):
    return [i for i, x in enumerate(nums) if x == target]

print(find_all([1, 2, 3, 2, 5, 2], 2))    # [1, 3, 5]

Another — find the first index where a condition holds:

def first_index_above(nums, threshold):
    for i, x in enumerate(nums):
        if x > threshold:
            return i
    return -1

print(first_index_above([3, 1, 4, 1, 5, 9], 4))    # 4

Insertion and deletion in context

You already know the cost (O(n) in the middle), but the patterns are worth seeing.

Insertion at a specific index:

nums = [10, 20, 30, 40]
nums.insert(2, 99)
print(nums)    # [10, 20, 99, 30, 40]

Deletion by value:

nums = [10, 20, 30, 20]
nums.remove(20)     # removes the first 20
print(nums)         # [10, 30, 20]

Filtering many out at once — much cheaper than calling remove in a loop:

nums = [1, 2, 3, 4, 5, 6]
nums = [x for x in nums if x % 2 != 0]
print(nums)    # [1, 3, 5]

A common interview problem variant is “delete in place,” where you’re not allowed to allocate a new array. The trick is two pointers — one for reading, one for writing.

def remove_value(nums, val):
    """Remove all occurrences of val in place. Return the new length."""
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    return write

nums = [3, 2, 2, 3]
n = remove_value(nums, 3)
print(nums[:n])    # [2, 2]

This is the “two-pointer” technique in its simplest form. We’ll use it again and again.

Reversal

Three ways, in increasing order of cleverness.

With extra space — easy but uses O(n) extra memory:

nums = [1, 2, 3, 4, 5]
reversed_nums = nums[::-1]
print(reversed_nums)    # [5, 4, 3, 2, 1]

Using a built-in — in place, O(1) extra space:

nums = [1, 2, 3, 4, 5]
nums.reverse()
print(nums)    # [5, 4, 3, 2, 1]

By hand — the algorithm every interviewer wants to see:

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

nums = [1, 2, 3, 4, 5]
reverse_in_place(nums)
print(nums)    # [5, 4, 3, 2, 1]

The two-pointer reversal is O(n) time and O(1) space. Memorise it — it’s the building block of array rotation.

Rotation

“Rotate the array to the right by k positions.” A favourite interview question because there are three clean solutions, each with a different complexity trade-off.

Example: [1, 2, 3, 4, 5] rotated right by k=2 becomes [4, 5, 1, 2, 3].

Approach 1 — extra array. Place each element at its new position.

def rotate_v1(nums, k):
    n = len(nums)
    k %= n
    result = [0] * n
    for i in range(n):
        result[(i + k) % n] = nums[i]
    return result

print(rotate_v1([1, 2, 3, 4, 5], 2))    # [4, 5, 1, 2, 3]

Time: O(n). Space: O(n).

Approach 2 — slicing. Almost cheating, very Pythonic.

def rotate_v2(nums, k):
    k %= len(nums)
    return nums[-k:] + nums[:-k]

print(rotate_v2([1, 2, 3, 4, 5], 2))    # [4, 5, 1, 2, 3]

Time: O(n). Space: O(n).

Approach 3 — three reversals. The clever in-place solution.

def rotate_v3(nums, k):
    n = len(nums)
    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)         # reverse the whole array
    reverse(0, k - 1)          # reverse the first k
    reverse(k, n - 1)          # reverse the rest

nums = [1, 2, 3, 4, 5]
rotate_v3(nums, 2)
print(nums)    # [4, 5, 1, 2, 3]

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

That third approach is the answer interviewers want. Walk through it on paper with [1, 2, 3, 4, 5] and k=2 — the trick clicks immediately.

Prefix sums

A prefix sum is an array where each entry holds the sum of all elements up to that index in the original array.

nums =       [3, 1, 4, 1, 5, 9, 2]
prefix =     [3, 4, 8, 9, 14, 23, 25]

Build it in one pass:

def prefix_sums(nums):
    out = [0] * len(nums)
    out[0] = nums[0]
    for i in range(1, len(nums)):
        out[i] = out[i - 1] + nums[i]
    return out

print(prefix_sums([3, 1, 4, 1, 5, 9, 2]))
# [3, 4, 8, 9, 14, 23, 25]

Why bother? Because with the prefix array, the sum of any subrange is O(1):

sum(nums[l..r]) = prefix[r] - prefix[l - 1]    (with prefix[-1] = 0)

So if you need to answer many “what’s the sum from index l to index r?” questions, you build the prefix array once in O(n), and each query is O(1) instead of O(n).

def range_sum(prefix, l, r):
    if l == 0:
        return prefix[r]
    return prefix[r] - prefix[l - 1]

p = prefix_sums([3, 1, 4, 1, 5, 9, 2])
print(range_sum(p, 1, 3))    # 1 + 4 + 1 = 6
print(range_sum(p, 0, 6))    # 25

Prefix sums show up in subarray problems, equilibrium-point problems, and 2D image-processing problems (where they become “summed-area tables”). They’re one of the highest-leverage tricks in array DSA.

Kadane’s algorithm — a preview

Problem. Given an array of integers (possibly negative), find the maximum sum of any non-empty contiguous subarray.

Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → the subarray [4, -1, 2, 1] sums to 6.

The brute force is O(n²) — try every start and end pair. Kadane’s algorithm solves it in O(n) with O(1) space, and it’s one of the most elegant algorithms in DSA.

The insight: walk left to right. At each index, ask “what’s the best subarray that ends here?” That’s either the current element on its own, or the current element added to the best subarray ending at the previous index. Take the max.

def max_subarray(nums):
    best_ending_here = nums[0]
    best_overall = nums[0]
    for x in nums[1:]:
        best_ending_here = max(x, best_ending_here + x)
        best_overall = max(best_overall, best_ending_here)
    return best_overall

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))    # 6

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

We’ll dig into the intuition in the practice-problems post — but for now, just appreciate that the brute O(n²) collapses to O(n) with one variable’s worth of state. That collapse is what DSA is for.

One-pass vs two-pass thinking

A theme that comes up constantly: can you do the work in one walk through the array, or do you need two?

Many problems are easiest to first think about in two passes — gather information in pass 1, use it in pass 2 — and then refactor to a single pass if needed.

Example — average gap from the mean.

# Two-pass — clearest
def avg_gap_two_pass(nums):
    mean = sum(nums) / len(nums)
    total = 0
    for x in nums:
        total += abs(x - mean)
    return total / len(nums)

Two passes is O(2n) = O(n). For most problems this is fine.

But sometimes one-pass is required (a stream of data) or cheaper (avoids re-reading from disk). When the second pass uses something you computed in the first, you can often fold them together with a clever invariant — that’s the Kadane-style move.

One-pass example — running max:

def running_max(nums):
    out = []
    current = float("-inf")
    for x in nums:
        current = max(current, x)
        out.append(current)
    return out

print(running_max([3, 1, 4, 1, 5, 9, 2, 6]))
# [3, 3, 4, 4, 5, 9, 9, 9]

A useful habit when you finish a problem: ask “could I do this in one pass?” Sometimes the answer is no, but the question often reveals a better solution.

A worked example — equilibrium index

Problem. Given an array, return any index i such that the sum of values to the left of i equals the sum to the right. If none exists, return -1.

Brute force — O(n²). For each index, sum both sides.

def equilibrium_slow(nums):
    n = len(nums)
    for i in range(n):
        left = sum(nums[:i])
        right = sum(nums[i + 1:])
        if left == right:
            return i
    return -1

Prefix-sum approach — O(n) time, O(1) extra space.

def equilibrium(nums):
    total = sum(nums)
    left = 0
    for i, x in enumerate(nums):
        right = total - left - x
        if left == right:
            return i
        left += x
    return -1

print(equilibrium([-7, 1, 5, 2, -4, 3, 0]))    # 3

The brute force does the same arithmetic over and over. The fast version sees the structure: as you walk forward, left grows by x each step, and right is whatever’s left. That’s the prefix-sum trick at its purest.

Practice problems

For each problem, aim for the best time complexity you can. Then write down what you achieved.

1. Given an array, return True if it contains the same element twice in a row (e.g. [1, 2, 2, 3]).
2. Given two arrays of equal length, return their element-wise maximum.
3. Given an array, replace each element with the maximum of the elements to its right (the last element becomes -1).
4. Given an array, return the index of the first element that equals the sum of all elements before it.
5. Given an array of integers, find the longest run of consecutive equal values and return its length.
6. Given an array, return a new array where each element is the sum of itself and the previous element (a prefix-sum builder).
7. Given an array and a number k, return the maximum sum of any k consecutive elements. (Hint: sliding window.)
8. Given an array of integers (possibly negative), return the maximum sum of any contiguous subarray using Kadane’s algorithm.

Recap

You now know:

• The standard traversal patterns: forward, with index, two-array, reverse
• Linear search and its all-matches and first-match variants
• In-place deletion with a two-pointer write index
• Three ways to reverse, and three ways to rotate
• Prefix sums turn many “range query” problems into O(1) lookups
• Kadane’s algorithm turns a quadratic subarray problem into linear
• Two-pass solutions are often clearest; one-pass solutions are often cheaper

Next steps

Now we move from learning patterns to applying them. The next post walks through ten classic array problems with full solutions — exactly the texture of a junior interview round.

→ Next: Arrays — 10 Practice Problems with Solutions

Questions or feedback? Email codeloomdevv@gmail.com.