Continuous Subarray Sum

📋

Problem

Imagine you are analyzing a stream of daily sales and want to quickly detect if any consecutive days' sales sum up to a multiple of a given number, helping spot periodic trends or anomalies.

Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, that is, sum is n * k where n is an integer. Otherwise, return false.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9-10^9 ≤ k ≤ 10^9

Edge cases: nums = [0, 0], k = 0 → true (sum zero is multiple of zero)nums = [1, 2], k = 0 → false (no subarray sums to zero)nums = [5, 0, 0], k = 0 → true (subarray [0,0] sums to 0)

</>

IDE

def checkSubarraySum(nums: list[int], k: int) -> bool:public boolean checkSubarraySum(int[] nums, int k)bool checkSubarraySum(vector<int>& nums, int k)function checkSubarraySum(nums, k)

def checkSubarraySum(nums, k):
    # Write your solution here
    pass

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool checkSubarraySum(vector<int>& nums, int k) {
    // Write your solution here
    return false;
}

function checkSubarraySum(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: falseFails to detect subarray summing to multiple of k due to missing remainder map or subarray length check.✅ Implement prefix sum remainder tracking and ensure subarray length >= 2 before returning true.

Wrong: trueIncorrectly returns true for single element or empty array inputs.✅ Add explicit check for array length < 2 and return false immediately.

Wrong: falseFails to handle k=0 case properly, missing consecutive zeros subarray detection.✅ Add special case handling for k=0 by checking consecutive zeros in nums.

Wrong: falseModulo operation mishandled for negative k values.✅ Normalize remainder calculation to positive range using remainder = ((sum % k) + abs(k)) % abs(k).

Wrong: TLEUsing brute force O(n^2) approach on large inputs.✅ Switch to O(n) prefix sum with hash map approach to track remainders.

✓

Test Cases

Focus on handling minimal and boundary inputs correctly before moving on.

Prepare to handle tricky modulo cases and common algorithmic pitfalls.

Optimize your solution to linear time using prefix sums and hash maps.

t1_01basic

Input{"nums":[23,2,4,6,7],"k":6}

Expectedtrue

⏱ Performance - must finish in 2000ms

The subarray [2, 4] sums to 6, which is a multiple of k=6.

💡 Consider prefix sums and their remainders modulo k.

💡 Use a hash map to track earliest indices of each remainder.

💡 Return true if a remainder repeats with at least two elements apart.

Why it failed: Failed to detect subarray summing to multiple of k; likely missing remainder tracking or subarray length check >= 2. Fix by storing first occurrence of each remainder and checking distance.

✓ Correctly identifies subarray with sum multiple of k.

t1_02basic

Input{"nums":[5,0,0],"k":0}

Expectedtrue

⏱ Performance - must finish in 2000ms

Subarray [0, 0] sums to 0, which is a multiple of k=0.

💡 Handle the special case when k is zero separately.

💡 Check for any continuous subarray of at least two zeros.

💡 Return true if such a subarray exists, else false.

Why it failed: Incorrectly handles k=0 case; must check for consecutive zeros as sum zero is multiple of zero. Fix by adding explicit check for k=0 and consecutive zeros.

✓ Correctly handles k=0 and detects zero-sum subarrays.

t2_01edge

Input{"nums":[],"k":5}

Expectedfalse

⏱ Performance - must finish in 2000ms

Empty array has no subarrays, so return false.

💡 Check if input array is empty or too short for subarray of size 2.

💡 Return false immediately if length < 2.

💡 No subarray exists in empty input.

Why it failed: Fails on empty input by not returning false immediately; fix by adding length check at start.

✓ Correctly returns false for empty input.

t2_02edge

Input{"nums":[1],"k":1}

Expectedfalse

⏱ Performance - must finish in 2000ms

Single element array cannot have subarray of size at least two.

💡 Minimum subarray size is two; check array length.

💡 Return false if length < 2 regardless of k.

💡 No valid subarray possible with single element.

Why it failed: Fails to enforce minimum subarray length of two; fix by checking length before processing.

✓ Correctly returns false for single element input.

t2_03edge

Input{"nums":[1,2,3,4],"k":5}

Expectedtrue

⏱ Performance - must finish in 2000ms

Subarray [2,3] sums to 5, which is multiple of k=5.

💡 Check subarrays that sum exactly to k, not just multiples.

💡 Use prefix sums modulo k to detect repeats.

💡 Ensure subarray length is at least two.

Why it failed: Fails to detect subarray summing exactly to k; likely incorrect modulo or subarray length logic. Fix by verifying remainder repeats and index difference >= 2.

✓ Correctly detects subarray summing to multiple of k at boundary.

t3_01corner

Input{"nums":[1,2,12,4,5],"k":6}

Expectedtrue

⏱ Performance - must finish in 2000ms

Subarray [2,12,4] sums to 18, multiple of 6; tests greedy trap.

💡 Greedy approach may fail; consider prefix sums and remainders.

💡 Track earliest occurrence of each remainder to find valid subarray.

💡 Check subarray length >= 2 when remainder repeats.

Why it failed: Greedy approach fails by stopping early or ignoring remainder repeats; fix by using prefix sum remainder map and checking index difference >= 2.

✓ Correctly handles greedy trap by using prefix sums and remainder map.

t3_02corner

Input{"nums":[5,5,5,5],"k":5}

Expectedtrue

⏱ Performance - must finish in 2000ms

Multiple subarrays sum to multiples of 5; tests handling of repeated elements.

💡 Repeated elements can produce multiple valid subarrays.

💡 Ensure remainder map stores earliest index only.

💡 Check subarray length >= 2 for repeated remainders.

Why it failed: Fails by overwriting remainder indices or ignoring subarray length; fix by storing first occurrence and checking index difference >= 2.

✓ Correctly handles repeated elements and remainder tracking.

t3_03corner

Input{"nums":[23,2,4,6,7],"k":-6}

Expectedtrue

⏱ Performance - must finish in 2000ms

Negative k handled correctly; subarray [2,4] sums to 6, multiple of -6.

💡 Modulo with negative k requires normalization.

💡 Use remainder = ((sum % k) + abs(k)) % abs(k) to handle negatives.

💡 Check remainder repeats with subarray length >= 2.

Why it failed: Fails on negative k due to incorrect modulo handling; fix by normalizing remainder to positive range.

✓ Correctly handles negative k with normalized modulo.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"k":97}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) prefix sum + hash map solution must complete within 2 seconds.

