How do you solve Continuous Subarray Sum on LeetCode?

Continuous Subarray Sum (LeetCode #523) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The sum of a subarray being a multiple of k can be efficiently tracked using cumulative sums and their remainders.

What is the brute force solution for Continuous Subarray Sum?

The brute force approach for Continuous Subarray Sum is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible subarray of size at least two to see if its sum is a multiple of k. This is straightforward but inefficient for larger arrays. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Continuous Subarray Sum?

Continuous Subarray Sum uses the following concepts: Array, Hash Table, Math, Prefix Sum. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Continuous Subarray Sum?

Always clarify edge cases, such as what to do when k is 0. Think about how you can reduce time complexity by using data structures like HashMaps. Practice explaining your thought process as you code, as it helps interviewers understand your reasoning.

What are common mistakes when solving Continuous Subarray Sum?

Not considering the case when k is 0, which can lead to division errors. Failing to check the length of the subarray before returning true.

#523

Continuous Subarray Sum

Medium

ArrayHash TableMathPrefix SumHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a HashMap to store the cumulative sum modulo k. This allows us to check for previously seen remainders, which indicates that the sum of elements between those indices is a multiple of k.

⚙️

Algorithm

4 steps

1Step 1: Initialize a HashMap to store the remainder of cumulative sums and their indices.
2Step 2: Iterate through the array while maintaining a cumulative sum and calculating its modulo k.
3Step 3: If the same remainder has been seen before and the distance between indices is at least 2, return true.
4Step 4: If the remainder is not in the HashMap, store it with the current index.

solution.py15 lines

1# Full working Python code
2
3def checkSubarraySum(nums, k):
4    sum_map = {0: -1}
5    total = 0
6    for i in range(len(nums)):
7        total += nums[i]
8        if k != 0:
9            total %= k
10        if total in sum_map:
11            if i - sum_map[total] > 1:
12                return True
13        else:
14            sum_map[total] = i
15    return False

ℹ

Complexity note: The time complexity is linear because we only pass through the array once, and the space complexity is linear due to the HashMap storing remainders.

1The sum of a subarray being a multiple of k can be efficiently tracked using cumulative sums and their remainders.
2Using a HashMap allows us to check for previously seen remainders, reducing the need for nested loops.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.