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. You are given an array of integers and need to determine if any value appears at least twice. Which approach guarantees the most efficient detection of duplicates in terms of time complexity?

easy

A. Sort the array and then scan once to check if any adjacent elements are equal.

B. Use a hash set to track seen elements and check membership while iterating once.

C. Use nested loops to compare every pair of elements for equality.

D. Use dynamic programming to build a table of duplicate occurrences.

Solution

1. Step 1: Understand the problem requirements

   The problem requires detecting duplicates efficiently in an array.

2. Step 2: Compare approaches based on time complexity

   Sorting then scanning is O(n log n), nested loops is O(n²), and dynamic programming is unnecessary here. Using a hash set allows O(n) time with O(n) space by checking membership during one pass.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Hash set membership check is O(1) average, enabling linear time detection [OK]

Hint: Hash set membership check enables linear time detection [OK]

Common Mistakes:

• Confusing sorting approach as optimal
• Thinking nested loops are efficient enough
• Misapplying DP to a membership problem

2. You are given a string and need to find the index of the first character that appears exactly once. Which approach guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Use a greedy approach that picks the first character that is not equal to its adjacent characters.

B. Use a brute force nested loop to compare each character with every other character.

C. Use a dynamic programming approach to store subproblems of unique characters.

D. Use a single pass to track each character's frequency and first occurrence index, then find the minimum index with frequency one.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the first unique character's index efficiently.

2. Step 2: Identify approach that tracks frequency and first occurrence in one pass

   Only the single pass with frequency and index tracking guarantees O(n) time and O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single pass frequency + index tracking is optimal [OK]

Hint: Track frequency and first index in one pass [OK]

Common Mistakes:

• Assuming greedy adjacent check works
• Using DP unnecessarily
• Brute force is optimal

3. What is the average time complexity of the remove operation in the optimal Insert Delete GetRandom data structure that uses a hash map and an array with the swap-delete trick?

medium

A. O(n), because removing an element requires shifting elements in the array

B. O(log n), because hash map operations take logarithmic time on average

C. O(1), because swapping with the last element and updating the hash map takes constant time

D. O(1) amortized, but worst-case O(n) due to occasional resizing of the array

Solution

1. Step 1: Identify operations in remove

   Remove finds index in O(1) via hash map, swaps with last element, updates hash map, and pops last element.

2. Step 2: Analyze time per step

   All steps are O(1) average time; no shifting of elements occurs.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Swap-delete avoids O(n) shifting, ensuring O(1) remove [OK]

Hint: Swap-delete avoids shifting, so remove is O(1) [OK]

Common Mistakes:

• Assuming array remove requires shifting O(n)
• Confusing hash map average O(1) with O(log n)
• Ignoring that resizing is amortized and rare

4. What is the time complexity of the optimal sorting + two pointers approach for finding the intersection of two arrays of sizes m and n, respectively?

medium

A. O(m * n)

B. O(m log m + n log n)

C. O(m + n)

D. O(min(m, n) * log(max(m, n)))

Solution

1. Step 1: Identify sorting cost

   Sorting nums1 costs O(m log m), sorting nums2 costs O(n log n).

2. Step 2: Identify two-pointer traversal cost

   Two-pointer traversal is O(m + n) which is dominated by sorting.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting dominates, so total is O(m log m + n log n) [OK]

Hint: Sorting dominates time complexity [OK]

Common Mistakes:

• Confusing traversal cost as total
• Assuming nested loops complexity
• Misreading min/max in complexity

5. What is the average time complexity of the hash map based Two Sum solution that iterates over the array once and checks for complements in the hash map?

medium

A. O(n) average time due to single pass with hash map lookups

B. O(n log n) due to sorting the array

C. O(n^2) because each lookup in hash map can be O(n) in worst case

D. O(n) but with O(n) extra space for the hash map

Solution

1. Step 1: Analyze time complexity of hash map lookups

   Hash map lookups and insertions are O(1) average time, so iterating once over n elements is O(n).

2. Step 2: Distinguish average vs worst case

   Worst case hash collisions can degrade to O(n), but average case is O(1), making total O(n) average time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with O(1) average lookups yields O(n) average time [OK]

Hint: Hash map lookups average O(1), total O(n) time [OK]

Common Mistakes:

• Confusing worst-case hash map lookup with average case
• Assuming sorting is required
• Ignoring extra space usage