Array / Slice

O(1) access / O(n) insert / O(n)

Contiguous storage with O(1) index access; prefix sums turn range queries into subtraction.

How to recognise it

  • Repeated range-sum or range-count queries → prefix sum
  • In-place rewrite of an array → read/write indices
  • Matrix traversal → direction arrays or layer-by-layer bounds
Go
// Prefix sum: sum of a[l..r] inclusive
func buildPrefix(a []int) []int {
    pre := make([]int, len(a)+1)
    for i, v := range a {
        pre[i+1] = pre[i] + v
    }
    return pre
}

func rangeSum(pre []int, l, r int) int {
    return pre[r+1] - pre[l]
}

// Subarray sum equals k: prefix sum + hash map (LC 560)
func subarraySum(nums []int, k int) int {
    count, sum := 0, 0
    seen := map[int]int{0: 1}
    for _, v := range nums {
        sum += v
        count += seen[sum-k]
        seen[sum]++
    }
    return count
}

// Difference array: add delta to every a[l..r]
func applyRangeAdds(n int, ops [][3]int) []int { // ops: {l, r, delta}
    diff := make([]int, n+1)
    for _, op := range ops {
        diff[op[0]] += op[2]
        diff[op[1]+1] -= op[2]
    }
    res := make([]int, n)
    run := 0
    for i := 0; i < n; i++ {
        run += diff[i]
        res[i] = run
    }
    return res
}

Common variants

  • Prefix sum → pre[i+1] = pre[i] + a[i]; sum(l..r) = pre[r+1] - pre[l]
  • Prefix sum + hash map → Count subarrays with sum k: look up pre - k seen so far
  • Difference array → Many range increments → +1 at l, -1 at r+1, then prefix-sum once
  • Go slice aliasing → append may share the backing array; copy before mutating

Classic problems

← All algorithms