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

Try every (start, end) pair and add the block from scratch with time complexity O(N³) and space complexity O(1).

What is the optimal approach and complexity for Subarray Sum Equals K?

count += seen[prefix − k], then seen[prefix]++ with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Subarray Sum Equals K?

Look for key signals in the prompt: "contiguous subarrays" indicates Each range sum is a difference of two prefix sums.; "sum equals k" indicates Exact target → look up `prefix − k` in a map.; "nums[i] can be negative" indicates No sliding window — the sum is not monotonic. Prefix sums do not care.; "count the subarrays" indicates Store **counts** per total, not a set or first index..

Subarray Sum Equals K

Medium·LeetCode #560 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given an integer array nums and an integer k. The numbers can be negative.

Count how many contiguous, non-empty subarrays add up to exactly k.

Input

An integer array nums and an integer k.

Output

The number of non-empty subarrays whose sum equals k.

Example 1

Input: nums = [1, 1, 1], k = 2

Output: 2

[1, 1] at indices 0..1 and [1, 1] at indices 1..2.

Example 2

Input: nums = [1, 2, 3], k = 3

Output: 2

[1, 2] (0..1) and [3] (index 2).

Constraints

• 1 ≤ nums.length ≤ 2 · 10^4
• −1000 ≤ nums[i] ≤ 1000
• −10^7 ≤ k ≤ 10^7

Pattern Recognition Clues

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

“contiguous subarrays”

→ Each range sum is a difference of two prefix sums.

“sum equals k”

→ Exact target → look up `prefix − k` in a map.

“nums[i] can be negative”

→ No sliding window — the sum is not monotonic. Prefix sums do not care.

“count the subarrays”

→ Store **counts** per total, not a set or first index.

Approach Complexity Ladder

Brute Force — sum every subarrayO(N³)O(1)

Try every (start, end) pair and add the block from scratch

Better — prefix array, every pairO(N²)O(N)

Precompute prefix sums; each block sum is one subtraction

Optimal — prefix sum + hash mapO(N)O(N)

count += seen[prefix − k], then seen[prefix]++

Brute Force Intuition

Try every start and every end, add up nums[start..end] with a third loop, and count the pairs whose sum is k.

Recognition rule for this sub-pattern:

Contiguous + exact sum, negatives allowed. Store how many times each prefix sum appeared; look up prefix − K.

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