💡 Brute force O(n^2) will time out for n=100.

💡 Use prefix sums and hash map for O(n) time complexity.

💡 Avoid nested loops; track remainders and earliest indices.

Why it failed: TLE due to O(n^2) brute force approach; fix by implementing O(n) prefix sum with remainder hash map.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Consider the following Python function to find the longest contiguous subarray with equal number of 0s and 1s. What is the returned value when the input is [0, 1, 0, 1]?

def findMaxLength(nums):
    prefix_sum = 0
    seen = {0: -1}
    max_length = 0
    for i, num in enumerate(nums):
        prefix_sum += 1 if num == 1 else -1
        if prefix_sum in seen:
            max_length = max(max_length, i - seen[prefix_sum])
        else:
            seen[prefix_sum] = i
    return max_length

easy

A. 4

B. 2

C. 3

D. 0

Solution

1. Step 1: Trace prefix sums and seen map

   Index 0: num=0 -> prefix_sum=-1, seen={0:-1, -1:0}, max_length=0 Index 1: num=1 -> prefix_sum=0, seen has 0 at -1, max_length=max(0,1-(-1))=2 Index 2: num=0 -> prefix_sum=-1, seen has -1 at 0, max_length=max(2,2-0)=2 Index 3: num=1 -> prefix_sum=0, seen has 0 at -1, max_length=max(2,3-(-1))=4

2. Step 2: Return max_length

   max_length is 4, the length of the entire array.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Full array balanced, max_length=4 [OK]

Hint: Prefix sums track balance; max length updates on repeated sums [OK]

Common Mistakes:

• Off-by-one errors in length calculation
• Ignoring initial seen entry for sum 0
• Confusing prefix sum updates

