LeetCode 523: Continuous Subarray Sum Solution in Python – A Step-by-Step Guide

What Is LeetCode 523: Continuous Subarray Sum?

In LeetCode 523: Continuous Subarray Sum, you’re given an array of integers nums and an integer k, and your task is to determine if there exists a continuous subarray of length at least 2 whose sum is a multiple of k (including 0). For example, with nums = [23, 2, 4, 6, 7] and k = 6, the subarray [2, 4] sums to 6 (a multiple of 6), so return True. This problem tests prefix sums and modular arithmetic, related to LeetCode 560: Subarray Sum Equals K.

Problem Statement

• Input:
• nums (List[int]): Array of integers.
• k (int): Target multiple.
• Output: Boolean—True if a valid subarray exists, False otherwise.
• Rules: Subarray must be continuous, length ≥ 2, sum divisible by k.

Constraints

• 1 <= nums.length <= 10⁵
• 0 <= nums[i] <= 10⁹
• 0 <= sum(nums[i]) <= 2³¹ - 1
• 1 <= k <= 2³¹ - 1

Examples

• Input: nums = [23,2,4,6,7], k = 6
• Output: True
• [2, 4] sums to 6 (6 % 6 = 0).
• Input: nums = [23,2,6,4,7], k = 6
• Output: True
• [23, 2, 6, 4, 7] sums to 42 (42 % 6 = 0).
• Input: nums = [23,2,6,4,7], k = 13
• Output: False
• No subarray sums to a multiple of 13.

Understanding the Problem: Finding a Multiple Sum

To solve LeetCode 523: Continuous Subarray Sum in Python, we need to find a contiguous subarray of at least two elements whose sum is divisible by k. A naive approach might check every possible subarray, but with up to 10⁵ elements, that’s too slow. We’ll explore:

• Best Solution (Prefix Sum with Hash Map): O(n) time, O(n) space—efficient and smart.
• Alternative Solution (Brute-Force Subarray Check): O(n²) time, O(1) space—simple but slow.

Let’s dive into the prefix sum solution with a friendly breakdown!

Best Solution: Prefix Sum with Hash Map

Why Prefix Sum Wins

The prefix sum with hash map is the best for LeetCode 523 because it reduces the problem to finding two prefix sums with the same remainder modulo k, ensuring a subarray sum is a multiple of k, in O(n) time and O(n) space. It’s like tracking running totals and spotting matching checkpoints!

How It Works

Think of this as a sum-tracking journey:

• Step 1: Compute Prefix Sums:
• prefix[i] = sum of elements from 0 to i.
• Step 2: Use Modulo:
• For subarray nums[i:j+1], sum = prefix[j] - prefix[i-1].
• If sum % k = 0, then (prefix[j] - prefix[i-1]) % k = 0, so prefix[j] % k = prefix[i-1] % k.
• Step 3: Hash Map:
• Store remainders of prefix sums; if a remainder repeats with distance ≥ 2, found a subarray.
• Handle k=0 separately or normalize remainders.
• Step 4: Return:
• True if valid subarray found, False otherwise.
• Why It Works:
• Same remainder means difference is a multiple of k.
• Tracks indices for length check.

It’s like a modulo sum detector!

Step-by-Step Example

Example: nums = [23, 2, 4, 6, 7], k = 6

