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
    seen: defaultdict[int, int] = defaultdict(int)
    seen[0] = 1

    running = 0
    count = 0

    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]
        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].

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."""
    first_index: dict[int, int] = {0: -1}     # empty prefix ends before index 0
    running = 0
    best = 0

    for index, value in enumerate(nums):
        running += value

        if running - k in first_index:
            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
    first_index: dict[int, int] = {0: -1}
    running = 0

    for index, value in enumerate(nums):
        running += value
        remainder = running % k

        if remainder not in first_index:
            first_index[remainder] = index      # earliest only, never overwrite
        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.

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

    # Pass 1, left to right: answer[i] becomes the product of everything
    # strictly to the left of i.
    prefix = 1
    for i in range(n):
        answer[i] = prefix
        prefix *= nums[i]

    # Pass 2, right to left: multiply in the product of everything
    # strictly to the right of i.
    suffix = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix
        suffix *= nums[i]

    return answer

Walkthrough

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

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
    """
    counts: defaultdict[int, int] = defaultdict(int)
    counts[0] = 1                 # the empty prefix has remainder 0

    running = 0
    total = 0

    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

    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.

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.