A Staff-level array problem is rarely about the array itself. It is about recognizing the structure that makes the array easy to reason about.

This study guide is an original, copyright-safe set of notes based on the themes of Chapter 5, Arrays, from Elements of Programming Interviews in Python. It is not a transcription or close rewrite of the book.

1. Why Arrays Matter

Arrays are one of the most important foundations of coding interviews because many apparently different problems reduce to a small set of reusable patterns.

At Staff level, the goal is not to memorize dozens of array solutions.

The goal is to recognize:

what information must be maintained,
what work is being repeated,
whether the input has useful ordering,
whether the problem is local or global,
whether the answer can be constructed in place,
and which invariant guarantees correctness.

A useful mental model is:

Array
  ↓
Understand structure
  ↓
Identify repeated work
  ↓
Choose a pattern
  ↓
Maintain an invariant
  ↓
Reduce complexity
  ↓
Validate edge cases

2. Array Complexity You Should Know

For a Python list, common operations have approximately these costs:

Operation	Typical Complexity
Access by index	O(1)
Update by index	O(1)
Append	O(1) amortized
Pop from end	O(1)
Insert at beginning	O(n)
Delete from beginning	O(n)
Search for a value	O(n)
Sort	O(n log n)
Reverse in place	O(n)

The key Staff-level observation is:

Random access is cheap; moving many elements is not.

Therefore, if a solution repeatedly inserts or deletes near the beginning of a Python list, question the design.

3. Pattern 1 — Two Pointers

Two pointers are useful when two positions in an array can move through the data without repeatedly restarting a search.

Typical forms include:

left  →             ← right

or:

slow →
fast ────→

Common applications

Pair-sum problems
Removing duplicates
Partitioning
Merging sorted arrays
Reversing an array
Detecting relationships between elements

Example: pair sum in a sorted array

Suppose:

nums = [1, 2, 4, 7, 11, 15]
target = 15

Start with:

left = 0
right = len(nums) - 1

If:

nums[left] + nums[right] > target

move right leftward.

If:

nums[left] + nums[right] < target

move left rightward.

Otherwise, the pair has been found.

def pair_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1

    while left < right:
        total = nums[left] + nums[right]

        if total == target:
            return left, right
        if total < target:
            left += 1
        else:
            right -= 1

    return None

Complexity

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

The important insight is not the code.

It is the monotonic movement of the two pointers.

4. Pattern 2 — Sliding Window

Sliding windows are useful when the problem concerns a contiguous portion of an array.

Instead of recomputing every range:

[0]
[0,1]
[0,1,2]
[1,2]
[1,2,3]
...

maintain a current window and update it incrementally.

A typical structure is:

left = 0

for right in range(len(nums)):
    # Add nums[right]

    while window_is_invalid():
        # Remove nums[left]
        left += 1

    # Process current window

When to consider it

Look for language such as:

contiguous
subarray
longest range
shortest range
at most K
at least K
maximum/minimum window

Important constraint

Sliding windows often rely on a monotonic property.

For example, if all values are non-negative, increasing the right boundary cannot decrease the sum.

That property makes shrinking the left boundary safe.

5. Pattern 3 — Prefix Sums

Prefix sums turn repeated range-sum calculations into constant-time queries after linear preprocessing.

Define:

prefix[i] = sum of elements before index i

For:

nums = [2, 4, 1, 5]

we can construct:

prefix = [0, 2, 6, 7, 12]

Then the sum of:

nums[l:r]

can be computed as:

prefix[r] - prefix[l]

Complexity

Building the prefix array:

O(n)

Each range query:

O(1)

This is a classic example of:

Spend computation once to make repeated queries cheap.

6. Pattern 4 — Prefix Information + Hash Map

Some array problems require finding a subarray satisfying a sum condition.

A powerful technique is to combine:

Prefix sum
+
Hash map

Suppose:

prefix[j] - prefix[i] = target

Then:

prefix[i] = prefix[j] - target

So while scanning the array, we can ask whether the required earlier prefix sum has already been seen.

