The Hidden Patterns Behind Subarray Problems

Vardhan_Kirti — Wed, 19 Aug 2026 18:39:28 +0000

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

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]

The answer is:

[4, -1, 2, 1]

Its sum is:

4 + (-1) + 2 + 1 = 6

So the answer is:

There is one important word here:

contiguous

Kadane's Algorithm works on a subarray, not a subsequence.

For example:

[4, -1, 2, 1]

is valid because the elements are next to each other.

But something like:

[4, 2, 1]

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]

Possible subarrays are:

[2]

[2, -1]

[2, -1, 3]

[-1]

[-1, 3]

[3]

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;
    }
}

This solution is correct.

But what is the complexity?

Time  = O(n²)
Space = O(1)

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]

Start from the first element and keep a running sum:

4
4 + (-2) = 2
2 + 5 = 7
7 + (-1) = 6

So:

4 → 2 → 7 → 6

When we reached:

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

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]

Then:

maximumSum = max(maximumSum, currentSum)

And now comes the important decision.

If:

currentSum < 0

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

Your bag contains:

You want to keep carrying that because it is helping your total.

Now imagine someone puts:

-100

inside.

Your total becomes:

7 - 100 = -93

Now ask:

Is this baggage useful for the next element?

No.

If tomorrow you see:

+10

you are better off starting with:

instead of:

-93 + 10 = -83

So:

negative running sum
        ↓
throw it away
        ↓
start fresh

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.

In compact form:

currentSum += num

maximumSum = max(maximumSum, currentSum)

if currentSum < 0
    currentSum = 0

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;
    }
}

Notice something very important.

We update:

maxSum

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]

Let's track three things:

Current Number
Current Sum
Maximum Sum

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	6

So the final answer is:

The subarray producing it is:

[4, -1, 2, 1]

The important moment happens when currentSum becomes negative.

For example:

4 + (-1) + 2 + 1 + (-5)

gives:

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]

The correct answer is:

-2

But look at our reset rule.

If we reset every negative sum to zero, someone might accidentally write:

int maxSum = 0;

Then the answer would become:

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;

and update maxSum before resetting currentSum.

Dry run:

current = -5
max = -5
reset

current = -2
max = -2
reset

current = -8
max = -2
reset

Final answer:

-2

Correct.

Common Kadane Mistakes

Mistake 1: `maxSum = 0`

Wrong:

int maxSum = 0;

This fails for:

[-3, -5, -1]

because it would return:

instead of:

-1

Use:

int maxSum = Integer.MIN_VALUE;

Mistake 2: Resetting Before Updating Maximum

Wrong:

if (currentSum < 0) {
    currentSum = 0;
}

maxSum = Math.max(maxSum, currentSum);

For all-negative arrays, this can lose the actual answer.

Correct:

maxSum = Math.max(maxSum, currentSum);

if (currentSum < 0) {
    currentSum = 0;
}

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)

This is the major improvement:

Brute Force → O(n²)

Kadane       → O(n)

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

Think:

Kadane's Algorithm

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]

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

The maximum product is:

from:

[2, 3]

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

usually makes the running sum worse.

For example:

5 + (-8) = -3

So throwing away a negative running sum makes sense.

But multiplication behaves differently.

Consider:

-2 × -3 = 6

Two negative values create a positive value.

Suddenly a negative product that looked useless can become the best answer later.

Consider:

[-2, 3, -4]

The complete product is:

(-2) × 3 × (-4)

which equals:

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

Negative × Positive
        ↓
Negative

Negative × Negative
        ↓
Positive

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

For product, we need:

currentMax
currentMin

Why?

Because:

currentMax × negative

can become negative.

But:

currentMin × negative

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]

Initially:

currentMax = -2
currentMin = -2
answer = -2

Now process 3.

Possible products are:

3

-2 × 3 = -6

-2 × 3 = -6

So:

currentMax = 3
currentMin = -6

Now process -4.

Possible maximum values are:

-4
3 × -4 = -12
-6 × -4 = 24

So:

currentMax = 24

And there is the answer.

Notice where it came from:

currentMin

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

2. Extend the previous maximum product

num × currentMax

3. Extend the previous minimum product

num × currentMin

Therefore:

newMax =
max(
    num,
    num × currentMax,
    num × currentMin
)

And:

newMin =
min(
    num,
    num × currentMax,
    num × currentMin
)

This is the entire idea.

Why Do We Need Temporary Variables?

Suppose:

