Continuous Subarray Sum

🎯

Continuous Subarray Sum

mediumHASH_MAPAmazonFacebookBloomberg

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.

💡 This problem requires understanding how to efficiently check sums of continuous subarrays without enumerating all possibilities. Beginners often struggle because the naive approach is too slow, and the key insight involves prefix sums combined with modular arithmetic and hash maps.

📋

Problem Statement

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

💡

Example

Input"nums = [23, 2, 4, 6, 7], k = 6"

Outputtrue

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

Input"nums = [23, 2, 6, 4, 7], k = 6"

Outputtrue

The subarray [23, 2, 6, 4, 7] sums to 42, which is 7 * 6.

Input"nums = [23, 2, 6, 4, 7], k = 13"

Outputfalse

No continuous subarray of size at least 2 sums to a multiple of 13.

• 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)
• nums = [1], k = 1 → false (subarray size must be at least 2)

⚠️

Common Mistakes

Not handling k=0 separately

Modulo by zero error or incorrect results

✅ Add explicit check for k=0 and check if subarray sums to zero

Checking subarray length incorrectly (allowing length 1)

Returns true for single element subarrays, violating problem constraints

✅ Ensure subarray length is at least 2 by checking index difference > 1

Not normalizing negative modulo results

Incorrect remainder mapping leading to false negatives

✅ Normalize remainder with (remainder + k) % k

Updating remainder map even if remainder already exists

Overwrites earliest index, causing incorrect subarray length calculation

✅ Only insert remainder if not already present

Not initializing remainder map with {0: -1}

Misses subarrays starting at index 0

✅ Initialize remainder map with 0 mapped to -1

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem's core: checking all possible subarrays. Though inefficient, it builds intuition about subarray sums and why optimization is needed.

Intuition

Check every possible continuous subarray of length at least two and compute its sum to see if it's divisible by k.

Algorithm

1. Iterate over all possible start indices of subarrays.
2. For each start, iterate over all possible end indices (start+1 to end).
3. Calculate the sum of elements between start and end.
4. Check if the sum is divisible by k; if yes, return true.

💡 The nested loops and sum calculation are straightforward but lead to repeated work, making it slow for large inputs.

</>

Code

def checkSubarraySum(nums, k):
    n = len(nums)
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            if end - start + 1 >= 2:
                if k == 0:
                    if total == 0:
                        return True
                else:
                    if total % k == 0:
                        return True
    return False

# Driver code
if __name__ == '__main__':
    print(checkSubarraySum([23, 2, 4, 6, 7], 6))  # True

Line Notes

for start in range(n):Outer loop picks the start index of subarray

total = 0Initialize sum for the current start index

for end in range(start, n):Inner loop picks the end index of subarray

total += nums[end]Accumulate sum of current subarray

if end - start + 1 >= 2:Ensure subarray length is at least 2 before checking

if k == 0:Handle special case where k is zero to avoid modulo by zero

if total == 0:If sum is zero and k is zero, subarray qualifies

if total % k == 0:Check if sum is divisible by k