This changes many quadratic-looking problems into linear-time solutions.

The broader pattern is:

Repeated range computation
        ↓
Prefix representation
        ↓
Fast lookup
        ↓
O(n)

7. Pattern 5 — In-Place Transformation

At Staff level, always ask:

Can I solve this without allocating another array?

Examples include:

reversing an array,
rotating an array,
partitioning,
removing elements,
rearranging values,
merging data when sufficient space exists.

The trade-off is often:

Extra memory
     ↕
Mutation

Before modifying an input, clarify whether mutation is allowed.

8. Pattern 6 — Partitioning

Partitioning separates elements according to a predicate.

For example:

values < pivot | values >= pivot

A basic two-pointer partition is:

def partition(nums, pivot):
    left = 0

    for right in range(len(nums)):
        if nums[right] < pivot:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1

    return left

The important invariant is:

Before left:
    every element satisfies the left predicate

The exact invariant depends on the problem.

Partitioning appears in:

quicksort,
selection algorithms,
Dutch National Flag problems,
filtering,
stable/unstable rearrangement problems.

9. Pattern 7 — Dutch National Flag

When an array contains three categories, a three-way partition can be useful.

Conceptually:

[ category 0 ][ category 1 ][ unknown ][ category 2 ]

Maintain three regions:

low
mid
high

and process the unknown region.

The key idea is not the particular code.

It is:

Maintain regions whose meaning is known, while shrinking the unknown region.

This is a general algorithmic pattern.

10. Pattern 8 — Merge Two Sorted Arrays

If two sequences are already sorted, do not repeatedly search for the next smallest value.

Use two indices:

i → array A
j → array B

Compare:

if a[i] <= b[j]:
    take a[i]
    i += 1
else:
    take b[j]
    j += 1

Each element is processed once.

Complexity

Time:  O(n + m)
Space: O(n + m)

When the destination array has spare capacity, the merge can sometimes be performed from the end to avoid overwriting unprocessed values.

11. Pattern 9 — Remove Duplicates

For a sorted array, duplicates have structure.

Example:

[1, 1, 2, 2, 2, 4, 5, 5]

A slow/fast pointer approach can maintain:

[unique values][unprocessed values]

The invariant can be:

Everything before the write position is already the desired deduplicated prefix.

This turns repeated shifting into a single scan.

12. Pattern 10 — Buy/Sell and Running Extremes

Many array problems can be solved by maintaining a best value seen so far.

For example, for a one-transaction stock problem:

minimum price seen so far
+
best profit so far

At each price:

min_price = min(min_price, price)
best_profit = max(best_profit, price - min_price)

Complexity

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

This pattern generalizes to:

running minimum,
running maximum,
best prefix,
best suffix,
maximum difference,
maximum profit.

13. Pattern 11 — Maximum Subarray

A classic array problem asks for the contiguous region with the largest sum.

The important reasoning is:

At each position, should the current element extend the previous candidate, or should a new candidate start here?

A compact recurrence is:

current = max(value, current + value)
best = max(best, current)

Python implementation:

def max_subarray(nums):
    current = best = nums[0]

    for x in nums[1:]:
        current = max(x, current + x)
        best = max(best, current)

    return best

Complexity

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

The Staff-level explanation should focus on the invariant rather than simply naming the algorithm.

14. Pattern 12 — Rearrangement and Rotation

Array rotation often looks like a problem requiring another array.

But a rotation can sometimes be implemented through reversals.

For a right rotation by k:

1. Reverse the whole array
2. Reverse the first k elements
3. Reverse the remaining elements

The general lesson is:

Look for transformations that can be composed from simpler in-place operations.

Always normalize:

k %= len(nums)

before performing rotation.

15. Pattern 13 — Majority and Frequency Problems

Some problems ask whether one value appears more frequently than all others or whether an element crosses a frequency threshold.

Possible approaches include:

Approach	Time	Extra Space
Sorting	O(n log n)	Depends
Hash map	O(n)	O(n)
Specialized voting approach	O(n)	O(1)

