🧮 Mastering Prefix Sum in Java – The Ultimate Guide with Real Examples

When it comes to optimizing range queries and speeding up subarray calculations, Prefix Sum is one of the most efficient and widely used techniques. Whether you’re solving problems on arrays, matrices, or strings — this concept can simplify things drastically.

Let’s dive into the idea of prefix sum with Java code, intuition, and interview-level examples.

🔍 What is a Prefix Sum?

A Prefix Sum is a running total of values in an array. It allows you to compute the sum of any subarray in constant time after a linear-time preprocessing step.

🧠 Formula

For an array arr[], the prefix sum array prefix[] is defined as:

prefix[i] = prefix[i - 1] + arr[i]

To get the sum of elements from index l to r:

sum = prefix[r] - prefix[l - 1]

(Take care of index 0 edge case!)

🧪 Java Implementation

✅ Basic Prefix Sum of Array

public int[] computePrefixSum(int[] arr) {
    int[] prefix = new int[arr.length];
    prefix[0] = arr[0];

    for (int i = 1; i < arr.length; i++) {
        prefix[i] = prefix[i - 1] + arr[i];
    }
    return prefix;
}

📘 Example 1: Range Sum Query (Immutable)

🔧 Problem:

Preprocess the array so you can get the sum of any subarray [i...j] in O(1) time.

public class RangeSumQuery {
    int[] prefix;

    public RangeSumQuery(int[] nums) {
        prefix = new int[nums.length];
        prefix[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
        return i == 0 ? prefix[j] : prefix[j] - prefix[i - 1];
    }
}

📘 Example 2: Check Subarray Sum Equals K

🔧 Problem:

Count the number of subarrays with sum = K.

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    int count = 0, sum = 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;
}

🧠 This uses prefix sum + hashmap for efficient counting.

📘 Example 3: 2D Prefix Sum (Matrix)

🔧 Problem:

Efficiently compute the sum of a submatrix in a 2D grid.

public class NumMatrix {
    int[][] prefix;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        prefix = new int[m + 1][n + 1];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i + 1][j + 1] = matrix[i][j] 
                    + prefix[i + 1][j] 
                    + prefix[i][j + 1] 
                    - prefix[i][j];
            }
        }
    }

    public int sumRegion(int r1, int c1, int r2, int c2) {
        return prefix[r2 + 1][c2 + 1] 
             - prefix[r1][c2 + 1] 
             - prefix[r2 + 1][c1] 
             + prefix[r1][c1];
    }
}

📘 Example 4: Maximum Sum Subarray (Kadane’s Algorithm vs. Prefix Sum)

You can use prefix sum to brute-force all subarrays:

public int maxSubarraySum(int[] nums) {
    int max = Integer.MIN_VALUE;
    int[] prefix = new int[nums.length];
    prefix[0] = nums[0];

    for (int i = 1; i < nums.length; i++) {
        prefix[i] = prefix[i - 1] + nums[i];
    }

    for (int i = 0; i < nums.length; i++) {
        for (int j = i; j < nums.length; j++) {
            int sum = i == 0 ? prefix[j] : prefix[j] - prefix[i - 1];
            max = Math.max(max, sum);
        }
    }
    return max;
}

⏱ Time: O(n²) — can be improved to O(n) using Kadane's Algorithm.

📘 Example 5: Binary String with Equal 0s and 1s

Convert '0' to -1 and use prefix sum to find longest balanced subarray.

public int findMaxLength(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    int max = 0, sum = 0;

    for (int i = 0; i < nums.length; i++) {
        sum += (nums[i] == 0) ? -1 : 1;
        if (map.containsKey(sum)) {
            max = Math.max(max, i - map.get(sum));
        } else {
            map.put(sum, i);
        }
    }
    return max;
}

✅ Real-World Use Cases

Subarray sum problems
Histogram and matrix-based queries
Financial transactions or running totals
Game score calculations
Frequency and cumulative distributions

🎯 Key Takeaways

Concept	Usage
1D Prefix Sum	Quick range queries
2D Prefix Sum	Matrix-based region queries
HashMap + Prefix Sum	Count subarrays efficiently
Preprocessing	O(n), then O(1) for queries