Continuous Subarray Sum (Multiple of K)

📋

Problem

Imagine you are analyzing financial transactions over days, and you want to find if any continuous sequence of days sums up to a multiple of a given number K, indicating a cyclical pattern in spending.

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: k = 0 and subarray sums to 0 → true if subarray sum is zeronums contains negative numbers → should still work correctlysubarray length exactly 2 → minimum valid subarray size

</>

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: falseNot handling subarray length >= 2 condition properly; returning false when valid subarray exists.✅ Ensure to check that subarray length is at least two before returning true.

Wrong: falseFailing to handle k=0 special case by checking consecutive zeros.✅ Add explicit check for consecutive zeros when k=0 before modulo logic.

Wrong: falseIncorrect modulo operation with negative numbers causing wrong remainder tracking.✅ Normalize negative remainders by adding k before storing/checking in hashmap.

Wrong: trueGreedy approach returning true prematurely without checking all subarrays.✅ Use prefix sum remainder hashmap approach instead of greedy partial sums.

Wrong: TLEUsing brute force O(n^2) approach on large inputs.✅ Implement O(n) prefix sum remainder hashmap solution.

✓

Test Cases

Focus on handling minimal and boundary inputs correctly.

Consider tricky cases that break greedy or naive approaches.

Optimize your solution to linear time using prefix sums and hashmaps.

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

💡 Consider prefix sums and their remainders modulo k.

💡 Use a hashmap to track earliest indices of each remainder.

💡 Check 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 earliest remainder indices and verifying distance >= 2.

✓ Correctly identifies subarray with sum multiple of k.

t1_02basic

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Subarray [0,0] sums to 0, which is multiple of 3.

💡 Remember that zero sum subarrays are multiples of any k except when k=0.

💡 Handle the special case when k=0 by checking for consecutive zeros.

💡 Check subarray length is at least two when sum is zero.

Why it failed: Incorrectly returns false for zero sum subarray; likely missing special case for k=0 or subarray length check. Fix by explicitly checking consecutive zeros when k=0.

✓ Correctly handles zero sum subarray with k nonzero.

t2_01edge

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

Expectedfalse

⏱ Performance - must finish in 2000ms

Empty array has no subarrays of length >= 2.

💡 Check for empty input or insufficient length early.

💡 Return false if nums length < 2.

💡 No subarray exists if array is empty.

Why it failed: Fails on empty input by not checking length; fix by returning false if nums length < 2.

✓ Correctly returns false for empty input.

t2_02edge

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

Expectedfalse

⏱ Performance - must finish in 2000ms

Single element array cannot have subarray of length >= 2.

💡 Minimum subarray length is 2; single element arrays fail immediately.

💡 Check length before processing.

💡 Return false if nums length < 2.

Why it failed: Fails single element input by not enforcing subarray length >= 2; fix by checking length before main logic.

✓ Correctly returns false for single element input.

t2_03edge

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Subarray [1,2] sums to 3, which is multiple of 3; tests exact boundary subarray length 2.

💡 Verify subarray length exactly 2 is handled.

💡 Check remainder calculation for small subarrays.

💡 Ensure subarray length >= 2 condition is inclusive.

Why it failed: Fails to detect subarray length exactly 2; fix by using >= 2 condition in length checks.

✓ Correctly handles subarray length exactly 2.

t3_01corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

No continuous subarray of length >= 2 sums to multiple of 5; tests greedy approach trap.

💡 Greedy approach may fail by stopping early.

💡 Use prefix sums and remainder hashmap instead of greedy.

💡 Track remainders and check for repeats with distance >= 2.

Why it failed: Greedy approach returns true incorrectly; fix by using prefix sum remainder hashmap and verifying subarray length >= 2.

✓ Correctly rejects no valid subarray despite tempting greedy partial sums.

t3_02corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Tests k=0 special case; subarray of zeros sums to 0 which is multiple of 0.

💡 k=0 requires special handling: check for consecutive zeros.

💡 Prefix sum modulo k is undefined for k=0.

💡 Return true if any two consecutive zeros found.

Why it failed: Fails k=0 case by using modulo operation; fix by checking consecutive zeros explicitly when k=0.

✓ Correctly handles k=0 by detecting consecutive zeros.

t3_03corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Tests negative numbers; subarray [-2, 2] sums to 0 which is a multiple of 6, so returns true.

💡 Negative numbers affect prefix sums but modulo still applies.

💡 Use modulo operation that handles negative values correctly.

💡 Normalize remainder by adding k if negative.

Why it failed: Fails negative number handling by not normalizing negative remainders; fix by adding k to negative remainder before storing/checking.

✓ Correctly handles negative numbers with modulo normalization.

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) solution must complete within 2 seconds; brute force O(n^2) will time out.

💡 Brute force O(n^2) is too slow for n=100.

💡 Use prefix sums with hashmap for O(n) time.