The Staff-level decision is not simply:

“Which algorithm is fastest?”

Instead ask:

Is the input mutable?
Is ordering important?
Is memory constrained?
Is there guaranteed structure?
Is the query performed once or repeatedly?

16. Pattern 14 — Binary Search on Arrays

Binary search is not only about finding an exact value.

It is a general technique for finding a boundary in a monotonic predicate.

Think:

False False False True True True
                ↑
          first True

This perspective allows binary search to solve problems such as:

first element satisfying a condition,
last element satisfying a condition,
insertion position,
lower bound,
upper bound,
minimum feasible value.

A useful template is:

def first_true(n, predicate):
    left, right = 0, n

    while left < right:
        mid = left + (right - left) // 2

        if predicate(mid):
            right = mid
        else:
            left = mid + 1

    return left

The crucial requirement is monotonicity.

17. Pattern 15 — Search in a Rotated Sorted Array

A rotated sorted array still contains useful ordering information.

Example:

[15, 18, 20, 2, 4, 7, 10]

At each midpoint, determine which half is sorted.

Then ask whether the target belongs to that sorted half.

The Staff-level insight is:

Do not throw away all ordering information just because the array is not globally sorted.

Exploit the partial order that remains.

18. Pattern 16 — Permutations and Next Lexicographic Arrangement

For permutation-style problems, brute-force enumeration can be enormous.

Instead, exploit lexicographic structure.

For the next permutation:

Find the rightmost position i
such that nums[i] < nums[i + 1]

Then:

1. Find the smallest larger value to the right.
2. Swap.
3. Reverse the suffix.

The important idea is:

Make the smallest possible increase, then minimize everything after the changed position.

This is another example of replacing candidate enumeration with structural reasoning.

19. Pattern 17 — Sampling and Randomness

Some array problems involve selecting elements randomly.

When randomness is required over a changing stream, ask:

Can the entire input fit in memory?
Must every element have equal probability?
Is the input known in advance?
Is the data arriving as a stream?

For streaming selection, reservoir-style techniques can provide uniform sampling without storing the entire stream.

This connects array algorithms to production systems:

Large stream
    ↓
Limited memory
    ↓
Maintain compact state
    ↓
Uniform result

20. Invariants: The Most Important Staff-Level Skill

For every array algorithm, ask:

What is guaranteed to be true after every iteration?

Examples:

Two pointers

All discarded candidates cannot contain the answer.

Sliding window

Current window satisfies the required constraint.

Prefix sum

prefix[i] represents the aggregate of everything before i.

Partition

The processed region satisfies its partition predicate.

Binary search

The answer always remains inside the search interval.

Maximum subarray

current = best subarray ending at the current position.

If you can state the invariant clearly, the correctness argument becomes much easier.

21. Edge Cases You Should Test

For array problems, systematically test:

[]
[1]
[1, 1]
[1, 2]
[2, 1]
[0]
[-1]
[0, 0]
Already sorted
Reverse sorted
All identical
Very large input
Very large values
Very small values

Also ask:

Can the input be modified?
Can duplicates occur?
Can values be negative?
Is ordering significant?
Is the array guaranteed to be sorted?
What should happen when no answer exists?
Can k be larger than the array length?
Is an empty result valid?

22. Complexity Patterns

The most important transformations are:

Nested search → Two pointers

O(n²)
  ↓
O(n)

Repeated range computation → Prefix sum

O(n) per query
  ↓
O(1) per query after O(n) preprocessing

Repeated filtering → In-place partition

Extra array
  ↓
O(1) auxiliary space

Enumeration → Mathematical structure

Many candidates
  ↓
Direct construction

Repeated query → Preprocessing

One-time O(n) work
        ↓
Cheap repeated queries

23. Staff-Level Trade-Offs

A strong Staff engineer should discuss trade-offs explicitly.

For example:

Requirement	Possible Direction
Minimum memory	In-place algorithm
Fast repeated queries	Preprocessing/index
Immutable input	Auxiliary structure
Huge streaming input	Streaming algorithm
Simple implementation	Standard library
Strict latency	Precompute/cache
Parallel processing	Partition independent regions
Very large data	External/distributed processing