• Init: remainder_map = {0: -1}, prefix_sum = 0.
• Step 1: Iterate with prefix sums:
• i=0: 23, prefix_sum = 23, 23 % 6 = 5, remainder_map = {0: -1, 5: 0}.
• i=1: 2, prefix_sum = 25, 25 % 6 = 1, remainder_map = {0: -1, 5: 0, 1: 1}.
• i=2: 4, prefix_sum = 29, 29 % 6 = 5, remainder_map[5] = 0, length = 2-0 = 2 ≥ 2, return True.
• Result: True ([2, 4] sums to 6).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        # Step 1: Initialize hash map with remainder 0 at -1
        remainder_map = {0: -1}  # Key: remainder, Value: index
        prefix_sum = 0

        # Step 2: Iterate through array
        for i in range(len(nums)):
            # Update prefix sum
            prefix_sum += nums[i]

            # Step 3: Handle k = 0 case and compute remainder
            if k != 0:
                prefix_sum %= k

            # Step 4: Check if remainder seen before
            if i - remainder_map.get(prefix_sum, i) >= 2:
                return True
            if prefix_sum not in remainder_map:
                remainder_map[prefix_sum] = i

        # Step 5: No valid subarray found
        return False

• Line 4: Map starts with 0 at -1 (empty sum).
• Line 5: Running prefix sum.
• Lines 8-12: Add current number; if k ≠ 0, take modulo.
• Lines 15-17: If remainder seen and length ≥ 2, return True; else store index.
• Line 20: Default to False.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(n)—hash map size.

It’s like a prefix sum sleuth!

Alternative Solution: Brute-Force Subarray Check

Why an Alternative Approach?

The brute-force solution checks every possible contiguous subarray, summing and testing divisibility by k. It’s O(n²) time and O(1) space—intuitive but inefficient for large arrays. Great for understanding the raw process!

How It Works

Picture this as a subarray sweep:

• Step 1: For each start index i, check all subarrays ending at j.
• Step 2: Compute sum, check if multiple of k, and length ≥ 2.
• Step 3: Return True if found, False otherwise.

It’s like a subarray sum scanner!

Step-by-Step Example

Example: nums = [23, 2, 4], k = 6

• Step 1: Check subarrays:
• i=0: [23], [23,2], [23,2,4].
• 23 % 6 ≠ 0.
• 25 % 6 ≠ 0.
• 29 % 6 ≠ 0.
• i=1: [2], [2,4].
• 2 % 6 ≠ 0.
• 6 % 6 = 0, length = 2, return True.
• Result: True.

Code for Brute-Force Approach

Copy codeclass Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        n = len(nums)

        # Step 1: Check all subarrays
        for i in range(n):
            curr_sum = nums[i]
            for j in range(i + 1, n):
                curr_sum += nums[j]
                if (k == 0 and curr_sum == 0) or (k != 0 and curr_sum % k == 0):
                    return True

        # Step 2: No valid subarray
        return False

• Lines 6-10: Nested loops for subarrays, check sum divisibility.
• Line 12: Default to False.
• Time Complexity: O(n²)—check all subarrays.
• Space Complexity: O(1)—just a variable.

It’s a slow sum checker!

Comparing the Two Solutions

• Prefix Sum (Best):
• Pros: O(n), O(n), efficient.
• Cons: Hash map logic.
• Brute-Force (Alternative):
• Pros: O(n²), O(1), simple.
• Cons: Too slow for large arrays.

Prefix sum wins for speed!

Additional Examples and Edge Cases

• [1, 2], k = 0: False (no length ≥ 2 sums to 0).
• [0, 0], k = 0: True (0+0 = 0).
• [1], k = 1: False (length < 2).

Prefix sum handles them all!

Complexity Recap

• Prefix Sum: Time O(n), Space O(n).
• Brute-Force: Time O(n²), Space O(1).

Prefix sum’s the efficiency star!

Key Takeaways

• Prefix Sum: Modulo magic—learn at Python Basics!
• Brute Force: Straightforward but costly.
• Arrays: Subarray sums are fun.
• Python: Hash maps shine!

Final Thoughts: Sum That Subarray!

LeetCode 523: Continuous Subarray Sum in Python is a clever array challenge. Prefix sum with hash map is your fast track, while brute force shows the basics. Want more? Try LeetCode 560: Subarray Sum Equals K or LeetCode 974: Subarray Sums Divisible by K. Ready to sum? Head to Solve LeetCode 523 on LeetCode and find that multiple today!