Subarray problems are among the most common problems in DSA.
And they are also among the easiest to overcomplicate.
You are given an array and asked something like:
Find the maximum sum of a subarray.
or:
Find the maximum product of a subarray.
or:
Count how many subarrays have sum equal to K.
At first, the natural thought is:
“I’ll generate every subarray and check it.”
That works.
Until the interviewer changes the input size.
Then your beautiful nested loops become an O(n²) monument to unnecessary suffering.
The important thing is that these problems are not all solved by one technique.
There are a few recurring patterns:
Maximum Sum
↓
Kadane's Algorithm
Maximum Product
↓
Track Maximum + Minimum
Count Subarrays with Sum K
↓
Prefix Sum + HashMap
Count Subarrays with XOR K
↓
Prefix XOR + HashMap
Enter fullscreen mode Exit fullscreen mode
The goal of this chapter is not to make you memorize four different pieces of code.
The goal is to understand why each technique works.
Once the reasoning becomes clear, the code becomes almost boring.
And boring code is usually a good sign.
1. Kadane’s Algorithm
The Problem
Given an integer array, find the contiguous subarray with the maximum sum.
This is the classic:
LeetCode 53 — Maximum Subarray
Consider:
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
Enter fullscreen mode Exit fullscreen mode
The answer is:
[4, -1, 2, 1]
Enter fullscreen mode Exit fullscreen mode
Its sum is:
4 + (-1) + 2 + 1 = 6
Enter fullscreen mode Exit fullscreen mode
So the answer is:
6
Enter fullscreen mode Exit fullscreen mode
There is one important word here:
contiguous
Kadane’s Algorithm works on a subarray, not a subsequence.
For example:
[4, -1, 2, 1]
Enter fullscreen mode Exit fullscreen mode
is valid because the elements are next to each other.
But something like:
[4, 2, 1]
Enter fullscreen mode Exit fullscreen mode
by skipping -1 would be a subsequence, not the original contiguous subarray.
That distinction matters.
Why Not Just Generate Every Subarray?
Take a smaller example:
[2, -1, 3]
Enter fullscreen mode Exit fullscreen mode
Possible subarrays are:
[2]
[2, -1]
[2, -1, 3]
[-1]
[-1, 3]
[3]
Enter fullscreen mode Exit fullscreen mode
We can calculate every sum and keep the largest.
In Java:
class Solution {
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
max = Math.max(max, sum);
}
}
return max;
}
}
Enter fullscreen mode Exit fullscreen mode
This solution is correct.
But what is the complexity?
Time = O(n²)
Space = O(1)
Enter fullscreen mode Exit fullscreen mode
For a small array, no problem.
For a very large array, not so pleasant.
So let’s ask the important question:
Are we recalculating information that we already know?
Yes.
The Key Observation
Consider:
[4, -2, 5, -1]
Enter fullscreen mode Exit fullscreen mode
Start from the first element and keep a running sum:
4
4 + (-2) = 2
2 + 5 = 7
7 + (-1) = 6
Enter fullscreen mode Exit fullscreen mode
So:
4 → 2 → 7 → 6
Enter fullscreen mode Exit fullscreen mode
When we reached:
7
Enter fullscreen mode Exit fullscreen mode
we already knew the best sum of a subarray ending at the current position.
There is no reason to throw all that information away and start calculating again from scratch.
This leads to the central question:
Should I continue the current subarray, or should I start a new one?
That is Kadane’s Algorithm.
The Core Idea of Kadane’s Algorithm
We maintain two pieces of information:
currentSum
maximumSum
Enter fullscreen mode Exit fullscreen mode
currentSum means:
The best subarray sum ending at the current position.
maximumSum means:
The best answer seen anywhere so far.
For every number:
currentSum += nums[i]
Enter fullscreen mode Exit fullscreen mode
Then:
maximumSum = max(maximumSum, currentSum)
Enter fullscreen mode Exit fullscreen mode
And now comes the important decision.
If:
currentSum < 0
Enter fullscreen mode Exit fullscreen mode
we throw it away.
Why?
Because a negative running sum can only hurt a future positive element.
Think of It Like Carrying a Bag
Imagine your current subarray is a bag.
Suppose you currently have:
+4
-2
+5
Enter fullscreen mode Exit fullscreen mode
Your bag contains:
7
Enter fullscreen mode Exit fullscreen mode
You want to keep carrying that because it is helping your total.
Now imagine someone puts:
-100
Enter fullscreen mode Exit fullscreen mode
inside.
Your total becomes:
7 - 100 = -93
Enter fullscreen mode Exit fullscreen mode
Now ask:
Is this baggage useful for the next element?
No.
If tomorrow you see:
+10
Enter fullscreen mode Exit fullscreen mode
you are better off starting with:
10
Enter fullscreen mode Exit fullscreen mode
instead of:
-93 + 10 = -83
Enter fullscreen mode Exit fullscreen mode
So:
negative running sum
↓
throw it away
↓
start fresh
Enter fullscreen mode Exit fullscreen mode
That is the intuition behind Kadane’s Algorithm.
Kadane’s Algorithm
The steps are:
1. Add the current number to currentSum.
2. Update maximumSum.
3. If currentSum becomes negative, reset it to 0.
4. Continue.
Enter fullscreen mode Exit fullscreen mode
In compact form:
currentSum += num
maximumSum = max(maximumSum, currentSum)
if currentSum < 0
currentSum = 0
Enter fullscreen mode Exit fullscreen mode
Java Implementation
class Solution {
public int maxSubArray(int[] nums) {
int currentSum = 0;
int maxSum = Integer.MIN_VALUE;
for (int num : nums) {
currentSum += num;
maxSum = Math.max(maxSum, currentSum);
if (currentSum < 0) {
currentSum = 0;
}
}
return maxSum;
}
}
Enter fullscreen mode Exit fullscreen mode
Notice something very important.
We update:
maxSum
Enter fullscreen mode Exit fullscreen mode
before resetting currentSum.
That detail matters.
We will see why in a moment.
Dry Run
Consider the LeetCode example:
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
Enter fullscreen mode Exit fullscreen mode
Let’s track three things:
Current Number
Current Sum
Maximum Sum
Enter fullscreen mode Exit fullscreen mode
Number Current Sum Maximum -2 -2 -2 1 1 1 -3 -2 1 4 4 4 -1 3 4 2 5 5 1 6 6 -5 1 6 4 5 6So the final answer is:
6
Enter fullscreen mode Exit fullscreen mode
The subarray producing it is:
[4, -1, 2, 1]
Enter fullscreen mode Exit fullscreen mode
The important moment happens when currentSum becomes negative.
For example:
4 + (-1) + 2 + 1 + (-5)
Enter fullscreen mode Exit fullscreen mode
gives:
1
Enter fullscreen mode Exit fullscreen mode
It is still positive, so we keep it.
If it had become negative, we would have discarded the entire running sum.
The All-Negative Case
This is one of the most common Kadane mistakes.
Consider:
[-5, -2, -8]
Enter fullscreen mode Exit fullscreen mode
The correct answer is:
-2
Enter fullscreen mode Exit fullscreen mode
But look at our reset rule.
If we reset every negative sum to zero, someone might accidentally write:
int maxSum = 0;
Enter fullscreen mode Exit fullscreen mode
Then the answer would become:
0
Enter fullscreen mode Exit fullscreen mode
which is wrong.
There is no empty subarray here.
The answer must come from an actual element.
That is why we initialize:
int maxSum = Integer.MIN_VALUE;
Enter fullscreen mode Exit fullscreen mode
and update maxSum before resetting currentSum.
Dry run:
current = -5
max = -5
reset
current = -2
max = -2
reset
current = -8
max = -2
reset
Enter fullscreen mode Exit fullscreen mode
Final answer:
-2
Enter fullscreen mode Exit fullscreen mode
Correct.
Common Kadane Mistakes
Mistake 1: maxSum = 0
Wrong:
int maxSum = 0;
Enter fullscreen mode Exit fullscreen mode
This fails for:
[-3, -5, -1]
Enter fullscreen mode Exit fullscreen mode
because it would return:
0
Enter fullscreen mode Exit fullscreen mode
instead of:
-1
Enter fullscreen mode Exit fullscreen mode
Use:
int maxSum = Integer.MIN_VALUE;
Enter fullscreen mode Exit fullscreen mode
Mistake 2: Resetting Before Updating Maximum
Wrong:
if (currentSum < 0) {
currentSum = 0;
}
maxSum = Math.max(maxSum, currentSum);
Enter fullscreen mode Exit fullscreen mode
For all-negative arrays, this can lose the actual answer.
Correct:
maxSum = Math.max(maxSum, currentSum);
if (currentSum < 0) {
currentSum = 0;
}
Enter fullscreen mode Exit fullscreen mode
Mistake 3: Thinking Kadane Finds a Subsequence
It doesn’t.
Kadane finds the maximum sum of a contiguous subarray.
Kadane Complexity
Time = O(n)
Space = O(1)
Enter fullscreen mode Exit fullscreen mode
This is the major improvement:
Brute Force → O(n²)
Kadane → O(n)
Enter fullscreen mode Exit fullscreen mode
One pass through the array.
No extra array.
No nested loops.
Very little code.
This is exactly the kind of optimization interviewers like.
How to Recognize Kadane’s Algorithm
Look for phrases such as:
Maximum subarray sum
Largest contiguous sum
Maximum continuous segment
Best contiguous interval
Maximum gain over a continuous range
Enter fullscreen mode Exit fullscreen mode
Think:
Kadane's Algorithm
Enter fullscreen mode Exit fullscreen mode
2. Maximum Product Subarray
Now let’s make the problem slightly nastier.
Because apparently maximum sum wasn’t difficult enough.
The problem:
Find the contiguous subarray having the maximum product.
This is:
LeetCode 152 — Maximum Product Subarray
Example:
[2, 3, -2, 4]
Enter fullscreen mode Exit fullscreen mode
Possible products include:
2 = 2
2 × 3 = 6
2 × 3 × -2 = -12
2 × 3 × -2 × 4 = -48
3 = 3
3 × -2 = -6
3 × -2 × 4 = -24
-2 = -2
-2 × 4 = -8
4 = 4
Enter fullscreen mode Exit fullscreen mode
The maximum product is:
6
Enter fullscreen mode Exit fullscreen mode
from:
[2, 3]
Enter fullscreen mode Exit fullscreen mode
At first glance, this looks like Kadane.
It is not.
And this is a very important distinction.
Why Doesn’t Normal Kadane Work?
Kadane works beautifully for sums because:
negative + positive
Enter fullscreen mode Exit fullscreen mode
usually makes the running sum worse.
For example:
5 + (-8) = -3
Enter fullscreen mode Exit fullscreen mode
So throwing away a negative running sum makes sense.
But multiplication behaves differently.
Consider:
-2 × -3 = 6
Enter fullscreen mode Exit fullscreen mode
Two negative values create a positive value.
Suddenly a negative product that looked useless can become the best answer later.
Consider:
[-2, 3, -4]
Enter fullscreen mode Exit fullscreen mode
The complete product is:
(-2) × 3 × (-4)
Enter fullscreen mode Exit fullscreen mode
which equals:
24
Enter fullscreen mode Exit fullscreen mode
If you discarded the negative product when it appeared, you would never discover 24.
So:
For maximum product, a negative value is not automatically bad.
It may be extremely useful later.
The Key Observation
There are three important multiplication rules:
Positive × Positive
↓
Positive
Enter fullscreen mode Exit fullscreen mode
Negative × Positive
↓
Negative
Enter fullscreen mode Exit fullscreen mode
Negative × Negative
↓
Positive
Enter fullscreen mode Exit fullscreen mode
Therefore:
A very small negative product today can become the largest positive product tomorrow.
This is the core idea behind Maximum Product Subarray.
So What Do We Track?
For Kadane’s sum problem, we only need:
currentSum
Enter fullscreen mode Exit fullscreen mode
For product, we need:
currentMax
currentMin
Enter fullscreen mode Exit fullscreen mode
Why?
Because:
currentMax × negative
Enter fullscreen mode Exit fullscreen mode
can become negative.
But:
currentMin × negative
Enter fullscreen mode Exit fullscreen mode
can become positive.
So the minimum is just as important as the maximum.
This is the central insight:
Today’s minimum can become tomorrow’s maximum.
Example
Consider:
[-2, 3, -4]
Enter fullscreen mode Exit fullscreen mode
Initially:
currentMax = -2
currentMin = -2
answer = -2
Enter fullscreen mode Exit fullscreen mode
Now process 3.
Possible products are:
3
-2 × 3 = -6
-2 × 3 = -6
Enter fullscreen mode Exit fullscreen mode
So:
currentMax = 3
currentMin = -6
Enter fullscreen mode Exit fullscreen mode
Now process -4.
Possible maximum values are:
-4
3 × -4 = -12
-6 × -4 = 24
Enter fullscreen mode Exit fullscreen mode
So:
currentMax = 24
Enter fullscreen mode Exit fullscreen mode
And there is the answer.
Notice where it came from:
currentMin
Enter fullscreen mode Exit fullscreen mode
That is exactly why we track both.
The Three Possibilities
For every new number num, a new subarray ending here can come from three possibilities:
1. Start fresh
num
Enter fullscreen mode Exit fullscreen mode
2. Extend the previous maximum product
num × currentMax
Enter fullscreen mode Exit fullscreen mode
3. Extend the previous minimum product
num × currentMin
Enter fullscreen mode Exit fullscreen mode
Therefore:
newMax =
max(
num,
num × currentMax,
num × currentMin
)
Enter fullscreen mode Exit fullscreen mode
And:
newMin =
min(
num,
num × currentMax,
num × currentMin
)
Enter fullscreen mode Exit fullscreen mode
This is the entire idea.
Why Do We Need Temporary Variables?
Suppose:
currentMax = ...
currentMin = ...
Enter fullscreen mode Exit fullscreen mode
You calculate the new currentMax.
Now if you calculate currentMin using the updated currentMax, you have accidentally mixed the old state with the new state.
That is wrong.
So save the previous maximum:
int tempMax = currentMax;
Enter fullscreen mode Exit fullscreen mode
Then use:
tempMax
Enter fullscreen mode Exit fullscreen mode
when calculating the new minimum.
Java Implementation
class Solution {
public int maxProduct(int[] nums) {
int currentMax = nums[0];
int currentMin = nums[0];
int answer = nums[0];
for (int i = 1; i < nums.length; i++) {
int num = nums[i];
int tempMax = currentMax;
currentMax = Math.max(
num,
Math.max(
num * currentMax,
num * currentMin
)
);
currentMin = Math.min(
num,
Math.min(
num * tempMax,
num * currentMin
)
);
answer = Math.max(answer, currentMax);
}
return answer;
}
}
Enter fullscreen mode Exit fullscreen mode
A Cleaner Version: Swap on Negative
There is another way to understand the same idea.
When:
num < 0
Enter fullscreen mode Exit fullscreen mode
maximum and minimum switch roles.
Why?
Suppose:
max = 5
min = -3
Enter fullscreen mode Exit fullscreen mode
Multiply both by -2:
5 × -2 = -10
-3 × -2 = 6
Enter fullscreen mode Exit fullscreen mode
The old minimum became the new maximum.
So when the current number is negative, we can simply swap:
if (nums[i] < 0) {
int temp = max;
max = min;
min = temp;
}
Enter fullscreen mode Exit fullscreen mode
Then calculate normally.
Recommended Java Version
class Solution {
public int maxProduct(int[] nums) {
int max = nums[0];
int min = nums[0];
int ans = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] < 0) {
int temp = max;
max = min;
min = temp;
}
max = Math.max(nums[i], max * nums[i]);
min = Math.min(nums[i], min * nums[i]);
ans = Math.max(ans, max);
}
return ans;
}
}
Enter fullscreen mode Exit fullscreen mode
This version captures the idea very nicely.
When the sign flips:
maximum ↔ minimum
Enter fullscreen mode Exit fullscreen mode
and then the calculation continues.
Common Mistakes in Maximum Product
Mistake 1: Applying Kadane Directly
You may be tempted to do:
if (product < 0) {
product = 1;
}
Enter fullscreen mode Exit fullscreen mode
That does not work.
A negative product can later become the maximum.
Mistake 2: Tracking Only Maximum
You must track:
maximum
AND
minimum
Enter fullscreen mode Exit fullscreen mode
Because:
minimum × negative
Enter fullscreen mode Exit fullscreen mode
can become maximum.
Mistake 3: Forgetting the Negative Swap
When:
num < 0
Enter fullscreen mode Exit fullscreen mode
the roles of maximum and minimum change.
Mistake 4: Initializing With 1
Do not blindly write:
int max = 1;
Enter fullscreen mode Exit fullscreen mode
Consider:
[-5]
Enter fullscreen mode Exit fullscreen mode
The answer is:
-5
Enter fullscreen mode Exit fullscreen mode
So initialize using:
nums[0]
Enter fullscreen mode Exit fullscreen mode
Complexity
Time = O(n)
Space = O(1)
Enter fullscreen mode Exit fullscreen mode
Again, one pass.
The interesting part is not the complexity.
It is the state we decided to maintain.
For maximum sum:
one state
Enter fullscreen mode Exit fullscreen mode
For maximum product:
two states
Enter fullscreen mode Exit fullscreen mode
That is an important general DSA lesson:
The trick is often not finding a faster loop. It is deciding what information the loop needs to remember.
How to Recognize Maximum Product Problems
Look for:
Maximum product
Product of a contiguous subarray
Continuous product
Negative numbers
Enter fullscreen mode Exit fullscreen mode
Think:
Track maximum AND minimum
Enter fullscreen mode Exit fullscreen mode
3. Counting Subarrays With a Given Sum
Now let’s solve a different kind of question.
Until now, we asked:
What is the maximum?
Enter fullscreen mode Exit fullscreen mode
Now we ask:
How many subarrays have sum exactly equal to K?
This difference is important.
We are counting.
Consider:
nums = [1, 1, 1]
k = 2
Enter fullscreen mode Exit fullscreen mode
Valid subarrays are:
[1, 1]
[1, 1]
Enter fullscreen mode Exit fullscreen mode
So the answer is:
2
Enter fullscreen mode Exit fullscreen mode
This is:
LeetCode 560 — Subarray Sum Equals K
Brute Force
The easiest solution is to generate every subarray and calculate its sum.
class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (sum == k) {
count++;
}
}
}
return count;
}
}
Enter fullscreen mode Exit fullscreen mode
Complexity:
Time = O(n²)
Space = O(1)
Enter fullscreen mode Exit fullscreen mode
So again:
Can we do better?
Yes.
This time Prefix Sum will work together with a HashMap.
Prefix Sum Gives Us an Equation
Suppose:
prefix[right]
Enter fullscreen mode Exit fullscreen mode
is the sum from the beginning to right.
For a subarray:
left → right
Enter fullscreen mode Exit fullscreen mode
its sum is:
prefix[right] - prefix[left - 1]
Enter fullscreen mode Exit fullscreen mode
If we want the sum to equal K:
prefix[right] - prefix[left - 1] = K
Enter fullscreen mode Exit fullscreen mode
Rearrange:
prefix[left - 1] = prefix[right] - K
Enter fullscreen mode Exit fullscreen mode
This is the entire algorithm.
Do not memorize the code.
Memorize this equation.
What Does the Equation Mean?
Suppose the current prefix sum is:
10
Enter fullscreen mode Exit fullscreen mode
and:
K = 6
Enter fullscreen mode Exit fullscreen mode
Then we need:
10 - 6 = 4
Enter fullscreen mode Exit fullscreen mode
So we ask:
Have I seen a prefix sum equal to 4 before?
If yes, then the elements between that previous prefix and the current position have sum 6.
That is how we find valid subarrays without generating them one by one.
Why Use a HashMap?
Because we repeatedly need to ask:
Have I seen this prefix sum before?
A HashMap gives us approximately:
O(1)
Enter fullscreen mode Exit fullscreen mode
lookup time.
But there is one more important detail.
We don’t just store whether a prefix sum exists.
We store:
frequency
Enter fullscreen mode Exit fullscreen mode
Why?
Because the same prefix sum may occur multiple times.
And every occurrence can produce another valid subarray.
So the map looks like:
prefix sum → frequency
Enter fullscreen mode Exit fullscreen mode
The Famous map.put(0, 1)
The code starts with:
map.put(0, 1);
Enter fullscreen mode Exit fullscreen mode
This line looks mysterious until you understand what it represents.
It means:
Before the array starts, we have seen a prefix sum of 0 exactly once.
Consider:
nums = [2, 3]
k = 5
Enter fullscreen mode Exit fullscreen mode
Prefix sums:
2
5
Enter fullscreen mode Exit fullscreen mode
At the second element:
currentPrefix = 5
Enter fullscreen mode Exit fullscreen mode
We need:
5 - 5 = 0
Enter fullscreen mode Exit fullscreen mode
Where did that 0 come from?
It represents the empty prefix before index 0.
Without:
map.put(0, 1);
Enter fullscreen mode Exit fullscreen mode
we would miss subarrays that start at index 0.
This is one of the most important details in the entire pattern.
Dry Run: [1, 1, 1], K = 2
Initially:
prefix = 0
count = 0
map = {0 : 1}
Enter fullscreen mode Exit fullscreen mode
First number: 1
prefix = 1
Enter fullscreen mode Exit fullscreen mode
Need:
1 - 2 = -1
Enter fullscreen mode Exit fullscreen mode
Not found.
Store:
1 → 1
Enter fullscreen mode Exit fullscreen mode
Map becomes:
{0:1, 1:1}
Enter fullscreen mode Exit fullscreen mode
Second number: 1
prefix = 2
Enter fullscreen mode Exit fullscreen mode
Need:
2 - 2 = 0
Enter fullscreen mode Exit fullscreen mode
Found.
How many times?
1
Enter fullscreen mode Exit fullscreen mode
So:
count = 1
Enter fullscreen mode Exit fullscreen mode
Store prefix 2.
Third number: 1
prefix = 3
Enter fullscreen mode Exit fullscreen mode
Need:
3 - 2 = 1
Enter fullscreen mode Exit fullscreen mode
Prefix 1 exists.
So:
count = 2
Enter fullscreen mode Exit fullscreen mode
Final answer:
2
Enter fullscreen mode Exit fullscreen mode
Exactly correct.
Java Solution
class Solution {
public int subarraySum(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int prefix = 0;
int count = 0;
for (int num : nums) {
prefix += num;
if (map.containsKey(prefix - k)) {
count += map.get(prefix - k);
}
map.put(
prefix,
map.getOrDefault(prefix, 0) + 1
);
}
return count;
}
}
Enter fullscreen mode Exit fullscreen mode
A More Detailed Dry Run
Take:
nums = [1, 2, 3]
k = 3
Enter fullscreen mode Exit fullscreen mode
Number Prefix Needprefix-k
Found?
Count
1
1
-2
No
0
2
3
0
Yes
1
3
6
3
Yes
2
Valid subarrays:
[1, 2]
[3]
Enter fullscreen mode Exit fullscreen mode
Answer:
2
Enter fullscreen mode Exit fullscreen mode
Why Not Sliding Window?
This is a common question.
For problems where all numbers are positive, a sliding window may sometimes work for exact-sum conditions.
But once negative numbers are allowed, the predictable movement needed by the standard sliding-window approach disappears.
For example:
[2, -1, 2]
Enter fullscreen mode Exit fullscreen mode
Adding -1 decreases the sum.
So:
expand window
↓
sum increases
Enter fullscreen mode Exit fullscreen mode
is no longer guaranteed.
That is why Prefix Sum + HashMap is the more general pattern for counting subarrays with a target sum when negative values can exist.
Complexity
Time = O(n)
Space = O(n)
Enter fullscreen mode Exit fullscreen mode
We process each element once.
The HashMap stores prefix frequencies.
That gives us the jump from:
O(n²)
Enter fullscreen mode Exit fullscreen mode
to:
O(n)
Enter fullscreen mode Exit fullscreen mode
4. Counting Subarrays With XOR = K
Now comes the fun part.
The exact same reasoning works for XOR.
Suppose we want:
Count the number of subarrays whose XOR equals K.
For sum we had:
prefix[right] - prefix[left - 1] = K
Enter fullscreen mode Exit fullscreen mode
For XOR we have:
prefixXor[right] ^ prefixXor[left - 1] = K
Enter fullscreen mode Exit fullscreen mode
Now use the XOR property:
A ^ B = C
Enter fullscreen mode Exit fullscreen mode
which can be rearranged as:
A = C ^ B
Enter fullscreen mode Exit fullscreen mode
So:
prefixXor[left - 1]
=
prefixXor[right] ^ K
Enter fullscreen mode Exit fullscreen mode
Notice something beautiful.
The structure is almost identical.
Only the operation changed.
Sum Version
need = prefix - K
Enter fullscreen mode Exit fullscreen mode
XOR Version
need = prefixXor ^ K
Enter fullscreen mode Exit fullscreen mode
This is why understanding the mathematics behind Prefix techniques is much more useful than memorizing code.
Java Implementation
public int countSubarraysXor(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int prefixXor = 0;
int count = 0;
for (int num : nums) {
prefixXor ^= num;
count += map.getOrDefault(
prefixXor ^ k,
0
);
map.put(
prefixXor,
map.getOrDefault(prefixXor, 0) + 1
);
}
return count;
}
Enter fullscreen mode Exit fullscreen mode
Notice the similarities:
Prefix Sum:
prefix += num
need = prefix - k
Enter fullscreen mode Exit fullscreen mode
versus:
Prefix XOR:
prefixXor ^= num
need = prefixXor ^ k
Enter fullscreen mode Exit fullscreen mode
Everything else remains conceptually the same.
The Master Pattern
This is the pattern worth remembering.
For sum:
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int prefix = 0;
int answer = 0;
for (int num : nums) {
prefix += num;
answer += map.getOrDefault(
prefix - k,
0
);
map.put(
prefix,
map.getOrDefault(prefix, 0) + 1
);
}
Enter fullscreen mode Exit fullscreen mode
For XOR:
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int prefix = 0;
int answer = 0;
for (int num : nums) {
prefix ^= num;
answer += map.getOrDefault(
prefix ^ k,
0
);
map.put(
prefix,
map.getOrDefault(prefix, 0) + 1
);
}
Enter fullscreen mode Exit fullscreen mode
The framework is:
1. Maintain cumulative information.
2. Calculate what previous value is required.
3. Ask the HashMap how many times it occurred.
4. Add that frequency to the answer.
5. Store the current cumulative value.
Enter fullscreen mode Exit fullscreen mode
That is the pattern.
One Very Important Ordering Rule
Consider these two operations:
count += map.getOrDefault(...);
Enter fullscreen mode Exit fullscreen mode
and:
map.put(...);
Enter fullscreen mode Exit fullscreen mode
The lookup should happen first.
Correct:
count += map.getOrDefault(prefix - k, 0);
map.put(prefix, map.getOrDefault(prefix, 0) + 1);
Enter fullscreen mode Exit fullscreen mode
Why?
Because we are interested in a previous prefix.
If you insert the current prefix first, you risk treating the current position as if it were already in the past.
For prefix-counting problems, order matters.
Common Mistakes
Mistake 1: Forgetting map.put(0, 1)
Without:
map.put(0, 1);
Enter fullscreen mode Exit fullscreen mode
you miss subarrays beginning at index 0.
Mistake 2: Updating the Map Before Counting
Wrong:
map.put(prefix, ...);
count += ...
Enter fullscreen mode Exit fullscreen mode
Correct:
count += ...;
map.put(prefix, ...);
Enter fullscreen mode Exit fullscreen mode
We want previous prefix values, not the current one.
Mistake 3: Using Sliding Window With Negative Numbers
For the general exact-sum counting problem, negative numbers destroy the monotonic behavior required for the standard sliding-window approach.
Example:
2 -1 2
Enter fullscreen mode Exit fullscreen mode
Adding an element can decrease the sum.
So use:
Prefix Sum + HashMap
Enter fullscreen mode Exit fullscreen mode
for the general case.
Mistake 4: Confusing Sum and XOR Equations
Keep these two equations separate.
Sum
need = prefix - k
Enter fullscreen mode Exit fullscreen mode
XOR
need = prefix ^ k
Enter fullscreen mode Exit fullscreen mode
Do not mentally substitute one for the other.
The Interview Recognition Cheat Sheet
When you see:
Problem clue Think Maximum contiguous sum Kadane Range sum query Prefix Sum Maximum product subarray Track Maximum + Minimum Count subarrays with sum K Prefix Sum + HashMap Count subarrays with XOR K Prefix XOR + HashMap Fixed-size window Sliding Window Variable-size window Sliding WindowThis kind of recognition is what makes DSA faster.
A beginner reads the whole problem and starts coding.
An experienced problem solver first asks:
Which pattern is hiding inside this problem?
How the Patterns Are Connected
It may look like we have learned several unrelated techniques.
We haven’t.
They are all based on the same broader idea:
Maintain the right amount of information while traversing the array.
For Kadane:
What do I need to remember?
Best sum ending here.
Enter fullscreen mode Exit fullscreen mode
For Maximum Product:
What do I need to remember?
Best product ending here.
Worst product ending here.
Enter fullscreen mode Exit fullscreen mode
For Prefix Sum + HashMap:
What do I need to remember?
Previous prefix sums and their frequencies.
Enter fullscreen mode Exit fullscreen mode
For Prefix XOR + HashMap:
What do I need to remember?
Previous prefix XORs and their frequencies.
Enter fullscreen mode Exit fullscreen mode
This is the deeper DSA skill.
Not memorizing syntax.
Not memorizing LeetCode answers.
Choosing the correct state.
A Simple Way to Think During an Interview
When you see a subarray problem, ask these questions in order:
Question 1
Are they asking for the:
maximum/minimum?
Enter fullscreen mode Exit fullscreen mode
If yes, consider:
Kadane
Enter fullscreen mode Exit fullscreen mode
Question 2
Are they asking for:
maximum product?
Enter fullscreen mode Exit fullscreen mode
Then think:
Maximum + Minimum
Enter fullscreen mode Exit fullscreen mode
because negative values can reverse the result.
Question 3
Are they asking:
How many subarrays?
Enter fullscreen mode Exit fullscreen mode
Now think about Prefix Sum or Prefix XOR with a frequency map.
Question 4
Is there a target:
sum = K
Enter fullscreen mode Exit fullscreen mode
Then derive:
need = prefix - K
Enter fullscreen mode Exit fullscreen mode
Question 5
Is it:
XOR = K
Enter fullscreen mode Exit fullscreen mode
Then derive:
need = prefixXor ^ K
Enter fullscreen mode Exit fullscreen mode
Practice Order
Don’t randomly jump between hard problems.
Build the patterns in this order.
Stage 1: Master Kadane
LeetCode 53 — Maximum Subarray
This should become automatic.
Focus on understanding:
currentSum
maximumSum
negative reset
all-negative arrays
Enter fullscreen mode Exit fullscreen mode
Stage 2: Maximum Product
LeetCode 152 — Maximum Product Subarray
Focus on:
currentMax
currentMin
negative number
swapping roles
Enter fullscreen mode Exit fullscreen mode
Stage 3: Prefix Sum + HashMap
LeetCode 560 — Subarray Sum Equals K
This is mandatory.
Understand:
prefix - k
map.put(0, 1)
frequency counting
lookup before insertion
Enter fullscreen mode Exit fullscreen mode
Then move to:
LeetCode 525 — Contiguous Array
LeetCode 974 — Subarray Sums Divisible by K
LeetCode 930 — Binary Subarrays With Sum
LeetCode 1248 — Count Number of Nice Subarrays
Stage 4: Prefix XOR
Practice:
Count Subarrays With Given XOR
and:
LeetCode 1442 — Count Triplets That Can Form Two Arrays of Equal XOR
Also revisit:
LeetCode 1310 — XOR Queries of a Subarray
which uses Prefix XOR directly.
Final Mental Model
Here is the part I actually want you to remember.
When the problem says:
maximum contiguous sum
Enter fullscreen mode Exit fullscreen mode
think:
"What is the best subarray ending here?"
Enter fullscreen mode Exit fullscreen mode
That leads to:
Kadane
Enter fullscreen mode Exit fullscreen mode
When the problem says:
maximum contiguous product
Enter fullscreen mode Exit fullscreen mode
think:
"What are the best and worst products ending here?"
Enter fullscreen mode Exit fullscreen mode
That leads to:
Maximum + Minimum
Enter fullscreen mode Exit fullscreen mode
When the problem says:
count subarrays with sum K
Enter fullscreen mode Exit fullscreen mode
think:
"If my current prefix is X,
I need an old prefix of X-K."
Enter fullscreen mode Exit fullscreen mode
That leads to:
Prefix Sum + HashMap
Enter fullscreen mode Exit fullscreen mode
When the problem says:
count subarrays with XOR K
Enter fullscreen mode Exit fullscreen mode
think:
"If my current prefix XOR is X,
I need an old prefix of X^K."
Enter fullscreen mode Exit fullscreen mode
That leads to:
Prefix XOR + HashMap
Enter fullscreen mode Exit fullscreen mode
The Real Lesson
The biggest improvement in DSA does not come from memorizing more code.
It comes from getting better at asking:
What information from the past can help me solve the current position?
Kadane remembers:
the best running sum
Enter fullscreen mode Exit fullscreen mode
Maximum Product remembers:
the best and worst running products
Enter fullscreen mode Exit fullscreen mode
Prefix Sum remembers:
cumulative sums
Enter fullscreen mode Exit fullscreen mode
Prefix HashMap remembers:
how often useful cumulative values appeared
Enter fullscreen mode Exit fullscreen mode
Once you start thinking this way, subarray problems become much less about trying random techniques and much more about identifying the state you need.
And that is exactly what interviews are testing.
Not whether you can type HashMap<Integer, Integer> without looking at the ceiling for emotional support.