Prefix Sum Interview Problems: Patterns, Tricks & Pitfalls

public class PrefixSumFoundation {

    /**
     * Builds a 1-indexed prefix sum array.
     * prefix[i] = sum of scores[0..i-1]
     * prefix[0] = 0  (sentinel — eliminates left-edge special cases)
     */
    static int[] buildPrefixSum(int[] scores) {
        int n = scores.length;
        int[] prefix = new int[n + 1];  // one extra slot for the sentinel at index 0
        prefix[0] = 0;

        for (int i = 1; i <= n; i++) {
            // Each cell = previous prefix total + the current element
            prefix[i] = prefix[i - 1] + scores[i - 1];
        }
        return prefix;
    }

    /**
     * Returns the sum of scores[left..right] (0-indexed, inclusive)
     * using the prebuilt prefix array in O(1) time.
     */
    static int rangeSum(int[] prefix, int left, int right) {
        // Shift to 1-indexed: prefix[right+1] - prefix[left]
        return prefix[right + 1] - prefix[left];
    }

    public static void main(String[] args) {
        // Monthly sales figures for a small store
        int[] monthlySales = {120, 340, 210, 480, 95, 310, 275};

        int[] prefix = buildPrefixSum(monthlySales);

        System.out.println("Prefix array: ");
        for (int val : prefix) {
            System.out.print(val + "  ");
        }
        System.out.println();

        // Q1: What were total sales in months 1–3? (0-indexed: indices 0 to 2)
        int q1 = rangeSum(prefix, 0, 2);
        System.out.println("Sales months 1-3: " + q1);   // 120+340+210 = 670

        // Q2: What were total sales in months 3–6? (0-indexed: indices 2 to 5)
        int q2 = rangeSum(prefix, 2, 5);
        System.out.println("Sales months 3-6: " + q2);   // 210+480+95+310 = 1095

        // Q3: Full array sum — just ask for index 0 to last
        int total = rangeSum(prefix, 0, monthlySales.length - 1);
        System.out.println("Total annual sales: " + total); // 1830
    }
}

import java.util.HashMap;
import java.util.Map;

public class SubarraySumEqualsK {

    /**
     * Counts contiguous subarrays whose elements sum to exactly targetSum.
     * Works with negative numbers too — sliding window does NOT handle that.
     *
     * Key insight:
     *   subarray(i..j) = targetSum
     *   ⟹ runningPrefix[j] - runningPrefix[i-1] = targetSum
     *   ⟹ runningPrefix[i-1] = runningPrefix[j] - targetSum
     *
     * So we just need to know: how many previous prefix sums equal (current - target)?
     */
    static int countSubarraysWithSum(int[] temperatures, int targetSum) {
        // Maps each prefix sum value → how many times we've seen it
        Map<Integer, Integer> prefixSumCount = new HashMap<>();

        // Seed the map: a prefix of 0 has been seen once (the empty prefix before index 0)
        prefixSumCount.put(0, 1);

        int runningTotal = 0;
        int validSubarrayCount = 0;

        for (int dailyReading : temperatures) {
            runningTotal += dailyReading;  // extend prefix sum one element to the right

            // If (runningTotal - targetSum) exists as a previous prefix,
            // each occurrence means a valid subarray ends exactly HERE.
            int needed = runningTotal - targetSum;
            validSubarrayCount += prefixSumCount.getOrDefault(needed, 0);

            // Record this prefix sum so future iterations can use it
            prefixSumCount.put(runningTotal, prefixSumCount.getOrDefault(runningTotal, 0) + 1);
        }

        return validSubarrayCount;
    }

    public static void main(String[] args) {
        // Temperature deltas from average — can be negative, zero, or positive
        int[] temperatureDeltas = {3, -1, 2, 1, -2, 4, -3, 2};
        int targetSum = 3;

        int result = countSubarraysWithSum(temperatureDeltas, targetSum);
        System.out.println("Number of subarrays summing to " + targetSum + ": " + result);
        // Subarrays: [3], [3,-1,2,1,-2,4,-3,2] no... let's trace manually
        // [3] = 3 ✓
        // [-1,2,1,-2,4,-3,2] = 3 ✓
        // [2,1] = 3 ✓
        // [1,-2,4] = 3 ✓
        // [-2,4,-3,2] = 1, no
        // So 4 valid subarrays

        // Edge case: array with zeros — many subarrays can sum to 0
        int[] withZeros = {0, 0, 0};
        System.out.println("Subarrays summing to 0 in [0,0,0]: " + countSubarraysWithSum(withZeros, 0));
        // [0], [0], [0], [0,0], [0,0], [0,0,0] = 6
    }
}

public class Grid2DPrefixSum {

    /**
     * Builds a 2D prefix sum table (1-indexed with a zero-padded border).
     * prefix[r][c] = sum of all grid values in the rectangle (0,0) → (r-1, c-1)
     */
    static int[][] build2DPrefix(int[][] heatMap) {
        int rows = heatMap.length;
        int cols = heatMap[0].length;

        // +1 for the sentinel row and column (all zeros)
        int[][] prefix = new int[rows + 1][cols + 1];

        for (int r = 1; r <= rows; r++) {
            for (int c = 1; c <= cols; c++) {
                prefix[r][c] = heatMap[r - 1][c - 1]   // current cell
                             + prefix[r - 1][c]          // sum of column above
                             + prefix[r][c - 1]          // sum of row to the left
                             - prefix[r - 1][c - 1];     // remove the corner counted twice
            }
        }
        return prefix;
    }

