Contiguous Array
Mahabharata — The Balanced Army — Finding the Longest Stretch With Equal Pandavas and Kauravas
यत्र पाण्डवाः कौरवाश्च समसंख्याः एकत्र। तत् दीर्घतमं क्षेत्रं — युद्धस्य सन्तुलनम्॥
*Where Pandavas and Kauravas are equal in number — that is the longest stretch of balanced battle.*
The Story
Sanjaya was narrating the battle formations to the blind king Dhritarashtra. The battlefield was divided into n sectors, each sector occupied by either a Pandava soldier (1) or a Kaurava soldier (0). Dhritarashtra asked a surprising question: "Which is the longest contiguous stretch of battlefield where the number of Pandava soldiers equals the number of Kaurava soldiers?"
This was equivalent to: find the longest subarray of 0s and 1s with equal numbers of both.
Vidura's elegant insight: treat every 0 as -1. Then a subarray with equal 0s and 1s has a sum of exactly 0 (positives cancel negatives). We need the longest subarray with sum = 0.
"This is exactly the prefix sum problem," Vidura said. "If prefixSum[i] == prefixSum[j], then the subarray (j+1..i) has sum 0 — equal counts of 1s and 0s."
"But instead of counting occurrences like ps-1, here we want the MAXIMUM LENGTH. So we store the FIRST index where each prefix sum was seen."
Algorithm: 1. Initialize map with {0: -1} (prefix sum 0 first seen before index 0) 2. Maintain running sum (1 for '1', -1 for '0') 3. If current sum was seen before at index j: length = i - j. Update maxLen. 4. If current sum is NEW: store it with its index.
Vidura traced through `[0,1,0,0,1,1,0]`:
map = {0:-1}, sum=0
- i=0 (0→-1): sum=-1. New. map={0:-1,-1:0} - i=1 (1): sum=0. Seen at -1! len=1-(-1)=2. maxLen=2. Don't update. - i=2 (0→-1): sum=-1. Seen at 0! len=2-0=2. maxLen=2. - i=3 (0→-1): sum=-2. New. map+{-2:3} - i=4 (1): sum=-1. Seen at 0! len=4-0=4. maxLen=4. - i=5 (1): sum=0. Seen at -1! len=5-(-1)=6. maxLen=6. - i=6 (0→-1): sum=-1. Seen at 0! len=6-0=6. maxLen=6.
Answer: 6 — the entire array from index 0 to 5 (six elements: [0,1,0,0,1,1]) has three 0s and three 1s.
"The battle front of length 6 is perfectly balanced," Dhritarashtra concluded.
"Notice the critical difference from ps-1," Vidura pointed out. "In ps-1 we stored COUNT (multiple paths could have the same prefix sum). Here we store the FIRST INDEX — because a longer subarray uses an EARLIER occurrence of the same sum. We never overwrite the first occurrence."
This is the Prefix Sum with First-Index Map technique for finding the longest balanced binary subarray.
The Scout's First Instinct
Try every start-end pair. Count 0s and 1s. Record maximum length where counts match. O(n²) time.
public int findMaxLengthBruteForce(int[] nums) {
int maxLen = 0;
for (int start = 0; start < nums.length; start++) {
int zeros = 0, ones = 0;
for (int end = start; end < nums.length; end++) {
if (nums[end] == 0) zeros++; else ones++;
if (zeros == ones) maxLen = Math.max(maxLen, end - start + 1);
}
}
return maxLen;
}Vidura's Transform Wisdom
public int findMaxLength(int[] nums) {
Map<Integer, Integer> firstSeen = new HashMap<>();
firstSeen.put(0, -1); // Sum 0 first seen before array starts
int sum = 0, maxLen = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i] == 1 ? 1 : -1; // 1→+1, 0→-1
if (firstSeen.containsKey(sum)) {
maxLen = Math.max(maxLen, i - firstSeen.get(sum));
} else {
firstSeen.put(sum, i); // Store FIRST index only
}
}
return maxLen;
}Step-by-Step Walkthrough
nums = [0,1]
map={0:-1}, sum=0
i=0(0→-1): sum=-1. Not in map. map={0:-1,-1:0}
i=1(1→+1): sum=0. In map at -1! len=1-(-1)=2. maxLen=2.
Return 2 ✅ ([0,1] has one 0 and one 1)Deep Insight
**Why store first index only?** A later occurrence of the same prefix sum means a SHORTER subarray to the current index. We want the MAXIMUM length, so the EARLIER (first) occurrence gives the longest span.
**The {0:-1} initialization:** If the entire prefix from index 0 to i has equal 0s and 1s, sum=0. We need length = i - (-1) = i+1. Without {0:-1}, we'd miss subarrays starting at index 0.
**ps-1 vs ps-4 comparison:** - ps-1: count subarrays with sum=K → store COUNT of each prefix sum - ps-4: longest subarray with sum=0 → store FIRST INDEX of each prefix sum Same technique, different map value type.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | All subarrays checked |
| Optimal | O(n) | O(n) | HashMap stores at most n distinct prefix sums |
Pattern Recognition
✅ Longest subarray with equal 0s and 1s
✅ Transform: 0→-1, find longest subarray with sum=0
✅ Prefix sum + first-index map
✅ Initialize {0:-1} for subarrays starting at index 0
**LeetCode Trigger Phrases:**
→ "equal number of 0s and 1s"
→ "contiguous array" + binary
→ "balanced binary subarray"Bhagavad Gita 13.28
समं पश्यन् हि सर्वत्र समवस्थितमीश्वरम्। न हिनस्त्यात्मनात्मानं ततो याति परां गतिम्॥
One who sees the Supreme Lord equally present everywhere does not harm the Self by the self and thus attains the supreme destination.
Connection: The algorithm seeks perfect balance — equal counts of two opposing forces (0s and 1s). Like the sage who sees the divine equally in all, the prefix sum map reveals every point where perfect equilibrium has been achieved. The longest balanced stretch is found not by brute comparison but by recognizing that equal prefix sums mark the boundaries of perfect balance.