DSA-030 · Prefix-frequency counting

Subarray Sum Equals K

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 29532 deterministic checks. Learner drafts are not executed.

Understand the problem

Count the nonempty contiguous subarrays whose sum equals k. Negative values and zeros are allowed, and equal-valued subarrays at different positions count separately.

Non-null int[] of length 0–100,000 with any signed int values; k is long between -10^14 and 10^14.
Return a long count. Empty input has zero nonempty subarrays. Prefix sums, differences, and frequencies use long.
Preserve input. Count positional intervals, not distinct sequences of values, and do not count the empty subarray.

Examples

Input: [1,1,1], k=2
Output: 2
Intervals [0,1] and [1,2] each sum to two.
Input: [0,0], k=0
Output: 3
Both singletons and the length-two interval count.
Input: [1,-1,1], k=1
Output: 3
The two 1 singletons and the full interval count; shrinking a positive-sum window is not generally valid.

Before you start

Prefix boundaries and subtraction
Multiplicity in maps and long counts

Recognize the structure

For prefix sums P, a subarray ending at the current boundary has sum k exactly when an earlier prefix equals current-k. Count how many earlier boundaries have that value. This is a frequency query, not merely a membership query.

Try before revealing

Hint 1

Express a subarray sum as two prefix sums.

Hint 2

Which earlier prefix value would make their difference equal k?

Hint 3

Count earlier occurrences, seed zero once, and query before inserting.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Accumulate every interval

For each start, extend an end index while maintaining a long sum. On [0,0], start 0 finds two matches and start 1 finds one. Running sums avoid resumming an interval, but there are still Θ(n²) intervals, so time is O(n²) with O(1) auxiliary space.

Improve the baseline

Represent interval sums as boundary differences

After reading a value, prefix is the sum through the current end. Every earlier boundary with prefix-k defines one matching nonempty interval.

Seed the boundary before the array

frequency[0]=1 represents the empty prefix boundary, allowing a matching interval starting at index 0.

Query before recording

Add frequency[prefix-k] to count before increasing frequency[prefix]. This prevents pairing the current boundary with itself when k=0.

Why it is correct

Initialize

The map contains precisely boundary 0 with sum zero, and count=0 because no nonempty interval has been processed.

Preserve

Before recording the new boundary, the map contains every strictly earlier prefix boundary with exact multiplicity. Subtraction establishes a one-to-one correspondence between each matching earlier boundary and a subarray ending here. Insertion then makes the map accurate for the next iteration.

Finish

Every nonempty subarray has one unique ending boundary and is counted only on that iteration. The finite scan therefore counts every match exactly once.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.HashMap;
import java.util.Map;

public final class Solution {
    public static long subarraySum(int[] nums, long k) {
        Map<Long, Long> frequency = new HashMap<>();
        frequency.put(0L, 1L);
        long prefix = 0, count = 0;
        for (int value : nums) {
            prefix += value;
            count += frequency.getOrDefault(prefix - k, 0L);
            frequency.merge(prefix, 1L, Long::sum);
        }
        return count;
    }

    public static long baseline(int[] nums, long k) {
        long count = 0;
        for (int start = 0; start < nums.length; start++) {
            long sum = 0;
            for (int end = start; end < nums.length; end++) {
                sum += nums[end];
                if (sum == k) count++;
            }
        }
        return count;
    }
}

Read the meaningful blocks

Use Long keys and counts

Large sums and O(n²) possible matches can exceed int even when individual elements fit.

Add multiplicity, not a boolean

Repeated prefix values represent different start boundaries.

Increment after querying

The transition order enforces nonempty intervals.

Complexity

Expected O(n) time with O(n) distinct prefix entries in the worst case. Prefix values and the result fit long under the declared bounds. Hash-table performance is expected.

Output is one long. Baseline enumerates Θ(n²) intervals in O(n²) time and O(1) auxiliary space; it also uses long sums.

Exact-state walkthroughs

Reveal normal and boundary traces

Repeated zero prefixes

Input: {"nums":[0,0],"k":0} · Result: 3

Step 1 of 6: Seed the boundary before index zero.

One empty prefix boundary exists, but no empty subarray is counted.

Prefix sum → number of earlier boundaries

0 → 1

State after this step
Variable	Value
prefix	`0`
count	`0`
frequency	`[[0,1]]`

