Subarray Problem Types

🧩 1. Subarray Problem Types

When you see “subarray,” the first thing to ask is:

“What property of the subarray am I checking or optimizing?”

That determines the technique.

Type of Subarray Problem	Goal	Common Approaches
Fixed-size sum	Sum of subarray of size k	Sliding Window
Variable-size sum	Subarray with target sum k	Prefix Sum + HashMap
Max/Min sum	Largest sum subarray	Kadane’s Algorithm
Count subarrays with property	Count of subarrays with sum = K or 0	Prefix Sum + HashMap
Longest subarray with condition	e.g., sum = K, 0-sum, equal 0s & 1s	Prefix Sum + HashMap
Product-based	e.g., product < k	Sliding Window (for positive numbers)
Bitwise-based	e.g., XOR = k	Prefix XOR + HashMap

---

⚙️ 2. The Prefix Sum Pattern (and Its Variants)

Let’s look at how prefix sum helps — it converts “subarray” problems into “difference between two prefixes.”

🔹 Definition

For an array arr,
prefix[i] = arr[0] + arr[1] + ... + arr[i]

Then,
sum(l, r) = prefix[r] - prefix[l - 1]

---

✅ Problems You Mentioned (and Their Patterns)

Let’s see how prefix sum fits into each.

1️⃣ Zero-Sum Subarray

Find if any subarray sums to 0 (or count them).

Approach

• Maintain running sum prefixSum.
• Use a HashSet (or HashMap if counting).
• If prefixSum repeats, it means a subarray in between sums to 0.

Why?

Because if prefix[j] == prefix[i],
then the sum of subarray (i+1 ... j) = 0.

---

2️⃣ K-Sum Subarray (Count of subarrays with sum = K)

Approach

• Keep running sum.
• For each prefix sum, check if (prefixSum - K) exists in map.
• Map stores how many times each prefixSum has occurred.

Formula

If prefix[j] - prefix[i] == K, then subarray (i+1 ... j) sums to K.

---

3️⃣ Longest K-Sum Subarray

Approach

• Similar to above, but instead of counting, track the first index of each prefixSum.
• When you find prefixSum - K in map, → compute length = currentIndex - indexOf(prefixSum - K).

---

4️⃣ Longest Zero-Sum Subarray

Approach

• Same as above with K = 0.
• Use map to store first occurrence of each prefixSum.
• Update max length whenever prefixSum repeats.

---

💡 3. Other Common Subarray Patterns

Here are related patterns you should know to complete your subarray toolbox:

Category	Problem	Key Idea
Sliding Window	Fixed size k subarray sum / max / avg	Maintain a window sum; slide by removing left, adding right
Kadane’s Algorithm	Maximum sum subarray	Dynamic running sum; reset when negative
Prefix XOR	Subarray with XOR = K	Use XOR property: xor[j] ^ xor[i-1] = K
Two Pointers / Sliding Window	Subarray with product < K / sum < K	Expand–shrink window dynamically
Monotonic Stack	Subarray min/max contribution (sum of subarray minimums, etc.)	Keep increasing/decreasing stack
Divide & Conquer	Max subarray sum (classic approach)	Combine prefix & suffix max from halves

---

🧠 4. How to Identify the Pattern

When you read a subarray problem, ask:

Question	If answer is…	Use this Pattern
“Fixed window size?”	Yes	Sliding Window
“Target sum or condition (sum=K, 0, XOR=K)?”	Yes	Prefix Sum / XOR + HashMap
“Max/Min sum?”	Yes	Kadane’s Algorithm
“Count subarrays?”	Yes	Prefix Sum + Frequency Map
“Longest subarray satisfying condition?”	Yes	Prefix Sum + First Occurrence Map
“Product-based?”	Yes	Sliding Window (positive numbers only)

---

🚀 5. Recommended Practice Order

Prefix Sum + HashMap

• Subarray Sum Equals K
• Zero Sum Subarray
• Longest Subarray with Sum K / Zero Sum

Kadane’s Algorithm

• Max Sum Subarray

Sliding Window

• Max Sum Subarray of size K
• Subarray product < K

Prefix XOR

• Count subarrays with XOR K

Advanced

• Sum of subarray minimums (Monotonic Stack)
• Maximum absolute sum subarray