public class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int n = nums.length;
        for (int start = 0; start < n; start++) {
            int total = 0;
            for (int end = start; end < n; end++) {
                total += nums[end];
                if (end - start + 1 >= 2) {
                    if (k == 0) {
                        if (total == 0) return true;
                    } else {
                        if (total % k == 0) return true;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.checkSubarraySum(new int[]{23, 2, 4, 6, 7}, 6)); // true
    }
}

Line Notes

for (int start = 0; start < n; start++) {Outer loop selects start index

int total = 0;Reset sum for each new start

for (int end = start; end < n; end++) {Inner loop selects end index

total += nums[end];Add current element to sum

if (end - start + 1 >= 2) {Check subarray length constraint

if (k == 0) {Special case for k=0 to avoid modulo error

if (total == 0) return true;If sum zero and k zero, subarray found

if (total % k == 0) return true;Check divisibility by k

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        for (int start = 0; start < n; start++) {
            int total = 0;
            for (int end = start; end < n; end++) {
                total += nums[end];
                if (end - start + 1 >= 2) {
                    if (k == 0) {
                        if (total == 0) return true;
                    } else {
                        if (total % k == 0) return true;
                    }
                }
            }
        }
        return false;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {23, 2, 4, 6, 7};
    cout << boolalpha << sol.checkSubarraySum(nums, 6) << endl; // true
    return 0;
}

Line Notes

for (int start = 0; start < n; start++) {Outer loop for subarray start

int total = 0;Initialize sum for current start

for (int end = start; end < n; end++) {Inner loop for subarray end

total += nums[end];Add current element to sum

if (end - start + 1 >= 2) {Check subarray length condition

if (k == 0) {Handle zero divisor case

if (total == 0) return true;Subarray sum zero matches k=0

if (total % k == 0) return true;Check if sum divisible by k

function checkSubarraySum(nums, k) {
    const n = nums.length;
    for (let start = 0; start < n; start++) {
        let total = 0;
        for (let end = start; end < n; end++) {
            total += nums[end];
            if (end - start + 1 >= 2) {
                if (k === 0) {
                    if (total === 0) return true;
                } else {
                    if (total % k === 0) return true;
                }
            }
        }
    }
    return false;
}

// Test
console.log(checkSubarraySum([23, 2, 4, 6, 7], 6)); // true

Line Notes

for (let start = 0; start < n; start++) {Outer loop picks subarray start

let total = 0;Reset sum for each start

for (let end = start; end < n; end++) {Inner loop picks subarray end

total += nums[end];Add current element to sum

if (end - start + 1 >= 2) {Ensure subarray length at least 2

if (k === 0) {Special case for zero divisor

if (total === 0) return true;Sum zero matches k=0

if (total % k === 0) return true;Check divisibility by k

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each can run up to n times, and sum is accumulated in O(1) per iteration, resulting in O(n^2) time. Space is constant as no extra data structures are used.

💡 For n=20, this means about 400 iterations, which is manageable, but for n=100000, it becomes 10 billion operations, which is too slow.

Interview Verdict: TLE

This approach is too slow for large inputs, so it is only useful to understand the problem and as a baseline before optimizing.

🧠

Prefix Sum with Hash Map (Remainder Tracking)

💡 This approach uses prefix sums and modular arithmetic to reduce the problem to checking if the same remainder has appeared before, enabling O(n) time complexity.

Intuition

If the sum of elements from index 0 to i has remainder r when divided by k, and the sum from 0 to j (j > i) also has remainder r, then the subarray from i+1 to j sums to a multiple of k.

Algorithm

1. Initialize a hash map to store remainder to earliest index mapping, starting with remainder 0 at index -1.
2. Iterate through nums, accumulating prefix sums.
3. Calculate current prefix sum modulo k (handle k=0 separately).
4. If this remainder has been seen before and the subarray length is at least 2, return true.
5. Otherwise, store the remainder with current index if not already stored.
6. Return false if no qualifying subarray found.

💡 The key is to track remainders and their earliest occurrence to quickly identify valid subarrays without checking all pairs.

</>

Code

def checkSubarraySum(nums, k):
    remainder_map = {0: -1}
    total = 0
    for i, num in enumerate(nums):
        total += num
        if k != 0:
            total %= k
        if total in remainder_map:
            if i - remainder_map[total] > 1:
                return True
        else:
            remainder_map[total] = i
    return False

# Driver code
if __name__ == '__main__':
    print(checkSubarraySum([23, 2, 4, 6, 7], 6))  # True

Line Notes

remainder_map = {0: -1}Initialize map with remainder 0 at index -1 to handle subarrays starting at index 0

total = 0Prefix sum accumulator

for i, num in enumerate(nums):Iterate over array with index

total += numAdd current element to prefix sum

if k != 0:Avoid modulo by zero

total %= kKeep prefix sum modulo k

if total in remainder_map:Check if this remainder was seen before

if i - remainder_map[total] > 1:Ensure subarray length at least 2

return TrueFound valid subarray

else: remainder_map[total] = iStore earliest index for this remainder

import java.util.HashMap;

public class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> remainderMap = new HashMap<>();
        remainderMap.put(0, -1);
        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            total += nums[i];
            if (k != 0) {
                total %= k;
            }
            if (remainderMap.containsKey(total)) {
                if (i - remainderMap.get(total) > 1) {
                    return true;
                }
            } else {
                remainderMap.put(total, i);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.checkSubarraySum(new int[]{23, 2, 4, 6, 7}, 6)); // true
    }
}

Line Notes

HashMap<Integer, Integer> remainderMap = new HashMap<>();Map remainder to earliest index

remainderMap.put(0, -1);Handle subarrays starting at index 0

int total = 0;Prefix sum accumulator

for (int i = 0; i < nums.length; i++) {Iterate over array

total += nums[i];Add current element

if (k != 0) { total %= k; }Modulo to keep remainder, avoid zero divisor

if (remainderMap.containsKey(total)) {Check if remainder seen before

if (i - remainderMap.get(total) > 1) {Check subarray length

return true;Found valid subarray

else { remainderMap.put(total, i); }Store earliest index for remainder

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> remainderMap;
        remainderMap[0] = -1;
        int total = 0;
        for (int i = 0; i < nums.size(); i++) {
            total += nums[i];
            if (k != 0) total %= k;
            if (remainderMap.find(total) != remainderMap.end()) {
                if (i - remainderMap[total] > 1) return true;
            } else {
                remainderMap[total] = i;
            }
        }
        return false;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {23, 2, 4, 6, 7};
    cout << boolalpha << sol.checkSubarraySum(nums, 6) << endl; // true
    return 0;
}

Line Notes

unordered_map<int, int> remainderMap;Map remainder to earliest index

remainderMap[0] = -1;Handle subarrays starting at index 0

int total = 0;Prefix sum accumulator

for (int i = 0; i < nums.size(); i++) {Iterate over array

total += nums[i];Add current element

if (k != 0) total %= k;Modulo to keep remainder, avoid zero divisor

if (remainderMap.find(total) != remainderMap.end()) {Check if remainder seen before

if (i - remainderMap[total] > 1) return true;Check subarray length

else { remainderMap[total] = i; }Store earliest index for remainder

function checkSubarraySum(nums, k) {
    const remainderMap = new Map();
    remainderMap.set(0, -1);
    let total = 0;
    for (let i = 0; i < nums.length; i++) {
        total += nums[i];
        if (k !== 0) total %= k;
        if (remainderMap.has(total)) {
            if (i - remainderMap.get(total) > 1) return true;
        } else {
            remainderMap.set(total, i);
        }
    }
    return false;
}

// Test
console.log(checkSubarraySum([23, 2, 4, 6, 7], 6)); // true

Line Notes

const remainderMap = new Map();Map remainder to earliest index

remainderMap.set(0, -1);Handle subarrays starting at index 0

let total = 0;Prefix sum accumulator

for (let i = 0; i < nums.length; i++) {Iterate over array

total += nums[i];Add current element

if (k !== 0) total %= k;Modulo to keep remainder, avoid zero divisor

if (remainderMap.has(total)) {Check if remainder seen before

if (i - remainderMap.get(total) > 1) return true;Check subarray length

else { remainderMap.set(total, i); }Store earliest index for remainder

⏱

Complexity

TimeO(n)

SpaceO(min(n, k))

Single pass through nums with constant time map operations results in O(n) time. Space depends on number of unique remainders, bounded by min(n, k).

💡 For n=100000, this approach can handle the input efficiently, unlike brute force.

Interview Verdict: Accepted

This is the optimal approach for this problem and is expected in interviews.

🧠

Prefix Sum with Hash Map (Handling Negative k and Zero k Robustly)

💡 This approach refines the previous by carefully handling negative k values and zero k, ensuring correctness in all edge cases.

Intuition

Modulo operation with negative numbers can behave differently in some languages, so normalize k and remainders to positive values to maintain correctness.

Algorithm

1. If k is negative, convert it to positive.
2. Initialize remainder map with 0 mapped to -1.
3. Iterate through nums, accumulate prefix sums.
4. Calculate remainder as (prefix sum modulo k + k) % k to ensure non-negative.
5. Check if remainder seen before with subarray length at least 2.
6. Return true if found, else false.

💡 Normalizing modulo results avoids bugs in languages where modulo of negative numbers is negative.

</>

Code

def checkSubarraySum(nums, k):
    if k < 0:
        k = -k
    remainder_map = {0: -1}
    total = 0
    for i, num in enumerate(nums):
        total += num
        if k != 0:
            total = (total % k + k) % k
        if total in remainder_map:
            if i - remainder_map[total] > 1:
                return True
        else:
            remainder_map[total] = i
    return False

# Driver code
if __name__ == '__main__':
    print(checkSubarraySum([23, 2, 4, 6, 7], 6))  # True

Line Notes

if k < 0:Normalize negative k to positive

k = -kMake k positive for consistent modulo

remainder_map = {0: -1}Initialize remainder map

total = 0Prefix sum accumulator

for i, num in enumerate(nums):Iterate over array

total += numAdd current element

total = (total % k + k) % kNormalize remainder to non-negative

if total in remainder_map:Check if remainder seen before

if i - remainder_map[total] > 1:Check subarray length

else: remainder_map[total] = iStore earliest index

import java.util.HashMap;

public class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        if (k < 0) k = -k;
        HashMap<Integer, Integer> remainderMap = new HashMap<>();
        remainderMap.put(0, -1);
        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            total += nums[i];
            if (k != 0) {
                total = ((total % k) + k) % k;
            }
            if (remainderMap.containsKey(total)) {
                if (i - remainderMap.get(total) > 1) {
                    return true;
                }
            } else {
                remainderMap.put(total, i);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.checkSubarraySum(new int[]{23, 2, 4, 6, 7}, 6)); // true
    }
}

Line Notes

if (k < 0) k = -k;Normalize negative k

HashMap<Integer, Integer> remainderMap = new HashMap<>();Map remainder to earliest index

remainderMap.put(0, -1);Handle subarrays starting at index 0

int total = 0;Prefix sum accumulator

for (int i = 0; i < nums.length; i++) {Iterate over array

total += nums[i];Add current element

total = ((total % k) + k) % k;Normalize remainder to non-negative

if (remainderMap.containsKey(total)) {Check if remainder seen before

if (i - remainderMap.get(total) > 1) {Check subarray length

else { remainderMap.put(total, i); }Store earliest index

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        if (k < 0) k = -k;
        unordered_map<int, int> remainderMap;
        remainderMap[0] = -1;
        int total = 0;
        for (int i = 0; i < nums.size(); i++) {
            total += nums[i];
            if (k != 0) {
                total = ((total % k) + k) % k;
            }
            if (remainderMap.find(total) != remainderMap.end()) {
                if (i - remainderMap[total] > 1) return true;
            } else {
                remainderMap[total] = i;
            }
        }
        return false;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {23, 2, 4, 6, 7};
    cout << boolalpha << sol.checkSubarraySum(nums, 6) << endl; // true
    return 0;
}

Line Notes

if (k < 0) k = -k;Normalize negative k

unordered_map<int, int> remainderMap;Map remainder to earliest index

remainderMap[0] = -1;Handle subarrays starting at index 0

int total = 0;Prefix sum accumulator

for (int i = 0; i < nums.size(); i++) {Iterate over array

total += nums[i];Add current element

total = ((total % k) + k) % k;Normalize remainder to non-negative

if (remainderMap.find(total) != remainderMap.end()) {Check if remainder seen before

if (i - remainderMap[total] > 1) return true;Check subarray length

else { remainderMap[total] = i; }Store earliest index

function checkSubarraySum(nums, k) {
    if (k < 0) k = -k;
    const remainderMap = new Map();
    remainderMap.set(0, -1);
    let total = 0;
    for (let i = 0; i < nums.length; i++) {
        total += nums[i];
        if (k !== 0) total = ((total % k) + k) % k;
        if (remainderMap.has(total)) {
            if (i - remainderMap.get(total) > 1) return true;
        } else {
            remainderMap.set(total, i);
        }
    }
    return false;
}

// Test
console.log(checkSubarraySum([23, 2, 4, 6, 7], 6)); // true

Line Notes

if (k < 0) k = -k;Normalize negative k

const remainderMap = new Map();Map remainder to earliest index

remainderMap.set(0, -1);Handle subarrays starting at index 0

let total = 0;Prefix sum accumulator

for (let i = 0; i < nums.length; i++) {Iterate over array

total += nums[i];Add current element

total = ((total % k) + k) % k;Normalize remainder to non-negative

if (remainderMap.has(total)) {Check if remainder seen before

if (i - remainderMap.get(total) > 1) return true;Check subarray length

else { remainderMap.set(total, i); }Store earliest index

⏱

Complexity

TimeO(n)

SpaceO(min(n, k))

Same as previous approach but with added normalization step, still linear time and space.

💡 This approach is safer in interviews to avoid subtle bugs with negative k.

Interview Verdict: Accepted

This approach is robust and recommended for production code and interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always code the prefix sum with hash map approach (Approach 2 or 3) as it is optimal and accepted. Brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	Yes	Mention only - never code
2. Prefix Sum + Hash Map	O(n)	O(min(n, k))	No	Yes	Code this approach
3. Prefix Sum + Hash Map (Robust with negative k)	O(n)	O(min(n, k))	No	Yes	Code this approach if negative k possible

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding, followed by the optimal prefix sum and hash map solution. Practice coding and testing edge cases.

How to Present

Clarify the problem constraints and what 'multiple of k' means.Describe the brute force approach and its inefficiency.Introduce prefix sums and the idea of tracking remainders with a hash map.Explain how matching remainders imply a valid subarray.Discuss edge cases like k=0 and negative k.Write clean code and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of prefix sums, modular arithmetic, hash maps, and edge case handling. They also assess your ability to optimize from brute force to linear time.

Common Follow-ups

• What if k is zero? → Handle separately by checking for consecutive zeros.
• Can this be done without extra space? → No, because we need to track remainders.
• What if negative numbers are present? → The modulo normalization handles this.
• How to find the actual subarray? → Store indices and reconstruct from remainder map.

💡 These follow-ups test your depth of understanding and ability to handle edge cases and extensions.

🔍

Pattern Recognition

When to Use

1) Problem asks for continuous subarray sums; 2) Check divisibility or multiples; 3) Constraints too large for brute force; 4) Hint towards prefix sums or modular arithmetic.

Signature Phrases

continuous subarray summultiple of ksubarray size at least two

NOT This Pattern When

Problems asking for non-continuous subsets or maximum sum subarrays without divisibility constraints.

Similar Problems

Subarray Sum Equals K - similar prefix sum and hash map techniqueLongest Subarray with Sum Divisible by K - extension to find max lengthSubarray Sums Divisible by K - counting subarrays instead of boolean check

Practice

1. Consider the following Python function to detect duplicates. What is the value of the variable seen after processing the third element in the input [2, 4, 2, 5]?

easy

A. {4, 2}

B. {2, 4, 2}

C. {2, 4, 5}

D. {2, 4}

Solution

1. Step 1: Trace the loop iterations

   After first element (2), seen = {2}. After second element (4), seen = {2, 4}. After third element (2), since 2 is already in seen, the function returns True before adding anything new.

2. Step 2: Determine seen after third element

   Because the function returns immediately upon detecting duplicate, seen remains {2, 4} at that point.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Duplicate detected at third element, no new additions after second iteration [OK]

Hint: Function returns immediately on duplicate, so seen stops growing [OK]

Common Mistakes:

• Assuming duplicate is added again to set
• Confusing order of insertion
• Misreading when return occurs

2. Consider the following Python code implementing the optimal approach for finding the intersection of two arrays. What is the final returned list when calling intersect([4,9,5], [9,4,9,8,4])?

def intersect(nums1, nums2):
    nums1.sort()
    nums2.sort()
    i, j = 0, 0
    intersection = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i] == nums2[j]:
            intersection.append(nums1[i])
            i += 1
            j += 1
        elif nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1
    return intersection

easy

A. [4, 4, 9]

B. [9, 9]

C. [4, 9]

D. [4, 9, 5]

Solution

1. Step 1: Sort both arrays

   nums1 sorted: [4,5,9], nums2 sorted: [4,4,8,9,9]

2. Step 2: Traverse with two pointers

   Compare 4 and 4 -> equal, add 4; i=1, j=1 Compare 5 and 4 -> 5>4, increment j=2 Compare 5 and 8 -> 5<8, increment i=2 Compare 9 and 8 -> 9>8, increment j=3 Compare 9 and 9 -> equal, add 9; i=3, j=4 (end)

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Intersection is [4,9] matching common elements with duplicates counted correctly [OK]

Hint: Sort arrays and advance pointers carefully [OK]

Common Mistakes:

• Off-by-one errors in pointer increments
• Including extra duplicates
• Returning unsorted results

3. Suppose the input array can contain multiple values beyond 0 and 1, but you want to find the longest contiguous subarray where the count of two specific values (say, x and y) are equal. Which modification to the prefix sum + hash map approach correctly handles this generalized problem?

hard

A. Transform array by replacing x with +1, y with -1, and ignore other values; then apply prefix sum + hash map

B. Sort the array first to group x and y, then apply prefix sum + hash map

C. Apply the original algorithm directly without changes since it works for any values

D. Use a hash map keyed by the difference of counts of x and y seen so far, updating prefix sums accordingly

Solution

1. Step 1: Understand problem generalization

   We want longest subarray where counts of x and y are equal, ignoring other values.

2. Step 2: Modify prefix sum logic

   Track difference of counts of x and y as prefix sum; use hash map keyed by this difference to find longest subarray.

3. Step 3: Why other options fail

   Transform array by replacing x with +1, y with -1, and ignore other values; then apply prefix sum + hash map ignores other values which may break continuity; Apply the original algorithm directly without changes since it works for only 0/1; Sort the array first to group x and y, then apply prefix sum + hash map sorting breaks subarray order.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Tracking count difference with hash map generalizes prefix sum approach [OK]

Hint: Track difference of counts for x and y with hash map [OK]

Common Mistakes:

• Ignoring other values breaks subarray continuity
• Applying original code without changes
• Sorting breaks contiguous subarray property

4. Suppose the problem changes: now elements from the arrays can be reused multiple times in the intersection (i.e., unlimited reuse). Which modification to the algorithm correctly handles this new requirement?

hard

A. Use a hash map to count frequencies in one array and for each element in the other array, add it to intersection if count > 0 without decrementing counts.

B. Use the same two-pointer approach but do not increment pointers when elements match, allowing reuse.

C. Use a hash map to count frequencies in one array and for each element in the other array, add it to intersection and decrement count accordingly.

D. Sort both arrays and use two pointers, but reset pointers to zero after each match to allow reuse.

Solution

1. Step 1: Understand reuse requirement

   Elements can be reused unlimited times, so counts should not be decremented after matching.

2. Step 2: Evaluate modifications

   Two-pointer approach relies on moving pointers forward, so it cannot handle reuse without complex resets. Hash map counting without decrementing counts allows unlimited reuse correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash map frequency counting without decrement handles reuse correctly [OK]

Hint: Do not decrement counts to allow reuse [OK]

Common Mistakes:

• Not changing pointer logic for reuse
• Decrementing counts incorrectly
• Resetting pointers causing infinite loops

5. Suppose the input strings can contain uppercase letters and non-alphabetic characters. Which modification to the optimal frequency counting approach correctly handles this scenario?

hard

A. Use a hash map to count frequencies of all characters without assuming a fixed alphabet.

B. Ignore non-alphabetic characters and count only lowercase letters using the fixed-size array.

C. Sort both strings and compare them after converting to lowercase.

D. Use a fixed-size array of length 26 and convert all characters to lowercase before counting.

Solution

1. Step 1: Identify limitation of fixed-size array

   Fixed array of size 26 only works for lowercase 'a'-'z'; uppercase and other chars cause index errors or incorrect counts.

2. Step 2: Use hash map for general characters

   A hash map can dynamically store counts for any character, handling uppercase and non-alphabetic safely.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash map handles arbitrary character sets correctly [OK]

Hint: Fixed arrays only work for known small alphabets [OK]

Common Mistakes:

• Assuming lowercase only
• Ignoring non-alphabetic chars silently
• Using fixed array with uppercase chars