💡 Track remainders and earliest indices to detect subarrays efficiently.

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

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

Practice

1. You are given an integer array and two bounds left and right. You need to count the number of contiguous subarrays where the maximum element lies between left and right inclusive. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Sort the array and use binary search to find valid subarrays within bounds.

B. Use a brute force nested loop to check every subarray and track its maximum.

C. Use a sliding window that expands and contracts based on the current maximum element.

D. Count subarrays with max ≤ right and subtract those with max < left using a single pass.

Solution

1. Step 1: Understand the problem constraints

   The problem requires counting subarrays with maximum elements bounded between left and right, which can be done efficiently by counting subarrays with max ≤ right and subtracting those with max < left.

2. Step 2: Identify the optimal approach

   The approach that counts subarrays with max ≤ right and subtracts those with max < left uses a single linear pass and constant space, guaranteeing O(n) time complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal linear approach uses subtraction of two counts [OK]

Hint: Subtract counts of subarrays bounded by right and left-1 [OK]

Common Mistakes:

• Assuming sliding window can track max efficiently
• Trying to sort and binary search subarrays
• Using brute force for optimal solution

2. What is the time complexity of the optimal approach that counts subarrays with maximum bounded by left and right using the subtraction of two counts (countAtMost)?

medium

A. O(n) because it makes two linear passes over the array

B. O(n^2) because it checks all subarrays explicitly

C. O(n log n) due to sorting the array before counting

D. O(n) with O(n) extra space to store intermediate counts

Solution

1. Step 1: Identify operations in countAtMost

   countAtMost iterates over the array once, updating counters in O(1) time per element.

2. Step 2: Analyze overall complexity

   numSubarrayBoundedMax calls countAtMost twice, each O(n), so total time is O(n). No sorting or nested loops involved.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two linear scans -> O(n) time, constant space [OK]

Hint: Two linear scans, no nested loops or sorting [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming sorting is needed
• Thinking extra space is O(n)

3. What is the time complexity of the optimal prefix sum with array approach for finding the longest subarray with equal number of 0s and 1s, given an input array of length n?

medium

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

B. O(n) with additional O(n) space for prefix sums and first occurrence array

C. O(n log n) due to sorting prefix sums

D. O(n^2) due to nested loops checking all subarrays

Solution

1. Step 1: Identify the main loop runs once over n elements.

   Each iteration does constant time work updating prefix sums and array lookups.

2. Step 2: Recognize space usage for prefix sums and first_occurrence array is O(n).

   Time is O(n), space is O(n), so total complexity includes both.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Brute force is O(n²), no sorting involved [OK]

Hint: Linear scan with O(n) space for prefix sums [OK]

Common Mistakes:

• Confusing brute force O(n²) with optimal
• Assuming sorting is needed
• Ignoring auxiliary space

4. What is the time complexity of the optimal two-pointer approach for the Summary Ranges problem on an input list of length n?

medium

A. O(n log n) due to sorting the input before scanning for ranges.

B. O(n²) because the inner while loop can run up to n times for each start pointer.

C. O(n) because each element is visited at most twice by the two pointers combined.

D. O(n) but with O(n) auxiliary space for storing the output ranges.

Solution

1. Step 1: Analyze outer and inner loops

   The outer loop advances start pointer, inner loop advances end pointer; together they move forward without revisiting elements.

2. Step 2: Confirm total iterations

   Each element is visited at most twice (once by start, once by end), so total time is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two pointers linear scan -> O(n) time [OK]

Hint: Two pointers each move forward once -> O(n) time [OK]

Common Mistakes:

• Assuming inner loop restarts fully causing O(n²)
• Confusing sorting cost if input is already sorted
• Ignoring that output space is separate from time complexity

5. Suppose the problem is modified so that elements can be reused multiple times in the subsequence (i.e., indices can be repeated). Which modification to the DP approach correctly handles this variant?

hard

A. Use a recursive memoized solution that tries all possible next elements including the current one

B. Keep the same DP but allow j to equal i in the inner loop to reuse elements

C. Modify DP to track counts per difference but reset dp[i][diff] to 1 each time to allow reuse

D. Use a graph-based BFS to explore sequences allowing repeated nodes

Solution

1. Step 1: Understand reuse means indices can repeat

   Standard DP assumes strictly increasing indices; allowing reuse breaks this assumption.

2. Step 2: Recognize recursive memoization can explore all sequences with repeated elements

   Recursive approach with memoization can try all next elements including current, correctly handling reuse.

3. Step 3: Evaluate other options

   Allowing j == i breaks DP indexing logic; resetting dp[i][diff] loses subsequence length info; BFS is inefficient and complex.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Recursive memoization handles repeated indices correctly [OK]

Hint: Reuse requires recursion with memoization, not standard DP indexing [OK]

Common Mistakes:

• Allowing j == i in DP loops breaks monotonic index assumption
• Resetting dp values loses subsequence length info
• Trying BFS which is inefficient