    /**
     * Returns the sum of a rectangular region.
     * All coordinates are 0-indexed (matching the original grid).
     */
    static int rectangleSum(int[][] prefix, int r1, int c1, int r2, int c2) {
        // Convert to 1-indexed for the prefix table
        return prefix[r2 + 1][c2 + 1]
             - prefix[r1][c2 + 1]      // strip above our rectangle
             - prefix[r2 + 1][c1]      // strip to the left of our rectangle
             + prefix[r1][c1];         // add corner back (was subtracted twice)
    }

    public static void main(String[] args) {
        // Simulated heat sensor readings on a 4x4 grid
        int[][] heatMap = {
            {2,  4,  6,  1},
            {5,  3,  8,  2},
            {1,  7,  4,  9},
            {3,  2,  5,  6}
        };

        int[][] prefix = build2DPrefix(heatMap);

        // Query 1: top-left 2x2 subgrid (rows 0-1, cols 0-1)
        int topLeft = rectangleSum(prefix, 0, 0, 1, 1);
        System.out.println("Top-left 2x2 sum: " + topLeft);  // 2+4+5+3 = 14

        // Query 2: bottom-right 2x2 subgrid (rows 2-3, cols 2-3)
        int bottomRight = rectangleSum(prefix, 2, 2, 3, 3);
        System.out.println("Bottom-right 2x2 sum: " + bottomRight);  // 4+9+5+6 = 24

        // Query 3: entire grid
        int total = rectangleSum(prefix, 0, 0, 3, 3);
        System.out.println("Full grid sum: " + total);  // all 16 values = 68
    }
}

import java.util.HashMap;
import java.util.Map;

public class PrefixSumDisguises {

    // ─── DISGUISE 1: Equal 0s and 1s ────────────────────────────────────────────
    /**
     * Finds the length of the longest subarray with equal 0s and 1s.
     * Trick: replace 0 → -1, then find longest subarray summing to 0.
     * A prefix sum repeating means the subarray between those two indices sums to 0.
     */
    static int longestEqualZeroOneSubarray(int[] binarySignals) {
        Map<Integer, Integer> firstSeenAt = new HashMap<>();
        firstSeenAt.put(0, -1);  // prefix sum of 0 was 'seen' before index 0 starts

        int runningTotal = 0;
        int longestLength = 0;

        for (int i = 0; i < binarySignals.length; i++) {
            // Transform: 0 → -1, 1 stays 1
            runningTotal += (binarySignals[i] == 0) ? -1 : 1;

            if (firstSeenAt.containsKey(runningTotal)) {
                // Same prefix sum seen before → the subarray between then and now sums to 0
                longestLength = Math.max(longestLength, i - firstSeenAt.get(runningTotal));
            } else {
                // Only store the FIRST occurrence — we want the longest span possible
                firstSeenAt.put(runningTotal, i);
            }
        }
        return longestLength;
    }

    // ─── DISGUISE 2: Difference Array for Range Updates ─────────────────────────
    /**
     * You have 'numDays' days, all starting at temperature 0.
     * Each event raises temperature by 'delta' across a range [start, end].
     * Apply all events efficiently, then read the final temperatures.
     *
     * With a difference array: each event is O(1). Final prefix sum is one O(n) pass.
     */
    static int[] applyTemperatureEvents(int numDays, int[][] events) {
        int[] diff = new int[numDays + 1]; // +1 to safely write past the last index

        for (int[] event : events) {
            int startDay = event[0];
            int endDay   = event[1];
            int delta    = event[2];

            diff[startDay] += delta;       // start raising here
            diff[endDay + 1] -= delta;     // stop raising after endDay
        }

        // One prefix sum pass converts the difference array into actual temperatures
        int[] temperature = new int[numDays];
        int running = 0;
        for (int day = 0; day < numDays; day++) {
            running += diff[day];
            temperature[day] = running;
        }
        return temperature;
    }

    public static void main(String[] args) {
        // Disguise 1 demo
        int[] binarySignals = {0, 1, 0, 0, 1, 1, 0};
        System.out.println("Longest equal-0s-and-1s subarray: "
            + longestEqualZeroOneSubarray(binarySignals));  // [0,1,0,0,1,1] = length 6

        // Disguise 2 demo: 7 days, three overlapping heating events
        int numDays = 7;
        int[][] heatingEvents = {
            {0, 3, 5},   // days 0-3: +5 degrees
            {1, 5, 3},   // days 1-5: +3 degrees
            {3, 6, 2}    // days 3-6: +2 degrees
        };
        int[] finalTemps = applyTemperatureEvents(numDays, heatingEvents);
        System.out.print("Daily temperatures: ");
        for (int temp : finalTemps) {
            System.out.print(temp + " ");
        }
        System.out.println();
        // Day 0: +5        = 5
        // Day 1: +5+3      = 8
        // Day 2: +5+3      = 8
        // Day 3: +5+3+2    = 10
        // Day 4: +3+2      = 5
        // Day 5: +3+2      = 5
        // Day 6: +2        = 2
    }
}