See the affected Java block

 1 import java.util.HashMap;
 2 import java.util.Map;
 3 
 4 public final class Solution {
 5     public static long subarraySum(int[] nums, long k) {
 6         Map<Long, Long> frequency = new HashMap<>();
 7         frequency.put(0L, 1L);
 8         long prefix = 0, count = 0;
 9         for (int value : nums) {
10             prefix += value;
11             count += frequency.getOrDefault(prefix - k, 0L);
12             frequency.merge(prefix, 1L, Long::sum);
13         }
14         return count;
15     }
16 
17     public static long baseline(int[] nums, long k) {
18         long count = 0;
19         for (int start = 0; start < nums.length; start++) {
20             long sum = 0;
21             for (int end = start; end < nums.length; end++) {
22                 sum += nums[end];
23                 if (sum == k) count++;
24             }
25         }
26         return count;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed the boundary before index zero.
One empty prefix boundary exists, but no empty subarray is counted.
prefix
0
count
0
frequency
[[0,1]]
Count matching strictly earlier boundaries.
Each matched boundary defines one nonempty interval ending here.
index
0
prefix
0
needed
0
matches
1
count
1
frequency
[[0,1]]
Record this boundary for later ends.
The map now includes every prefix boundary through this index.
index
0
prefix
0
count
1
frequency
[[0,2]]
Count matching strictly earlier boundaries.
Each matched boundary defines one nonempty interval ending here.
index
1
prefix
0
needed
0
matches
2
count
3
frequency
[[0,2]]
Record this boundary for later ends.
The map now includes every prefix boundary through this index.
index
1
prefix
0
count
3
frequency
[[0,3]]
Return the contract result.
The final state satisfies the requested output contract.
result
3

Negative cancellation

Input: {"nums":[1,-1,1],"k":1} · Result: 3

Step 1 of 8: Seed the boundary before index zero.

One empty prefix boundary exists, but no empty subarray is counted.

Prefix sum → number of earlier boundaries

0 → 1

State after this step
Variable	Value
prefix	`0`
count	`0`
frequency	`[[0,1]]`

See the affected Java block

 1 import java.util.HashMap;
 2 import java.util.Map;
 3 
 4 public final class Solution {
 5     public static long subarraySum(int[] nums, long k) {
 6         Map<Long, Long> frequency = new HashMap<>();
 7         frequency.put(0L, 1L);
 8         long prefix = 0, count = 0;
 9         for (int value : nums) {
10             prefix += value;
11             count += frequency.getOrDefault(prefix - k, 0L);
12             frequency.merge(prefix, 1L, Long::sum);
13         }
14         return count;
15     }
16 
17     public static long baseline(int[] nums, long k) {
18         long count = 0;
19         for (int start = 0; start < nums.length; start++) {
20             long sum = 0;
21             for (int end = start; end < nums.length; end++) {
22                 sum += nums[end];
23                 if (sum == k) count++;
24             }
25         }
26         return count;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed the boundary before index zero.
One empty prefix boundary exists, but no empty subarray is counted.
prefix
0
count
0
frequency
[[0,1]]
Count matching strictly earlier boundaries.
Each matched boundary defines one nonempty interval ending here.
index
0
prefix
1
needed
0
matches
1
count
1
frequency
[[0,1]]
Record this boundary for later ends.
The map now includes every prefix boundary through this index.
index
0
prefix
1
count
1
frequency
[[0,1],[1,1]]
Count matching strictly earlier boundaries.
Each matched boundary defines one nonempty interval ending here.
index
1
prefix
0
needed
-1
matches
0
count
1
frequency
[[0,1],[1,1]]
Record this boundary for later ends.
The map now includes every prefix boundary through this index.
index
1
prefix
0
count
1
frequency
[[0,2],[1,1]]
Count matching strictly earlier boundaries.
Each matched boundary defines one nonempty interval ending here.
index
2
prefix
1
needed
0
matches
2
count
3
frequency
[[0,2],[1,1]]
Record this boundary for later ends.
The map now includes every prefix boundary through this index.
index
2
prefix
1
count
3
frequency
[[0,2],[1,2]]
Return the contract result.
The final state satisfies the requested output contract.
result
3

Test the contract

Input: [], k=0
Output: 0
No empty-subarray count.
Input: [3], k=3
Output: 1
Initial zero boundary.
Input: [1,-1], k=0
Output: 1
Negative cancellation.
Input: [0,0,0], k=0
Output: 6
Repeated prefixes.

Common mistakes and counterexamples

Use a set instead of frequencies

Counterexample: [0,0], k=0 needs 3 matches, not 2.

Retain multiplicities of prefix boundaries.

Omit the initial zero boundary

Counterexample: [3], k=3 loses its only interval.

Seed 0→1.

Insert before querying

Counterexample: [0], k=0 falsely counts the empty suffix.

Query earlier boundaries first.

Use int for count

Counterexample: 100,000 zeros produce 5,000,050,000 matches.

Use long for the result and frequencies.

Follow-ups

Return the longest matching interval.

Store the earliest index for each prefix value rather than its frequency. The information retained changes with the requested output.

All values are nonnegative.

A two-window count such as atMost(k)-atMost(k-1) can apply under a carefully stated integral/nonnegative contract; zeros need correct multiplicity. Arbitrary negative inputs break this monotonicity.

Count sums divisible by k.

Group prefix boundaries by normalized remainder, define k>0, and pair equal remainders. Normalize negative Java remainders before looking them up.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 98/20,000 characters

Self-review

I can explain prefix-boundary multiplicity.I query before insertion.I use long for sums and counts.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Prefix sums: boundaries and multiplicity

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-14 · Original explanations, examples, and Java implementations for AceYourInterviews. Familiar task names identify standard algorithmic problems; no company-frequency claims are made.