DEV Community

Dev Cookies
Dev Cookies

Posted on

🚀 FAANG Coding Patterns Series – Day 3

Pattern: Prefix Sum & Difference Arrays

🔹 Why This Pattern?

  • Many problems involve subarray sums, ranges, or updates.
  • Brute force (O(n²)) → Prefix Sum / Difference Array reduces it to O(n).

  • Common for:

    • Subarray sum problems (K-sum, max sum, divisible sum).
    • Interval addition queries.
    • String prefix counts.
    • Range updates (especially in competitive coding).

🔥 Sub-Patterns

1️⃣ Classic Prefix Sum (Static Queries)

Example: Range Sum Query – Immutable (Amazon) 

class NumArray {
    private int[] prefix;

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

    public int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}
Enter fullscreen mode Exit fullscreen mode

Complexity:

  • Preprocessing: O(n)
  • Query: O(1)

2️⃣ Prefix Sum for Subarray Problems

Example: Subarray Sum Equals K (Google, Amazon) 

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int prefix = 0, count = 0;
        for (int num : nums) {
            prefix += num;
            if (map.containsKey(prefix - k)) {
                count += map.get(prefix - k);
            }
            map.put(prefix, map.getOrDefault(prefix, 0) + 1);
        }
        return count;
    }
}
Enter fullscreen mode Exit fullscreen mode

💡 Trick: Store prefixSum[i] counts in HashMap.

3️⃣ Difference Array (Efficient Range Updates)

Example: Corporate Flight Bookings (LeetCode 1109, Amazon/Google) 

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] diff = new int[n + 1];
        for (int[] b : bookings) {
            diff[b[0] - 1] += b[1];
            diff[b[1]] -= b[1];
        }
        int[] result = new int[n];
        result[0] = diff[0];
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] + diff[i];
        }
        return result;
    }
}
Enter fullscreen mode Exit fullscreen mode

Idea:

  • Use difference array for range increments in O(1).
  • Then take prefix sum at the end.

4️⃣ 2D Prefix Sum (Matrix Problems)

Example: Range Sum Query 2D (Google/Microsoft) 

class NumMatrix {
    private int[][] prefix;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        prefix = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = matrix[i - 1][j - 1] 
                             + prefix[i - 1][j] 
                             + prefix[i][j - 1] 
                             - prefix[i - 1][j - 1];
            }
        }
    }

    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];
    }
}
Enter fullscreen mode Exit fullscreen mode

📌 Flagship Problems by Company

Problem Company Pattern Difficulty
Subarray Sum Equals K Google, Amazon Prefix Sum + HashMap Medium
Range Sum Query Immutable Amazon Prefix Sum Easy
Corporate Flight Bookings Google, Amazon Difference Array Medium
Car Pooling Amazon, Uber Difference Array Medium
Range Sum Query 2D Immutable Google, Microsoft 2D Prefix Medium
Maximum Size Subarray Sum = k Google Prefix + HashMap Medium
Count Subarrays Divisible by K Amazon Prefix + Mod Medium

🧠 Quick “Pattern Recognition” Checklist

  • Querying sum of subarray multiple times? → Prefix sum.
  • Counting number of subarrays with condition? → Prefix sum + HashMap.
  • Multiple range updates? → Difference array.
  • Matrix queries? → 2D prefix sum.

🎯 Practice Set (Homework with Hints)

  1. Maximum Size Subarray Sum = K (Google) – Use prefix sum + earliest index.
  2. Count Subarrays Divisible by K (Amazon) – Store prefix % k in map.
  3. Car Pooling (Uber/Amazon) – Difference array + prefix check capacity.
  4. Range Addition (Google) – Classic diff array.
  5. 2D Range Sum Query (Google) – Build prefix 2D.

🔑 Key Takeaway

Prefix sums & difference arrays transform problems from brute-force to linear time.
Whenever you see subarray, interval, or range update/query problems → this is your go-to pattern.

📅 Coming Up – Day 4:
👉 Sliding Window + Variable Window Sizes (super hot in FAANG interviews).

Top comments (0)