Prefix Sum and Hash Map

1. Subarray Sum Equals K Medium

Problem

Given an array of integers and a target k, return the number of contiguous subarrays whose sum equals k. Values may be negative.

Approach

• Two constraints kill the window at once. The target is an exact match, and values may be negative. Say both, then move on.
• Keep a running prefix. At each index, count the earlier prefixes equal to running - k. That count is the number of subarrays ending here with sum k.
• The map counts how often each prefix appears. The same value can appear many times, and each one is a distinct subarray.

Solution

public static class SubarraySum
{
    /// <summary>Counts contiguous subarrays of nums summing to exactly k.</summary>
    /// <param name="nums">Integers. Negative values are allowed.</param>
    /// <param name="k">The exact target sum.</param>
    /// <returns>The number of qualifying subarrays.</returns>
    /// <example>Count([1, 2, 3], 3) returns 2.</example>
    public static int Count(int[] nums, int k)
    {
        // prefix value -> how many times it has been seen so far.
        // The empty prefix has sum 0 and is seen 1 time before any element.
        // It lets a subarray that starts at index 0 be counted.
        var seen = new Dictionary<int, int> { [0] = 1 };

        int running = 0;                 // 0: sum of no elements yet
        int count = 0;                   // 0: no subarrays found yet

        // Invariant: running = sum of nums up to and including value.
        // seen holds all prefixes that end before value.
        foreach (int value in nums)
        {
            running += value;
            // Every earlier prefix equal to (running - k) marks the start of a
            // subarray ending here whose sum is exactly k. Missing key reads 0.
            count += seen.GetValueOrDefault(running - k);
            // Record this prefix AFTER the lookup. +1: seen once more.
            seen[running] = seen.GetValueOrDefault(running) + 1;
        }
        return count;
    }
}

Walkthrough

nums = [1, 2, 3], k = 3:

1. value 1. running = 1. Look up 1 − 3 = −2. Found 0 times, so count = 0. seen is now {0:1, 1:1}.
2. value 2. running = 3. Look up 3 − 3 = 0. Found 1 time, so count = 1. seen is now {0:1, 1:1, 3:1}.
3. value 3. running = 6. Look up 6 − 3 = 3. Found 1 time, so count = 2. seen is now {0:1, 1:1, 3:1, 6:1}.

The two subarrays are [1, 2] and [3]. Notice that the seed [0] = 1 is what found [1, 2].

Reading the figure. Each box is one turn of the loop. The first lines show the lookup for running - k. The row of small cells is the seen map after the step. Green marks the key the lookup found. Amber marks the new prefix just recorded. Notice the lookup always happens before the amber key is added.

The sibling that wants an index, not a count

public static class LongestSubarraySum
{
    /// <summary>Length of the LONGEST subarray summing to k.
    /// Stores the first index of each prefix, not a count.</summary>
    /// <param name="nums">Integers. Negative values are allowed.</param>
    /// <param name="k">The exact target sum.</param>
    /// <returns>The longest length, or 0 if no subarray qualifies.</returns>
    /// <example>Longest([1, -1, 5, -2, 3], 3) returns 4.</example>
    public static int Longest(int[] nums, int k)
    {
        // prefix sum -> first index where it appeared.
        // [0] = -1: the empty prefix (sum 0) "ends" at index -1, before the array.
        // So a match at index i gives length i - (-1) = i + 1, the whole prefix.
        var firstIndex = new Dictionary<int, int> { [0] = -1 };
        int running = 0;                 // 0: sum of no elements yet
        int best = 0;                    // 0: no qualifying subarray found yet

        // index is the current end. Invariant: running = sum of nums[0..index].
        for (int index = 0; index < nums.Length; index++)
        {
            running += nums[index];

            // An earlier prefix of running - k means nums[start+1..index] sums to k.
            if (firstIndex.TryGetValue(running - k, out int start))
            {
                // Length = index - start. No +1: start is the index BEFORE the range.
                best = Math.Max(best, index - start);
            }

            // Only record the FIRST time a prefix appears: earlier start, longer span.
            // TryAdd does nothing if the key already exists.
            firstIndex.TryAdd(running, index);
        }
        return best;
    }
}

Edge cases to raise

• k == 0 with zeros in the array, such as [0, 0, 0]: the answer is 6. Good test of the look-up-then-record order.
• All negatives with a negative k: works unchanged.
• Empty array: returns 0.
• No qualifying subarray: returns 0.
• Huge values: the running int can overflow. Switch running and the key type to long.

2. Continuous Subarray Sum Medium

Problem

Return true if the array has a contiguous subarray of length at least two whose sum is a multiple of k. k is a positive integer, and a multiple includes 0 × k.

The modular insight

There are only k possible remainders. So on a long array a repeat is certain. The whole difficulty is the length-at-least-two rule.

Approach