There is rarely one universally best solution.

The correct answer depends on the constraints.

24. How to Explain an Array Problem in an Interview

Use this sequence:

1. Clarify requirements
        ↓
2. Build a small example
        ↓
3. Describe brute force
        ↓
4. Identify repeated work
        ↓
5. Recognize the pattern
        ↓
6. State the invariant
        ↓
7. Implement
        ↓
8. Test edge cases
        ↓
9. Analyze time and space
        ↓
10. Discuss trade-offs

A strong Staff-level explanation might sound like:

“The brute-force approach repeatedly examines overlapping ranges. Because the window has a monotonic property, I can maintain a sliding window and move each boundary only forward. Each element therefore enters and leaves the window at most once, giving linear time and constant auxiliary space.”

That explanation communicates much more than code alone.

25. Python Array Interview Cheat Sheet

# Length
len(nums)

# Index access
nums[i]

# Append
nums.append(x)

# Remove last
nums.pop()

# Sort in place
nums.sort()

# Sorted copy
sorted(nums)

# Reverse in place
nums.reverse()

# Two pointers
left, right = 0, len(nums) - 1

# Prefix sum
prefix = [0]
for x in nums:
    prefix.append(prefix[-1] + x)

# Frequency counting
from collections import Counter
counts = Counter(nums)

# Binary search
from bisect import bisect_left, bisect_right

Do not use a library function merely because it is shorter.

In an interview, first demonstrate that you understand the underlying algorithm.

26. The Array Pattern Map

Contiguous range
      ↓
Sliding Window / Prefix Sum

Sorted array
      ↓
Two Pointers / Binary Search

Pair relationship
      ↓
Two Pointers / Hash Map

Repeated range query
      ↓
Prefix Sum

Rearrangement
      ↓
Partition / Two Pointers

In-place requirement
      ↓
Index manipulation / Reversal

Monotonic predicate
      ↓
Binary Search

Best contiguous result
      ↓
Running state / Dynamic Programming

Streaming input
      ↓
Compact state / Sampling

This pattern map is more valuable than memorizing individual problems.

27. The Deep Lesson

Arrays teach a broader algorithmic principle:

The fastest solution often comes from discovering what does not need to be recomputed.

Consider the progression:

Brute force
    ↓
Observe repeated work
    ↓
Exploit ordering / locality
    ↓
Maintain state
    ↓
Establish invariant
    ↓
Process each element a bounded number of times
    ↓
Optimal or near-optimal solution

That reasoning pattern appears far beyond arrays.

It is fundamental to:

streaming systems,
distributed processing,
caching,
database indexing,
search systems,
machine learning pipelines,
real-time analytics.

28. Final Staff-Level Checklist

Before submitting an array solution, ask:

Requirements

Did I clarify the input?
Is mutation allowed?
Are duplicates possible?
Can values be negative?
What happens if no answer exists?

Algorithm

Is the input sorted?
Can I use two pointers?
Is this a sliding-window problem?
Would a prefix sum help?
Is there a monotonic predicate?
Can I maintain a running best?
Can I partition in place?

Correctness

What is my invariant?
Why is it preserved?
Why can I safely discard candidates?

Complexity

Time?
Auxiliary space?
Can repeated work be eliminated?
Is preprocessing worthwhile?

Engineering

What happens at very large scale?
What if the input is a stream?
Is memory or latency the dominant constraint?
What trade-off does my solution make?

Final Takeaway

The Staff-level array skill is not:

“I know many array problems.”

It is:

“I can look at an unfamiliar array problem, identify its structure, choose an appropriate invariant, eliminate repeated work, and explain the trade-offs clearly.”

That is the real transition from coding problem solver to Staff-level engineer.

Up Next

The natural progression is to move from arrays into strings, where many of the same ideas reappear through:

character frequency,
hashing,
substring search,
parsing,
palindrome reasoning,
and representation-aware algorithms.