Prefix Sums & Difference Arrays — Interview Preparation¶

Junior Questions¶

Middle Questions¶

Senior Questions¶

Professional Questions¶

Coding Challenge (3 Languages)¶

Challenge: Subarray Sum Equals K¶

Given an integer array nums and an integer k, return the total number of contiguous subarrays whose sum equals k. The array can contain negative numbers, so sliding window does not apply. Target time complexity: O(n).

Example: nums = [1, 1, 1], k = 2 -> output 2 ([1,1] at indices [0,1] and [1,2]).

Example: nums = [1, 2, 3], k = 3 -> output 2 ([3] and [1,2]).

Go¶

package main

import "fmt"

// SubarraySumK returns the number of contiguous subarrays summing to k.
// Approach: prefix sum + hash map of prefix-sum counts.
// Time: O(n). Space: O(n).
func SubarraySumK(nums []int, k int) int {
    // seen[s] = number of prefix-sum values that equal s so far.
    // Start with seen[0] = 1 to count the empty prefix.
    seen := map[int]int{0: 1}
    running := 0
    count := 0
    for _, v := range nums {
        running += v
        // We need: running - prefix_at_l == k, so prefix_at_l == running - k.
        if c, ok := seen[running-k]; ok {
            count += c
        }
        seen[running]++
    }
    return count
}

func main() {
    fmt.Println(SubarraySumK([]int{1, 1, 1}, 2))     // 2
    fmt.Println(SubarraySumK([]int{1, 2, 3}, 3))     // 2
    fmt.Println(SubarraySumK([]int{3, 4, 7, 2, -3, 1, 4, 2}, 7)) // 4
}

Java¶

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

public class Solution {
    /**
     * Number of contiguous subarrays summing to k.
     * Time: O(n). Space: O(n).
     */
    public static int subarraySumK(int[] nums, int k) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, 1); // empty prefix counts once
        int running = 0;
        int count = 0;
        for (int v : nums) {
            running += v;
            count += seen.getOrDefault(running - k, 0);
            seen.merge(running, 1, Integer::sum);
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(subarraySumK(new int[]{1, 1, 1}, 2));                         // 2
        System.out.println(subarraySumK(new int[]{1, 2, 3}, 3));                         // 2
        System.out.println(subarraySumK(new int[]{3, 4, 7, 2, -3, 1, 4, 2}, 7));         // 4
    }
}

Python¶

from collections import defaultdict
from typing import List


def subarray_sum_k(nums: List[int], k: int) -> int:
    """Number of contiguous subarrays summing to k.

    Time: O(n). Space: O(n).
    Works with negatives because we never need monotonicity.
    """
    seen = defaultdict(int)
    seen[0] = 1  # empty prefix
    running = 0
    count = 0
    for v in nums:
        running += v
        count += seen[running - k]
        seen[running] += 1
    return count


if __name__ == "__main__":
    print(subarray_sum_k([1, 1, 1], 2))                       # 2
    print(subarray_sum_k([1, 2, 3], 3))                       # 2
    print(subarray_sum_k([3, 4, 7, 2, -3, 1, 4, 2], 7))       # 4

Discussion Notes — what the interviewer is listening for¶

• Why a hash map? Because we need to count how many prior prefix sums equal running - k. Without the map, we would scan the prefix array per element — O(n^2).
• Why seen[0] = 1 initially? It accounts for subarrays that start at index 0 (where the "left prefix" is the empty prefix, value 0).
• Why not sliding window? Sliding window requires the running sum to behave monotonically when expanding/shrinking the window. Negative numbers break this monotonicity.
• Edge cases to mention: empty array (return 0), single-element array equal to k (return 1), all-zero array with k = 0 (n choose 2 plus n subarrays).
• Space: O(n) for the hash map. Cannot be reduced without losing correctness for negatives.
• Follow-up question often asked: "Now find the longest subarray with sum k." Same map, store the first-seen index of each prefix sum and track i - seen[running - k].