• Store the first index where each remainder appeared, not a count. You need the distance.
• Seed with [0] = -1. The empty prefix has remainder 0 and sits before index 0. That makes the length math work for a subarray that starts at the beginning.
• On a repeat, the subarray runs from firstIndex[remainder] + 1 to index. So its length is index - firstIndex[remainder]. Require at least 2.
• Never overwrite an existing remainder. The earliest index gives the longest span. That is the best chance of clearing the length rule.

Solution

public static class ContinuousSubarraySum
{
    /// <summary>True if some subarray of length 2 or more sums to a multiple of k.
    /// </summary>
    /// <param name="nums">Integers. The usual statement says non-negative.</param>
    /// <param name="k">A positive divisor.</param>
    /// <returns>True if such a subarray exists.</returns>
    /// <example>Check([23, 2, 4, 6, 7], 6) returns true.</example>
    public static bool Check(int[] nums, int k)
    {
        // remainder -> earliest index where the running sum had it.
        // [0] = -1: the empty prefix has remainder 0 and ends at index -1.
        // It lets a range that starts at index 0 qualify.
        var firstIndex = new Dictionary<int, int> { [0] = -1 };
        int running = 0;                 // 0: remainder of the empty sum

        // index is the current end.
        // Invariant: running = (sum of nums[0..index]) mod k, in 0..k-1.
        for (int index = 0; index < nums.Length; index++)
        {
            // % k: two prefixes with the same remainder differ by a multiple of k.
            // Reducing each step keeps running small, so it cannot overflow.
            // + k then % k again: C# % keeps the sign, so this lifts a
            // negative remainder into 0..k-1. Harmless for non-negative input.
            running = ((running + nums[index]) % k + k) % k;

            if (firstIndex.TryGetValue(running, out int start))
            {
                // The range is start + 1 .. index, so its length is the gap.
                // >= 2: the problem needs at least two elements.
                if (index - start >= 2) return true;
            }
            else
            {
                firstIndex[running] = index;     // earliest only, never overwrite
            }
        }
        return false;
    }
}

Walkthrough

nums = [23, 2, 4, 6, 7], k = 6:

1. index 0. Running sum 23, remainder 5. Not seen before. Record 5 at index 0.
2. index 1. Running sum 25, remainder 1. Not seen before. Record 1 at index 1.
3. index 2. Running sum 29, remainder 5. Seen at index 0. The gap is 2 − 0 = 2, which is long enough. Return true.

The subarray is [2, 4], which sums to 6.

Reading the figure. The rows show nums, the running sum, and the running sum mod 6. The two green cells share remainder 5. The arc joins them. The amber cells between them are the subarray [2, 4], and its sum is 6. The loop returns at index 2, so the dashed cells are never computed.

The map holds at most k distinct remainders. That bound is tighter than O(n), and it is worth stating.

Two details interviewers probe

Edge cases to raise

• Array shorter than 2: always false.
• [0, 0] with any k: true, since 0 is a multiple of everything.
• [1, 0] with k = 2: false. A good check of the length rule.
• A single element that is a multiple of k: does not qualify, because of the length rule.

3. Product of Array Except Self Medium

Problem

Return an array where answer[i] is the product of every element except nums[i]. Solve it without division and in O(n) time.

Approach

• The obvious answer is to take the total product and divide. Division is banned because one zero breaks it. Two zeros break it in a different way. Name that before you solve it.
• Everything except me is everything to my left times everything to my right. Those are a prefix product and a suffix product.
• Two sweeps. The first writes the prefix products straight into the answer. The second multiplies in the suffix products as it walks back. No second array, so the extra space is O(1).
• No hash map here. This is the prefix idea without the lookup half. The two halves can be used apart.

Solution

public static class ProductExceptSelf
{
    /// <summary>Product of all elements except the one at each index, without division.
    /// </summary>
    /// <param name="nums">Integers. Zeros are allowed.</param>
    /// <returns>A new array where answer[i] is the product of every other element.
    /// </returns>
    /// <example>Product([1, 2, 3, 4]) returns [24, 12, 8, 6].</example>
    public static int[] Product(int[] nums)
    {
        int n = nums.Length;
        var answer = new int[n];

        // Pass 1, left to right: answer[i] becomes the product of everything
        // strictly to the left of i.
        int prefix = 1;                  // 1: empty product, nothing left of index 0
        // Invariant: prefix = product of nums[0..i-1] at the top of each pass.
        for (int i = 0; i < n; i++)
        {
            answer[i] = prefix;          // store the left product before nums[i] joins
            prefix *= nums[i];           // now prefix covers nums[0..i]
        }

        // Pass 2, right to left: multiply in the product of everything
        // strictly to the right of i.
        int suffix = 1;                  // 1: empty product, nothing right of n - 1
        // Start at n - 1, the last index. i >= 0 so index 0 is included.
        // i-- walks backwards.
        // Invariant: suffix = product of nums[i+1..n-1] at the top of each pass.
        for (int i = n - 1; i >= 0; i--)
        {
            answer[i] *= suffix;         // left product times right product
            suffix *= nums[i];           // now suffix covers nums[i..n-1]
        }
        return answer;
    }
}

