Continuous Subarray Sum (Multiple of K)

🎯

Continuous Subarray Sum (Multiple of K)

mediumHASH_MAPAmazonFacebookBloomberg

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.

💡 This problem is about finding continuous segments in an array whose sums have a special property (being divisible by K). Beginners often struggle because the naive approach is slow and they don't immediately see how prefix sums and remainders can simplify the problem.

📋

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

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

Outputtrue

The entire subarray [23, 2, 6, 4, 7] sums to 42, which is a multiple of 6.

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

Outputfalse

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

• k = 0 and subarray sums to 0 → true if subarray sum is zero
• nums contains negative numbers → should still work correctly
• subarray length exactly 2 → minimum valid subarray size
• k is negative → divisibility check should consider absolute value

⚠️

Common Mistakes

Not checking subarray length >= 2

Returns true for single element subarrays, which is invalid

✅ Ensure index difference > 1 when checking remainder repeats

Modulo by zero error when k=0

Runtime error or incorrect results

✅ Handle k=0 as a special case by checking if subarray sum is zero

Updating remainder map on every occurrence

Overwrites earliest index, missing longer subarrays

✅ Only store the first occurrence of each remainder

Using prefix sums without modulo leading to large numbers

Possible integer overflow or inefficiency

✅ Apply modulo operation during prefix sum calculation

Not considering negative numbers correctly

Incorrect remainder calculations

✅ Use (running_sum % k + k) % k to handle negative values

🧠

Brute Force (Nested Loops Checking All Subarrays)

💡 Starting with brute force helps understand the problem's core: checking every possible subarray. Though inefficient, it builds intuition about what we are looking for.

Intuition

Check every possible continuous subarray of length at least two and see if its sum is 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 the subarray from start to end.
4. Check if the sum is divisible by k (or zero if k is zero). If yes, return true.

💡 The nested loops and sum calculation make it clear what the problem asks, but the repeated summations make it inefficient.

</>

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

# Example usage
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 the subarray

total = 0Initialize sum for the current start index

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

total += nums[end]Accumulate sum of elements from start to end

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

if k == 0:Special case: check if sum is zero when k is 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;Initialize sum for current 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) {Handle special case when k is zero

if (total == 0) return true;Return true if sum zero and k zero

if (total % k == 0) return true;Return true if sum divisible 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 start index

int total = 0;Sum accumulator reset for each start

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

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

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

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

if (total == 0) return true;Return true if sum zero and k zero

if (total % k == 0) return true;Return true 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;
}

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

Line Notes

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

let total = 0;Reset sum for each start

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

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

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

