Budgets That Hit the Target

TIP103 Unit 11 Session 2 (Click for link to problem statements)

Budgets That Hit the Target

A ledger of daily net changes is stored in nums. Auditors want to know how many contiguous stretches of days sum to exactly k.

Return the number of contiguous subarrays whose sum equals k.

def subarray_sum(nums, k):
    pass

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 20-30 mins
🛠️ Topics: Arrays, Prefix Sums, Hashmaps

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

Established a set (2-3) of test cases to verify their own solution later.

Established a set (1-2) of edge cases to verify their solution handles complexities.

Have fully understood the problem and have no clarifying questions.

Have you verified any Time/Space Constraints for this problem?

Q: What counts as a valid stretch of days?
- A: Any contiguous subarray of nums — the days must be consecutive, and we count every subarray whose elements sum to exactly k, even if subarrays overlap.
Q: Can the daily net changes be negative or zero?
- A: Yes. The ledger records net changes, so entries can be negative or zero. This means a running sum can decrease or repeat, and a simple sliding window will not work.
Q: Do we return the subarrays themselves or just how many there are?
- A: Just the count — an integer.

HAPPY CASE
Input: nums = [1, 1, 1], k = 2
Output: 2
Explanation: The stretches [1, 1] (days 0-1) and [1, 1] (days 1-2) each sum to 2.

Input: nums = [1, 2, 3], k = 3
Output: 2
Explanation: The stretches [1, 2] and [3] each sum to 3.

EDGE CASE
Input: nums = [1, -1, 0], k = 0
Output: 3
Explanation: With negative and zero entries, the stretches [1, -1], [1, -1, 0], and [0] all sum to 0. Overlapping subarrays each count separately.

Input: nums = [], k = 5
Output: 0
Explanation: An empty ledger has no subarrays, so no stretch can hit the target.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Subarray Sum Problems, we can consider the following approaches:

Prefix Sum + Hashmap: The sum of any subarray nums[i..j] equals prefix[j] - prefix[i-1]. If we store how many times each prefix sum has occurred in a hashmap, then at each index we can count in O(1) how many earlier prefixes equal current_prefix - k.
Brute Force: Check every pair of start and end indices and sum each subarray — correct but O(N^2) (or O(N^3) if sums are recomputed from scratch).
Note: a sliding window does not apply here because entries can be negative, so growing the window does not monotonically grow the sum.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Keep a running (prefix) sum as we scan the ledger left to right. A subarray ending at the current day sums to k exactly when some earlier prefix sum equals prefix_sum - k. Store counts of every prefix sum seen so far in a hashmap, seeded with {0: 1} to count subarrays that start at day 0.

1) Initialize count = 0, prefix_sum = 0, and a hashmap seen = {0: 1}.
2) For each num in nums:
   a) Add num to prefix_sum.
   b) If (prefix_sum - k) is in seen, add seen[prefix_sum - k] to count.
   c) Increment seen[prefix_sum] by 1.
3) Return count.

⚠️ Common Mistakes

Forgetting to seed the hashmap with {0: 1}, which misses every subarray that starts at index 0.
Updating seen[prefix_sum] before checking for prefix_sum - k; when k == 0 this wrongly counts the empty subarray at the current index.
Reaching for a sliding window, which breaks as soon as the ledger contains negative or zero entries.
Storing only whether a prefix sum has occurred (a set) instead of how many times (a count), undercounting when prefix sums repeat.

4: I-mplement

Implement the code to solve the algorithm.

def subarray_sum(nums, k):
    count = 0
    prefix_sum = 0
    seen = {0: 1}  # prefix sum -> number of times it has occurred

    for num in nums:
        prefix_sum += num
        # A subarray ending here sums to k if some earlier
        # prefix sum equals prefix_sum - k
        count += seen.get(prefix_sum - k, 0)
        # Record the current prefix sum for future days
        seen[prefix_sum] = seen.get(prefix_sum, 0) + 1

    return count

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Input: nums = [1, 1, 1], k = 2
- Day 0: prefix_sum = 1, seen has no -1, count = 0, seen = {0: 1, 1: 1}
- Day 1: prefix_sum = 2, seen[0] = 1, count = 1, seen = {0: 1, 1: 1, 2: 1}
- Day 2: prefix_sum = 3, seen[1] = 1, count = 2, seen = {0: 1, 1: 1, 2: 1, 3: 1}
- Output: 2
Input: nums = [1, 2, 3], k = 3
- Day 0: prefix_sum = 1, seen has no -2, count = 0
- Day 1: prefix_sum = 3, seen[0] = 1, count = 1 (stretch [1, 2])
- Day 2: prefix_sum = 6, seen[3] = 1, count = 2 (stretch [3])
- Output: 2

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of days in the ledger nums.

Time Complexity: O(N) because we make a single pass over the ledger, and each hashmap lookup and update is O(1) on average.
Space Complexity: O(N) because in the worst case every prefix sum is distinct and the hashmap stores one entry per day.

Uh oh!

Budgets That Hit the Target