currentMax = ...
currentMin = ...

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;

Then use:

tempMax

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;
    }
}

A Cleaner Version: Swap on Negative

There is another way to understand the same idea.

When:

num < 0

maximum and minimum switch roles.

Why?

Suppose:

max = 5
min = -3

Multiply both by -2:

5 × -2 = -10
-3 × -2 = 6

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;
}

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;
    }
}

This version captures the idea very nicely.

When the sign flips:

maximum ↔ minimum

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;
}

That does not work.

A negative product can later become the maximum.

Mistake 2: Tracking Only Maximum

You must track:

maximum
AND
minimum

Because:

minimum × negative

can become maximum.

Mistake 3: Forgetting the Negative Swap

When:

num < 0

the roles of maximum and minimum change.

Mistake 4: Initializing With `1`

Do not blindly write:

int max = 1;

Consider:

[-5]

The answer is:

-5

So initialize using:

nums[0]

Complexity

Time  = O(n)
Space = O(1)

Again, one pass.

The interesting part is not the complexity.

It is the state we decided to maintain.

For maximum sum:

one state

For maximum product:

two states

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

Think:

Track maximum AND minimum

3. Counting Subarrays With a Given Sum

Now let's solve a different kind of question.

Until now, we asked:

What is the maximum?

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

Valid subarrays are:

[1, 1]

[1, 1]

So the answer is:

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;
    }
}

Complexity:

Time  = O(n²)
Space = O(1)

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]

is the sum from the beginning to right.

For a subarray:

left → right

its sum is:

prefix[right] - prefix[left - 1]

If we want the sum to equal K:

prefix[right] - prefix[left - 1] = K

Rearrange:

prefix[left - 1] = prefix[right] - K

This is the entire algorithm.

Do not memorize the code.

Memorize this equation.

What Does the Equation Mean?

Suppose the current prefix sum is:

and:

K = 6

Then we need:

10 - 6 = 4

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)

lookup time.

But there is one more important detail.

We don't just store whether a prefix sum exists.

We store:

frequency

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

The Famous `map.put(0, 1)`

The code starts with:

map.put(0, 1);

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

Prefix sums:

2
5

At the second element:

currentPrefix = 5

We need:

5 - 5 = 0

Where did that 0 come from?

It represents the empty prefix before index 0.

Without:

map.put(0, 1);

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}

First number: 1

prefix = 1

Need:

1 - 2 = -1

Not found.

Store:

1 → 1

Map becomes:

{0:1, 1:1}

Second number: 1

prefix = 2

Need:

2 - 2 = 0

Found.

How many times?

So:

count = 1

Store prefix 2.

Third number: 1

prefix = 3

Need:

3 - 2 = 1

Prefix 1 exists.

So:

count = 2

Final answer:

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;
    }
}

A More Detailed Dry Run

Take:

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

Number	Prefix	Need `prefix-k`	Found?	Count
1	1	-2	No	0
2	3	0	Yes	1
3	6	3	Yes	2

Valid subarrays:

[1, 2]

[3]

Answer:

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]

Adding -1 decreases the sum.

So:

expand window
    ↓
sum increases

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)

We process each element once.

The HashMap stores prefix frequencies.

That gives us the jump from:

O(n²)

to:

O(n)

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

For XOR we have:

prefixXor[right] ^ prefixXor[left - 1] = K

Now use the XOR property:

A ^ B = C

which can be rearranged as:

A = C ^ B

So:

prefixXor[left - 1]
=
prefixXor[right] ^ K

Notice something beautiful.

The structure is almost identical.

Only the operation changed.

Sum Version

need = prefix - K

XOR Version

need = prefixXor ^ K

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;
}

Notice the similarities:

Prefix Sum:
prefix += num

need = prefix - k

versus:

Prefix XOR:
prefixXor ^= num

need = prefixXor ^ k

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
    );
}

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
    );
}

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.

That is the pattern.

One Very Important Ordering Rule

Consider these two operations:

count += map.getOrDefault(...);

and:

map.put(...);

The lookup should happen first.

Correct:

count += map.getOrDefault(prefix - k, 0);

map.put(prefix, map.getOrDefault(prefix, 0) + 1);

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);

you miss subarrays beginning at index 0.

Mistake 2: Updating the Map Before Counting

Wrong:

map.put(prefix, ...);

count += ...

Correct:

count += ...;

map.put(prefix, ...);

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

Adding an element can decrease the sum.

So use:

