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 equality, and the values may be negative. Say both, then move on.
• Keep a running prefix. At each index, the number of subarrays ending here with sum k is the number of earlier prefixes equal to running - k.
• The map counts occurrences, because the same prefix value can appear many times and each one is a distinct subarray.

Solution

from collections import defaultdict


def subarray_sum(nums: list[int], k: int) -> int:
    """Count contiguous subarrays of nums summing to exactly k.

    Args:
        nums: Integers. Negative values are allowed.
        k: The exact target sum.

    Returns:
        The number of qualifying subarrays.

    Example:
        >>> subarray_sum([1, 2, 3], 3)
        2
    """
    # prefix value -> how many times it has been seen so far.
    # defaultdict(int): a missing key reads as 0, meaning "never seen".
    seen: defaultdict[int, int] = defaultdict(int)
    # 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.
    seen[0] = 1

    running = 0                  # 0: sum of no elements yet
    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.
    for 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.
        count += seen[running - k]
        # Record this prefix AFTER the lookup. +1: seen once more.
        seen[running] += 1

    return count

Walkthrough

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

The two subarrays are [1, 2] and [3]. Notice 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

def longest_subarray_sum(nums: list[int], k: int) -> int:
    """Length of the LONGEST subarray summing to k. Store first index, not counts."""
    # 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.
    first_index: dict[int, int] = {0: -1}
    running = 0                  # 0: sum of no elements yet
    best = 0                     # 0: no qualifying subarray found yet

    # index is the current end. Invariant: running = sum of nums[0..index].
    for index, value in enumerate(nums):
        running += value

        # An earlier prefix of running - k means nums[start+1..index] sums to k.
        if running - k in first_index:
            # Length = index - start. No +1: start is the index BEFORE the range.
            best = max(best, index - first_index[running - k])

        # Only record the FIRST time a prefix appears: earlier start, longer span.
        if running not in first_index:
            first_index[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.

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 guaranteed. The whole difficulty is the length-at-least-two rule.

Approach

• Store the first index at which each remainder appeared, not a count, because you need the distance.
• Seed with {0: -1}. The empty prefix has remainder 0 and sits before index 0, which makes the length arithmetic work for a subarray starting at the beginning.
• On a repeat, the subarray runs from first_index[remainder] + 1 to index, so its length is index - first_index[remainder]. Require at least 2.
• Never overwrite an existing remainder. Keeping the earliest index gives the longest possible span, which is the best chance of clearing the length rule.

Solution

def check_subarray_sum(nums: list[int], k: int) -> bool:
    """True if some subarray of length >= 2 sums to a multiple of k.

    Args:
        nums: Non-negative integers.
        k: A positive divisor.

    Returns:
        True if such a subarray exists.

    Example:
        >>> check_subarray_sum([23, 2, 4, 6, 7], 6)
        True
    """
    # 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.
    first_index: dict[int, int] = {0: -1}
    running = 0                  # 0: sum of no elements yet

    # index is the current end. Invariant: running = sum of nums[0..index].
    for index, value in enumerate(nums):
        running += value
        # % k: two prefixes with the same remainder differ by a multiple of k.
        remainder = running % k

        if remainder not in first_index:
            first_index[remainder] = index      # earliest only, never overwrite
        # The range is first_index + 1 .. index, so its length is the gap.
        # >= 2: the problem needs at least two elements.
        elif index - first_index[remainder] >= 2:
            return True

    return False

Walkthrough

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

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, which is a tighter bound than O(n) and 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. The ban on division is there because a single zero breaks it, and two zeros break it differently. 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 array. The second multiplies the suffix products in 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, and it is worth seeing that the two halves are separable.

Solution

def product_except_self(nums: list[int]) -> list[int]:
    """Product of all elements except the one at each index, without division.

    Args:
        nums: Integers. Zeros are allowed.

    Returns:
        A new list where answer[i] is the product of every other element.

    Example:
        >>> product_except_self([1, 2, 3, 4])
        [24, 12, 8, 6]
    """
    n = len(nums)
    answer = [1] * n             # 1: the identity for *, so it changes nothing

    # Pass 1, left to right: answer[i] becomes the product of everything
    # strictly to the left of i.
    prefix = 1                   # 1: empty product, nothing to the left of 0
    # Invariant: prefix = product of nums[0..i-1] at the top of each pass.
    for i in range(n):
        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.
    suffix = 1                   # 1: empty product, nothing right of n - 1
    # Start at n - 1, the last index. Stop -1 so index 0 is included.
    # Step -1 walks backwards.
    # Invariant: suffix = product of nums[i+1..n-1] at the top of each pass.
    for i in range(n - 1, -1, -1):
        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]:

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.

The output array is not counted as extra space, by the usual convention. Say so, because the problem statement usually says so too.

Why zeros make division fail

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

Edge cases to raise

• One zero: every entry is 0 except at the zero’s own index. Handled with no special code.
• 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 arrays: Python integers grow, so no overflow. In a fixed-width language this can overflow, and that is a real answer to give.

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 modulo k as you go, so the keys stay in 0..k-1 and the map never grows past k entries.
• Every earlier prefix with the same remainder gives one qualifying subarray ending here. So add the whole count, not one.

Solution

from collections import defaultdict


def subarrays_div_by_k(nums: list[int], k: int) -> int:
    """Count contiguous subarrays whose sum is divisible by k.

    Args:
        nums: Integers. Negative values are allowed.
        k: A positive divisor.

    Returns:
        The number of qualifying subarrays.

    Example:
        >>> subarrays_div_by_k([4, 5, 0, -2, -3, 1], 5)
        7
    """
    # remainder -> how many earlier prefixes had it. Missing keys read as 0.
    counts: defaultdict[int, int] = defaultdict(int)
    counts[0] = 1                 # the empty prefix has remainder 0, seen once

    running = 0                   # 0: remainder of the empty sum
    total = 0                     # 0: no subarrays found yet

    # Invariant: running = (sum of nums up to and including value) % k.
    for value in nums:
        # Reducing each step keeps the key in 0..k-1. Python's % is already
        # non-negative for a positive k, so negatives need no correction.
        running = (running + value) % k

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

    return total

Walkthrough

nums = [4, 5, 0, -2, -3, 1], k = 5:

Answer 7. Note how a remainder seen three times contributes 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: correct in Python, and needs an explicit fix in a language whose modulo keeps the dividend’s sign.
• k == 1: everything is divisible, so the answer is n(n+1)/2.
• Empty array: returns 0.