Walkthrough

nums = [1, 2, 3, 4]. Each line shows the left product after pass 1, the suffix at that index, and the final value:

• i = 0: left 1, suffix 24, final 24.
• i = 1: left 1, suffix 12, final 12.
• i = 2: left 2, suffix 4, final 8.
• i = 3: left 6, suffix 1, final 6.

Reading the figure. Each column is one index. Pass 1 writes the product of everything to the left (blue). Pass 2 walks back and multiplies in the product of everything to the right (violet). The green cell is the result. Both passes start at 1, so the ends of each row are 1. No division is used anywhere.

By the usual rule, the output array does not count as extra space. Say so. The problem statement usually says so too.

Why zeros make division fail

• [1, 2, 0, 4]. The correct answer is [0, 0, 8, 0]. Division by the total divides by zero, and C# throws DivideByZeroException for int.
• [0, 0, 3]. The correct answer is [0, 0, 0]. The total is 0, so every entry needs a special case.

You can patch division by counting zeros and branching on 0, 1, or more. It works, and it is ugly. The two-pass version needs no cases at all. That is the real argument for it.

Edge cases to raise

• One zero: every entry is 0 except at the zero’s own index. No special code needed.
• Two or more zeros: the whole answer is zeros. Also automatic.
• Negative values: signs work out on their own.
• Length 1: returns [1], the empty product. Confirm that is wanted.
• Large values: an int product overflows and wraps without warning. Use long, or wrap the multiply in checked to throw OverflowException instead. Python hides this. C# does not.

4. Subarray Sums Divisible by K Medium

Problem

Return the number of contiguous subarrays whose sum is divisible by k. Values may be negative.

Approach

• This is problem 1 and problem 2 combined. Keys are remainders, as in problem 2. Values are counts, as in problem 1.
• Reduce the running sum mod k as you go. The keys stay in 0..k-1, so the counts fit in an int[k]. No dictionary is needed.
• Every earlier prefix with the same remainder gives one subarray ending here. So add the whole count, not one.

Solution

public static class SubarraysDivByK
{
    /// <summary>Counts contiguous subarrays whose sum is divisible by k.</summary>
    /// <param name="nums">Integers. Negative values are allowed.</param>
    /// <param name="k">A positive divisor.</param>
    /// <returns>The number of qualifying subarrays.</returns>
    /// <example>Count([4, 5, 0, -2, -3, 1], 5) returns 7.</example>
    public static int Count(int[] nums, int k)
    {
        // remainder -> how many earlier prefixes had it.
        // Keys are 0..k-1, so an array of size k replaces the dictionary.
        var counts = new int[k];
        counts[0] = 1;                   // the empty prefix has remainder 0, seen once

        int running = 0;                 // 0: remainder of the empty sum
        int total = 0;                   // 0: no subarrays found yet

        // Invariant: running = (sum of nums up to and including value) mod k.
        foreach (int value in nums)
        {
            // % k keeps the key small. C# % can return a negative number,
            // so + k then % k again moves it into 0..k-1.
            running = ((running + value) % k + k) % k;

            // Each earlier prefix with this remainder closes one valid subarray.
            total += counts[running];
            counts[running]++;           // +1: record this prefix after the lookup
        }
        return total;
    }
}

Walkthrough

nums = [4, 5, 0, -2, -3, 1], k = 5. Each line shows the remainder, the count for it before the step, and the new total:

• value 4: remainder 4, count before 0, total 0.
• value 5: remainder 4, count before 1, total 1.
• value 0: remainder 4, count before 2, total 3.
• value −2: remainder 2, count before 0, total 3.
• value −3: remainder 4, count before 3, total 6. Here the raw % gives -1, and the fix turns it into 4.
• value 1: remainder 0, count before 1, total 7.

Answer 7. A remainder seen three times adds three subarrays at its fourth appearance. That is the counting half doing its job.

Reading the figure. The bottom row is every prefix sum mod 5, starting with the seed 0. Cells with the same color hold the same remainder. Any two cells of one color bracket a subarray whose sum divides by 5. So the answer is the number of same-color pairs: 6 amber pairs plus 1 green pair.

The combinatorial view

Edge cases to raise

• All values divisible by k, such as [5, 5, 5] with k = 5: every subarray qualifies, so the answer is 6.
• Heavy negatives: C# needs the + k fix. Without it, counts[-1] throws IndexOutOfRangeException. That crash is a gift: it tells you the bug at once.
• k == 1: everything is divisible, so the answer is n(n+1)/2.
• Empty array: returns 0.
• Very long arrays: the answer can reach about n²/2, which passes int.MaxValue near n = 65,000. Return long if n can be that big.