2. You are given two integer arrays and need to find all elements that appear in both arrays, including duplicates, with the output containing each common element as many times as it appears in both arrays. Which approach guarantees the most efficient solution in terms of time complexity for large inputs?

easy

A. Sort both arrays and use two pointers to traverse them simultaneously, collecting common elements.

B. Use dynamic programming to build a table of common elements counts.

C. Use nested loops to check each element of the first array against all elements of the second array.

D. Use a greedy approach to pick elements from the first array that appear earliest in the second array.

Solution

1. Step 1: Understand problem requirements

   The problem requires finding all common elements including duplicates, so a method that preserves counts is needed.

2. Step 2: Evaluate approaches

   Sorting both arrays and using two pointers allows linear traversal after sorting, efficiently finding all duplicates. Nested loops are O(m*n), DP is not applicable here, and greedy does not guarantee correct counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two pointers is O(m log m + n log n) and handles duplicates correctly [OK]

Hint: Sorting + two pointers handles duplicates efficiently [OK]

Common Mistakes:

• Thinking nested loops are efficient enough
• Confusing DP applicability
• Assuming greedy works for duplicates

3. Identify the bug in the following Python code for detecting duplicates:

medium

A. Line 2: initializing the set should be a list

B. Line 6: returning False outside the loop is incorrect

C. Line 4: adding the number before checking membership causes always True

D. Line 5: the membership check should use 'not in' instead of 'in'

Solution

1. Step 1: Analyze the order of operations

   The code adds the number to the set before checking if it is already present, so the membership check always returns True on the first iteration.

2. Step 2: Identify the bug

   Membership check must occur before adding the number to avoid false positives.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding before checking membership causes immediate True return [OK]

Hint: Check membership before adding to avoid false positives [OK]

Common Mistakes:

• Adding before checking membership
• Misplacing return statements
• Confusing set initialization

4. What is the time complexity of the optimal bidirectional hash map approach to check if two strings of length n are isomorphic?

medium

A. O(n) because each character is processed once with constant-time hash map operations

B. O(n²) due to nested loops checking all character pairs

C. O(n log n) due to sorting characters before mapping

D. O(1) since hash maps provide constant-time lookups

Solution

1. Step 1: Identify the main loop over string length

   The algorithm iterates once over the strings of length n, processing each character pair exactly once.

2. Step 2: Analyze hash map operations

   Hash map insertions and lookups are average O(1), so total time is O(n) * O(1) = O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No nested loops or sorting involved, so O(n) [OK]

Hint: Single pass with hash maps -> O(n) time [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Assuming sorting is needed
• Ignoring hash map average case

5. The following code attempts to find the longest subarray with sum divisible by k. Identify the line containing the subtle bug that causes incorrect results for arrays containing negative numbers.

def longest_subarray_div_by_k(nums, k):
    earliest = [-2] * k
    earliest[0] = -1
    max_length = 0
    prefix_sum = 0
    for i, num in enumerate(nums):
        prefix_sum += num
        remainder = prefix_sum % k
        # Bug: missing adjustment for negative remainder
        if earliest[remainder] != -2:
            max_length = max(max_length, i - earliest[remainder])
        else:
            earliest[remainder] = i
    return max_length

medium

A. Line computing remainder = prefix_sum % k

B. Line initializing earliest[0] = -1

C. Line updating max_length = max(max_length, i - earliest[remainder])

D. Line setting earliest[remainder] = i

Solution

1. Step 1: Identify remainder calculation

   When prefix_sum is negative, prefix_sum % k in Python returns a non-negative remainder, but in some languages or implementations it can be negative. The code lacks adjustment for negative remainder.

2. Step 2: Why this causes bugs

   If remainder is negative, indexing earliest array causes errors or misses correct subarrays. The fix is to add if remainder < 0: remainder += k.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Negative prefix sums require remainder adjustment [OK]

Hint: Check remainder calculation for negative sums [OK]

Common Mistakes:

• Forgetting to adjust negative remainders
• Misinitializing earliest array
• Updating max_length incorrectly