Prefix Sum + HashMap

for the general case.

Mistake 4: Confusing Sum and XOR Equations

Keep these two equations separate.

Sum

need = prefix - k

XOR

need = prefix ^ k

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 Window

This 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.

For Maximum Product:

What do I need to remember?

Best product ending here.
Worst product ending here.

For Prefix Sum + HashMap:

What do I need to remember?

Previous prefix sums and their frequencies.

For Prefix XOR + HashMap:

What do I need to remember?

Previous prefix XORs and their frequencies.

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?

If yes, consider:

Kadane

Question 2

Are they asking for:

maximum product?

Then think:

Maximum + Minimum

because negative values can reverse the result.

Question 3

Are they asking:

How many subarrays?

Now think about Prefix Sum or Prefix XOR with a frequency map.

Question 4

Is there a target:

sum = K

Then derive:

need = prefix - K

Question 5

Is it:

XOR = K

Then derive:

need = prefixXor ^ K

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

Stage 2: Maximum Product

LeetCode 152 — Maximum Product Subarray

Focus on:

currentMax
currentMin
negative number
swapping roles

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

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

think:

"What is the best subarray ending here?"

That leads to:

Kadane

When the problem says:

maximum contiguous product

think:

"What are the best and worst products ending here?"

That leads to:

Maximum + Minimum

When the problem says:

count subarrays with sum K

think:

"If my current prefix is X,
I need an old prefix of X-K."

That leads to:

Prefix Sum + HashMap

When the problem says:

count subarrays with XOR K

think:

"If my current prefix XOR is X,
I need an old prefix of X^K."

That leads to:

Prefix XOR + HashMap

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

Maximum Product remembers:

the best and worst running products

Prefix Sum remembers:

cumulative sums

Prefix HashMap remembers:

how often useful cumulative values appeared

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.

DEV Community: Vardhan_Kirti

The Hidden Patterns Behind Subarray Problems

1. Kadane's Algorithm

The Problem

Why Not Just Generate Every Subarray?

The Key Observation

The Core Idea of Kadane's Algorithm

Think of It Like Carrying a Bag

Kadane's Algorithm

Java Implementation

Dry Run

The All-Negative Case

Common Kadane Mistakes

Mistake 1: maxSum = 0

Mistake 2: Resetting Before Updating Maximum

Mistake 3: Thinking Kadane Finds a Subsequence

Kadane Complexity

How to Recognize Kadane's Algorithm

2. Maximum Product Subarray

Why Doesn't Normal Kadane Work?

The Key Observation

So What Do We Track?

Example

The Three Possibilities

1. Start fresh

2. Extend the previous maximum product

3. Extend the previous minimum product

Why Do We Need Temporary Variables?

Java Implementation

A Cleaner Version: Swap on Negative

Recommended Java Version

Common Mistakes in Maximum Product

Mistake 1: Applying Kadane Directly

Mistake 2: Tracking Only Maximum

Mistake 3: Forgetting the Negative Swap

Mistake 4: Initializing With 1

Complexity

How to Recognize Maximum Product Problems

3. Counting Subarrays With a Given Sum

Brute Force

Prefix Sum Gives Us an Equation

What Does the Equation Mean?

Why Use a HashMap?

The Famous map.put(0, 1)

Dry Run: [1, 1, 1], K = 2

First number: 1

Second number: 1

Third number: 1

Java Solution

A More Detailed Dry Run

Why Not Sliding Window?

Complexity

4. Counting Subarrays With XOR = K

Sum Version

XOR Version

Java Implementation

The Master Pattern

One Very Important Ordering Rule

Common Mistakes

Mistake 1: Forgetting map.put(0, 1)

Mistake 2: Updating the Map Before Counting

Mistake 3: Using Sliding Window With Negative Numbers

Mistake 4: Confusing Sum and XOR Equations

Sum

XOR

The Interview Recognition Cheat Sheet

How the Patterns Are Connected

A Simple Way to Think During an Interview

Question 1

Question 2

Question 3

Question 4

Question 5

Practice Order

Stage 1: Master Kadane

Stage 2: Maximum Product

Stage 3: Prefix Sum + HashMap

Stage 4: Prefix XOR

Final Mental Model

The Real Lesson

Mistake 1: `maxSum = 0`

Mistake 4: Initializing With `1`

The Famous `map.put(0, 1)`

Dry Run: `[1, 1, 1]`, K = 2

Mistake 1: Forgetting `map.put(0, 1)`