if (k === 0) {Handle special case when k is zero

if (total === 0) return true;Return true if sum zero and k zero

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

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each can run up to n times, summing subarrays in O(1) per addition but total O(n^2) sums checked.

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

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but is essential to understand the problem and motivate better solutions.

🧠

Prefix Sum with Nested Loops (Improved Sum Calculation)

💡 This approach improves brute force by precomputing prefix sums to avoid repeated summations, teaching how to optimize naive solutions.

Intuition

Use prefix sums to calculate subarray sums in O(1) time, then check all subarrays for divisibility by k.

Algorithm

1. Compute prefix sums array where prefix[i] is sum of nums[0..i-1].
2. Iterate over all pairs (start, end) with end > start.
3. Calculate subarray sum as prefix[end+1] - prefix[start].
4. Check if subarray sum is divisible by k (or zero if k is zero). Return true if yes.

💡 This reduces repeated summations but still checks all subarrays, so it is faster but still quadratic.

</>

Code

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

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

Line Notes

prefix = [0] * (n + 1)Create prefix sums array with extra space for zero prefix

for i in range(n):Build prefix sums cumulatively

prefix[i + 1] = prefix[i] + nums[i]Prefix sum up to index i

for start in range(n):Outer loop for subarray start

for end in range(start + 1, n):Inner loop for subarray end ensuring length >= 2

total = prefix[end + 1] - prefix[start]Calculate subarray sum in O(1)

if k == 0:Handle special zero divisor case

if total % k == 0:Check divisibility by k

public class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        for (int start = 0; start < n; start++) {
            for (int end = start + 1; end < n; end++) {
                int total = prefix[end + 1] - prefix[start];
                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

int[] prefix = new int[n + 1];Prefix sums array with extra slot for zero prefix

prefix[i + 1] = prefix[i] + nums[i];Build prefix sums cumulatively

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

for (int end = start + 1; end < n; end++) {Inner loop for subarray end ensuring length >= 2

int total = prefix[end + 1] - prefix[start];Calculate subarray sum in O(1)

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

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();
        vector<int> prefix(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        for (int start = 0; start < n; ++start) {
            for (int end = start + 1; end < n; ++end) {
                int total = prefix[end + 1] - prefix[start];
                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

vector<int> prefix(n + 1, 0);Prefix sums vector with zero prefix

prefix[i + 1] = prefix[i] + nums[i];Build prefix sums cumulatively

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

for (int end = start + 1; end < n; ++end) {Inner loop for subarray end ensuring length >= 2

int total = prefix[end + 1] - prefix[start];Calculate subarray sum in O(1)

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

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

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

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

Line Notes

const prefix = new Array(n + 1).fill(0);Prefix sums array with zero prefix

prefix[i + 1] = prefix[i] + nums[i];Build prefix sums cumulatively

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

for (let end = start + 1; end < n; end++) {Inner loop for subarray end ensuring length >= 2

const total = prefix[end + 1] - prefix[start];Calculate subarray sum in O(1)

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

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

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Prefix sums reduce sum calculation to O(1), but nested loops still check O(n^2) subarrays.

💡 For n=20, this means 400 checks but faster sum calculation; still too slow for n=100000.

Interview Verdict: TLE / Better than brute force but still too slow

This approach is a stepping stone to the optimal solution, showing how prefix sums help but nested loops remain costly.

🧠

Optimal Hash Map with Prefix Sum Remainders

💡 This approach uses a hash map to track prefix sum remainders modulo k, enabling O(n) time detection of qualifying subarrays by leveraging the mathematical property of remainders.

Intuition

If two prefix sums have the same remainder when divided by k, the subarray between them 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 running sum.
3. Calculate remainder of running sum modulo k (handle k=0 separately).
4. If remainder seen before and subarray length >= 2, return true.
5. Otherwise, store remainder with current index if not already stored.
6. Return false if no qualifying subarray found.

💡 The hash map tracks where each remainder first appeared, so when it appears again, the subarray between those indices sums to a multiple of k.

</>

Code

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

# Example usage
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 from start

running_sum = 0Running sum accumulator

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

running_sum += numAdd current number to running sum

if k != 0:Avoid modulo by zero error

running_sum %= kKeep running sum modulo k

if running_sum in remainder_map:Check if remainder seen before

if i - remainder_map[running_sum] > 1:Ensure subarray length at least two

else: remainder_map[running_sum] = iStore first occurrence of this remainder

import java.util.*;

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

Map<Integer, Integer> remainderMap = new HashMap<>();Hash map to store remainder to index

remainderMap.put(0, -1);Initialize with remainder 0 at index -1

int runningSum = 0;Running sum accumulator

runningSum += nums[i];Add current element to running sum

if (k != 0) { runningSum %= k; }Modulo running sum by k if k not zero

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

if (i - remainderMap.get(runningSum) > 1) {Check subarray length at least two

else { remainderMap.put(runningSum, i); }Store first occurrence of 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 runningSum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            runningSum += nums[i];
            if (k != 0) {
                runningSum %= k;
            }
            if (remainderMap.find(runningSum) != remainderMap.end()) {
                if (i - remainderMap[runningSum] > 1) {
                    return true;
                }
            } else {
                remainderMap[runningSum] = 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;Hash map for remainder to index

remainderMap[0] = -1;Initialize with remainder 0 at index -1

int runningSum = 0;Running sum accumulator

runningSum += nums[i];Add current element to running sum

if (k != 0) { runningSum %= k; }Modulo running sum by k if k not zero

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

if (i - remainderMap[runningSum] > 1) {Check subarray length at least two

else { remainderMap[runningSum] = i; }Store first occurrence of remainder

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

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

Line Notes

const remainderMap = new Map();Hash map to store remainder to index

remainderMap.set(0, -1);Initialize with remainder 0 at index -1

let runningSum = 0;Running sum accumulator

runningSum += nums[i];Add current element to running sum

if (k !== 0) { runningSum %= k; }Modulo running sum by k if k not zero

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

if (i - remainderMap.get(runningSum) > 1) {Check subarray length at least two

else { remainderMap.set(runningSum, i); }Store first occurrence of remainder

⏱

Complexity

TimeO(n)

SpaceO(min(n, k))

Single pass through array with constant time hash map operations; space depends on distinct remainders stored.

💡 For n=100000, this means 100000 operations, which is efficient and scalable.

Interview Verdict: Accepted / Optimal solution

This is the best approach to implement in interviews due to its efficiency and elegance.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to code the optimal hash map approach after briefly explaining brute force.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Prefix Sum with Nested Loops	O(n^2)	O(n)	No	N/A	Mention as improvement over brute force
3. Optimal Hash Map with Prefix Sum Remainders	O(n)	O(min(n, k))	No	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply and practice explaining each approach clearly before your interview.

How to Present

Step 1: Clarify the problem and constraints, especially handling k=0 and subarray length.Step 2: Present brute force to show understanding of the problem.Step 3: Explain prefix sums to optimize sum calculation.Step 4: Introduce the hash map remainder approach as the optimal solution.Step 5: Code the optimal solution and test with examples.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize naive solutions, and knowledge of prefix sums and modular arithmetic.

Common Follow-ups

• What if k is zero? → Check for subarray sum zero explicitly.
• Can this be done without extra space? → No, hash map is needed for O(n) time.

💡 These follow-ups test edge case handling and space-time tradeoffs.

🔍

Pattern Recognition

When to Use

1) Problem asks for continuous subarray sums with divisibility or remainder conditions, 2) Subarray length constraints, 3) Large input size needing O(n) or O(n log n) solution, 4) Modulo or remainder operations mentioned or implied.

Signature Phrases

continuous subarray summultiple of ksum % k == 0

NOT This Pattern When

Problems asking for non-continuous subsets or maximum/minimum sums without divisibility constraints

Similar Problems

Subarray Sum Equals K - similar prefix sum usage but exact sum instead of moduloLongest Subarray with Sum Divisible by K - similar remainder trackingSubarray Sums Divisible by K - counting subarrays with remainder logic

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. Given the following Python code for summaryRanges, what is the final returned list when input is [1,2,3,5]?

from typing import List

def summaryRanges(nums: List[int]) -> List[str]:
    ranges = []
    n = len(nums)
    start = 0
    while start < n:
        end = start
        while end + 1 < n and nums[end + 1] == nums[end] + 1:
            end += 1
        if start == end:
            ranges.append(str(nums[start]))
        else:
            ranges.append(f"{nums[start]}->{nums[end]}")
        start = end + 1
    return ranges

easy

A. ['1', '2', '3', '5']

B. ['1->3', '5']

C. ['1->2', '3->5']

D. ['1->3', '5->5']

Solution

1. Step 1: Trace first range detection

   start=0 (nums[0]=1), end moves from 0 to 2 because nums[1]=2 and nums[2]=3 are consecutive.

2. Step 2: Append first range and move start

   Append '1->3', then start=3 (nums[3]=5), end=3, no consecutive next element, append '5'.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Ranges correctly summarize consecutive sequences [OK]

Hint: Two pointers expand end while consecutive -> correct ranges [OK]

Common Mistakes:

• Appending single elements as ranges like '5->5'
• Splitting consecutive sequences incorrectly
• Off-by-one errors in inner loop

3. The following code attempts to find the maximum number of pairs summing to k. Which line contains a subtle bug that can cause incorrect pair counting?

medium

A. Line 8: Incrementing freq[complement] instead of decrementing

B. Line 6: Calculating complement as k - num

C. Line 3: Initializing count to 0

D. Line 10: Incrementing freq[num] when complement not found

Solution

1. Step 1: Analyze frequency update when complement found

   When a complement is found, freq[complement] should be decremented to mark it used.

2. Step 2: Identify incorrect increment

   Line 8 increments freq[complement], which incorrectly increases available count, causing overcounting pairs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct logic requires decrementing frequency on pairing [OK]

Hint: Decrement freq on pairing, not increment [OK]

Common Mistakes:

• Incrementing freq instead of decrementing
• Forgetting to mark elements used
• Miscomputing complement

4. What is the time complexity of the optimal sliding window solution for the Minimum Operations to Reduce X to Zero problem, assuming the input array length is n?

medium

A. O(n^2) due to nested loops for adjusting window boundaries.

B. O(n) for the main loop plus O(n) for sum computations inside the loop.

C. O(n) because each element is visited at most twice by left and right pointers.

D. O(n log n) due to sorting or binary search steps.

Solution

1. Step 1: Analyze the main loop and window adjustments

   The right pointer moves from 0 to n-1 once, and the left pointer only moves forward when shrinking the window, so each element is visited at most twice.

2. Step 2: Confirm no nested loops causing quadratic time

   While loop inside the for loop advances left pointer without resetting, so total moves of left pointer ≤ n.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer sliding window runs in linear time [OK]

Hint: Sliding window moves pointers linearly [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Forgetting that left pointer only moves forward
• Confusing sum computations as extra loops

5. The following code attempts to implement summaryRanges but has a subtle bug. Which line contains the bug?

from typing import List

def summaryRanges(nums: List[int]) -> List[str]:
    ranges = []
    n = len(nums)
    start = 0
    while start < n:
        end = start
        while end + 1 < n and nums[end + 1] == nums[end] + 1:
            end += 1
        ranges.append(f"{nums[start]}->{nums[end]}")
        start = end + 1
    return ranges

medium

A. Line 7: The inner while loop condition misses the last element in some cases.

B. Line 4: Not checking if input list is empty causes crash on empty input.

C. Line 11: Updating start to end + 1 might skip elements if end is not updated correctly.

D. Line 9: Always appending 'start->end' even when start == end causes incorrect output for single elements.

Solution

1. Step 1: Identify output format issue

   When start == end, the code appends 'num->num' instead of just 'num', which is incorrect per problem spec.

2. Step 2: Confirm other lines are correct

   Inner loop condition and start update are correct; empty input handling is not shown but not the subtle bug here.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single element ranges must be output as single numbers, not ranges [OK]

Hint: Single element ranges output as 'num', not 'num->num' [OK]

Common Mistakes:

• Appending 'start->end' even when start == end
• Off-by-one in inner loop
• Skipping last range due to loop condition