Arrays and prefix computations

Explanation

Arrays give direct positional access. Prefix sums store the sum before each boundary, including boundary zero, so a range [a,b) is prefix[b]-prefix[a]. A rotation changes positions but should not change membership or mutate the caller’s input.

Write down inclusive and exclusive boundaries before coding. Test an empty interval, an interval touching the last element, and a rotation equal to the array length.

Runnable worked example

def solve(values):
    result = [0]
    for value in values:
        result.append(result[-1] + value)
    return result

assert solve([2, -1, 3]) == [0, 2, 1, 4]

Expected result: [0, 2, 1, 4].

The initial zero makes empty prefixes and half-open intervals uniform. O(n) time and output space.

Common mistakes

Do not confuse the final element index n-1 with the final boundary n. Avoid slicing assumptions that fail at zero.

Guided practice

Trace the example by hand and name the invariant after each update. Add a boundary case that would break a plausible incorrect implementation. Explain termination and the largest working structure before claiming a complexity bound.

Independent practice

• Build prefix sums
• Answer half-open range queries
• Rotate an array without mutation

Recap

Use indices and half-open intervals to transform arrays safely. Contracts, invariants, boundary tests, and complexity reasoning work together. The Python and JavaScript tracks cover corresponding algorithmic concepts with language-specific implementations and independent progress.