What is the brute force approach and complexity for Continuous Subarray Sum?

Fix each start, grow the end from start + 1, test sum % k with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Continuous Subarray Sum?

Store the earliest index per remainder; equal remainder ≥ 2 apart ⇒ true with optimal time complexity O(N) and space complexity O(min(N, K)).

How do you identify the pattern for Continuous Subarray Sum?

Look for key signals in the prompt: "continuous subarray" indicates A range [l..r] → difference of two prefix sums.; "multiple of k" indicates Key by prefix remainder; equal remainders ⇔ divisible sum.; "length at least 2" indicates We need positions, not counts → store the index of each remainder.; "does one exist? (true/false)" indicates Keep the earliest index, since it gives the longest candidate. Return at the first success..

Continuous Subarray Sum

Medium·LeetCode #523 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given an array nums of non-negative integers and a number k.

Return true if there is a contiguous subarray of length at least 2 whose sum is a multiple of k (0 counts as a multiple of every k). Otherwise return false.

Input

An integer array nums (all values ≥ 0) and an integer k (k ≥ 1).

Output

true if some subarray with 2 or more elements has a sum divisible by k, else false.

Example 1

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

Output: true

[2, 4] has length 2 and sum 6.

Example 2

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

Output: true

The whole array sums to 42 = 7 · 6.

Example 3

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

Output: false

No subarray of length 2 or more has a sum divisible by 13. Note [6] alone is divisible by 6 in the earlier example, but length 1 never counts.

Constraints

• 1 ≤ nums.length ≤ 10^5
• 0 ≤ nums[i] ≤ 10^9
• 0 ≤ sum(nums) ≤ 2^31 − 1
• 1 ≤ k ≤ 2^31 − 1

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“continuous subarray”

→ A range [l..r] → difference of two prefix sums.

“multiple of k”

→ Key by prefix remainder; equal remainders ⇔ divisible sum.

“length at least 2”

→ We need positions, not counts → store the index of each remainder.

“does one exist? (true/false)”

→ Keep the earliest index, since it gives the longest candidate. Return at the first success.

Approach Complexity Ladder

Brute Force — try every subarray of length ≥ 2O(N²)O(1)

Fix each start, grow the end from start + 1, test sum % k

Optimal — first index of each remainderO(N)O(min(N, K))

Store the earliest index per remainder; equal remainder ≥ 2 apart ⇒ true

Brute Force Intuition

For every start, begin with that one element, then add elements one by one from start + 1. Every sum we test now has at least 2 elements. Return true the first time a sum is a multiple of k.

Recognition rule for this sub-pattern:

Sum divisible by K ⇔ two prefixes have the same remainder. Store remainders, not sums. Fix negative remainders.

Remember this · Prefix Sum

Trigger

Range sums, "subarray sum equals K" (especially with negatives), equal counts, divisible by K.

Think

If I knew the total up to every index, would the answer become a difference of two totals?

Key question

Which earlier prefix value am I looking for when I stand at index i?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Prefix Sum translate into production architectures and low-level memory mechanics.

LLD Architecture