Problems

Master the prefix sum pattern by solving these carefully selected problems. Each problem demonstrates a different aspect of prefix sums, from basic cumulative sums to advanced 2D matrix operations and modular arithmetic.

For a theoretical overview, check out the Prefix Sum Guide or the Code Templates.

Easy Problems

1. Running Sum of 1d Array

LeetCode 1480

Brief: Given an array nums, return an array where each element is the sum of the array so far.
Why this pattern?: This is the textbook definition of a Prefix Sum array.
Key Insight: You can do this in-place (
O(1)
space) by updating the array as you iterate: nums[i] += nums[i-1].

Visual:

  graph LR
    subgraph Input
    I1[1] --> I2[2] --> I3[3] --> I4[4]
    end
    subgraph Running_Sum
    R1[1] --> R2[3] --> R3[6] --> R4[10]
    end
    I2 -.->|+1| R2
    I3 -.->|+3| R3
    I4 -.->|+6| R4
    style R4 fill:#f9d,stroke:#333

JavaScript:

var runningSum = function(nums) {
    for (let i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1];
    }
    return nums;
};

Python:

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        for i in range(1, len(nums)):
            nums[i] += nums[i - 1]
        return nums

Java:

class Solution {
    public int[] runningSum(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
}

C++:

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++i) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
};

Go:

func runningSum(nums []int) []int {
    for i := 1; i < len(nums); i++ {
        nums[i] += nums[i-1]
    }
    return nums
}

Ruby:

# @param {Integer[]} nums
# @return {Integer[]}
def running_sum(nums)
  (1...nums.length).each do |i|
    nums[i] += nums[i - 1]
  end
  nums
end

2. Find Pivot Index

LeetCode 724

Brief: Find the index where the sum of numbers to the left equals the sum of numbers to the right.
Why this pattern?: The condition “sum of left” implies we need a quick way to know the cumulative sum at any point.
Key Insight: Calculate totalSum first. Iterate keeping leftSum. Pivot logic is leftSum == totalSum - leftSum - nums[i].

Visual:

  graph TD
    subgraph Array
    A[1]
    B[7]
    P[3 Pivot]
    C[6]
    D[5]
    E[6]
    end
    LeftSum[Left Sum: 8]
    RightSum[Right Sum: 17]

    LeftSum -.-> P
    P -.-> RightSum

    style P fill:#f96,stroke:#333
    style LeftSum fill:#fff,stroke:#333
    style RightSum fill:#fff,stroke:#333

JavaScript:

var pivotIndex = function(nums) {
    const totalSum = nums.reduce((a, b) => a + b, 0);
    let leftSum = 0;

    for (let i = 0; i < nums.length; i++) {
        if (leftSum === totalSum - leftSum - nums[i]) {
            return i;
        }
        leftSum += nums[i];
    }
    return -1;
};

Python:

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        left_sum = 0
        for i, num in enumerate(nums):
            if left_sum == total_sum - left_sum - num:
                return i
            left_sum += num
        return -1

Java:

class Solution {
    public int pivotIndex(int[] nums) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;

        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (leftSum == totalSum - leftSum - nums[i]) {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }
}

C++:

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        int leftSum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (leftSum == totalSum - leftSum - nums[i]) {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }
};

Go:

func pivotIndex(nums []int) int {
    totalSum := 0
    for _, num := range nums {
        totalSum += num
    }
    leftSum := 0
    for i, num := range nums {
        if leftSum == totalSum - leftSum - num {
            return i
        }
        leftSum += num
    }
    return -1
}

Ruby:

# @param {Integer[]} nums
# @return {Integer}
def pivot_index(nums)
  total_sum = nums.sum
  left_sum = 0

  nums.each_with_index do |num, i|
    if left_sum == total_sum - left_sum - num
      return i
    end
    left_sum += num
  end
  -1
end

Medium Problems

3. Subarray Sum Equals K

LeetCode 560

Brief: Find the total number of continuous subarrays whose sum equals k.
Why this pattern?: Use a Hash Map to count how many times we have seen a required prefix sum.
Key Insight: Prefix[i] = Prefix[j] - k. Store { prefixSum: count } in a map.

Visual:

  graph LR
    Start[0] -->|sum=3| Pj[Pj=3]
    Pj -->|k=7| Pi[Pi=10]

    Pj -.->|Stored in Map| Map[Hash Map]
    Map -.->|Count increments| Count[Matches Found]

    style Pi fill:#aaf,stroke:#333
    style Pj fill:#f9d,stroke:#333

JavaScript:

var subarraySum = function(nums, k) {
    const map = new Map();
    map.set(0, 1);
    let sum = 0;
    let count = 0;

    for (let num of nums) {
        sum += num;
        if (map.has(sum - k)) {
            count += map.get(sum - k);
        }
        map.set(sum, (map.get(sum) || 0) + 1);
    }
    return count;
};

