The prefix/suffix refers to computing aggregated information for each element. A prefix value at position i represents a computation involving elements from the start of the array up to position i.
Prefix/Suffix Sums involves preprocessing an array to calculate cumulative sums, enabling O(1) queries for subarray sums later on.
Time Complexity O(1)
Space Complexity O(1|n)
If we can overwrite the array, we don’t need extra n space.
func genPrefixSum(arr []int) []int {
n := len(arr)
prefix := make([]int, n+1)
for i := 1; i < n+1; i++ {
// prefix[i] is exclusive of index i in arr
prefix[i] = prefix[i-1] + arr[i-1]
}
return prefix
}
func rangeSum(prefix []int, L, R int) int {
// the input L and R are inclusive
L++ // turn it to 1-index based
R++ // turn it to 1-index based
return prefix[R] - prefix[L-1]
}
Last review: Aug 1, 2025 Next review: Your speed was too slow for recalling the approach.
O(1)O(n)type NumArray struct {
prefix []int
}
func Constructor(nums []int) NumArray {
n := len(nums)
prefix := make([]int, n+1)
for i := 1; i <= n; i++ {
prefix[i] = prefix[i-1] + nums[i-1]
}
return NumArray{
prefix: prefix,
}
}
func (this *NumArray) SumRange(left int, right int) int {
left++
right++
return this.prefix[right] - this.prefix[left-1]
}
https://leetcode.com/problems/product-of-array-except-self
Last review: Aug 18, 2025 Next review: I was better, draw down on a paper and practice two approaches again.
Traverse every exception point and calculate their product.
O(n^2)