Python:

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        current_sum = 0
        prefix_counts = {0: 1}

        for num in nums:
            current_sum += num
            if current_sum - k in prefix_counts:
                count += prefix_counts[current_sum - k]

            prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1

        return count

Java:

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0;
        int count = 0;

        for (int num : nums) {
            sum += num;
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

C++:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        map[0] = 1;
        int sum = 0;
        int count = 0;

        for (int num : nums) {
            sum += num;
            if (map.find(sum - k) != map.end()) {
                count += map[sum - k];
            }
            map[sum]++;
        }
        return count;
    }
};

Go:

func subarraySum(nums []int, k int) int {
    m := map[int]int{0: 1}
    sum := 0
    count := 0

    for _, num := range nums {
        sum += num
        if val, ok := m[sum-k]; ok {
            count += val
        }
        m[sum]++
    }
    return count
}

Ruby:

# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer}
def subarray_sum(nums, k)
  count = 0
  sum = 0
  map = { 0 => 1 }

  nums.each do |num|
    sum += num
    count += map[sum - k] if map.key?(sum - k)
    map[sum] = (map[sum] || 0) + 1
  end
  count
end

4. Subarray Sums Divisible by K

LeetCode 974

Brief: Count subarrays divisible by k.
Why this pattern?: Similar to the above, but with modular arithmetic.
Key Insight: (P[j] - P[i]) % k == 0 implies P[j] % k == P[i] % k.

Visual:

  graph TD
    A[Prefix P_i = 7] -->|Mod 5| M1[Rem: 2]
    B[Prefix P_j = 12] -->|Mod 5| M2[Rem: 2]

    M1 --- M2
    M1 -.->|Same Remainder| SameResult[Divisible by K]

    style M1 fill:#aaf,stroke:#333
    style M2 fill:#aaf,stroke:#333

JavaScript:

var subarraysDivByK = function(nums, k) {
    const map = new Map();
    map.set(0, 1);
    let sum = 0;
    let count = 0;

    for (let num of nums) {
        sum += num;
        let mod = ((sum % k) + k) % k; // Handle negative
        if (map.has(mod)) {
            count += map.get(mod);
        }
        map.set(mod, (map.get(mod) || 0) + 1);
    }
    return count;
};

Python:

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        prefix_counts = {0: 1}
        current_sum = 0
        count = 0

        for num in nums:
            current_sum += num
            mod = current_sum % k # Python handles negative mod correctly for valid remainders usually, but purely arithmetic
            # To be safe and consistent with math definitions:
            mod = (mod + k) % k

            if mod in prefix_counts:
                count += prefix_counts[mod]
            prefix_counts[mod] = prefix_counts.get(mod, 0) + 1

        return count

Java:

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0;
        int count = 0;

        for (int num : nums) {
            sum += num;
            int mod = ((sum % k) + k) % k;
            if (map.containsKey(mod)) {
                count += map.get(mod);
            }
            map.put(mod, map.getOrDefault(mod, 0) + 1);
        }
        return count;
    }
}

C++:

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        map[0] = 1;
        int sum = 0;
        int count = 0;

        for (int num : nums) {
            sum += num;
            int mod = ((sum % k) + k) % k;
            if (map.count(mod)) {
                count += map[mod];
            }
            map[mod]++;
        }
        return count;
    }
};

Go:

func subarraysDivByK(nums []int, k int) int {
    m := map[int]int{0: 1}
    sum := 0
    count := 0

    for _, num := range nums {
        sum += num
        mod := ((sum % k) + k) % k
        if val, ok := m[mod]; ok {
            count += val
        }
        m[mod]++
    }
    return count
}

Ruby:

# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer}
def subarrays_div_by_k(nums, k)
  map = { 0 => 1 }
  sum = 0
  count = 0

  nums.each do |num|
    sum += num
    mod = ((sum % k) + k) % k
    count += map[mod] if map.key?(mod)
    map[mod] = (map[mod] || 0) + 1
  end
  count
end

Recommended Study Order

Basics: Start with Find Pivot Index (LC 724) to get comfortable with the concept of left/right sums.
Core Application: Solve Range Sum Query - Immutable (LC 303) to implement the standard class.
The “Aha” Moment: Tackle Subarray Sum Equals K (LC 560). This is the most common interview pattern.
Advanced: Attempt Range Sum Query 2D - Immutable (LC 304) to expand the concept to matrices.

Pro Tip: Whenever you see “Subarray Sum”, your first thought should be Prefix Sum. If the array contains negative numbers, Sliding Window will not work, making Prefix Sum the only viable linear solution.