Sliding WindowEasyO(n) time · O(1) space

Smallest Subarray with a Given Sum

Mahabharata — Draupadi's Akshaya Patra — The Minimum Feast That Satisfies a Sage's Wrath

न्यूनेन सम्पूर्णं यद्भवेत् तत् श्रेष्ठमुच्यते। यावन्मात्रेण तृप्तिस्स्यात् तावदेव प्रयच्छेत्॥

*The smallest that fulfills completely is said to be the best. Give only as much as brings satisfaction.*

The Story

The Pandavas were in exile, wandering the forests with Draupadi. Their only means of feeding the endless parade of sages and guests was the Akshaya Patra — the inexhaustible vessel gifted by the Sun God. It would produce food endlessly until Draupadi herself had eaten, after which it would yield nothing more that day.

One fateful afternoon, the fearsome sage Durvasa arrived with ten thousand disciples, demanding food. Draupadi had already eaten. The vessel was empty.

Krishna intervened. He found a single grain of rice stuck to the vessel's rim, ate it with devotion, and declared "The universe is satisfied." By some divine mystery, Durvasa and his disciples suddenly felt full and departed without eating.

But the lesson Yudhishthira drew from this miracle was mathematical. The court minister Vidura, in a subsequent letter, posed this challenge to sharpen the princes' minds:

"A caravan of n merchants carries provisions. Each merchant carries some weight of food. The Akshaya Patra can carry exactly one contiguous group of merchants' provisions. You need the group's total to be at LEAST S units — enough to satisfy the sage. Find the minimum number of contiguous merchants whose provisions sum to at least S."

Pandava's aide Dhaumya tried the straightforward approach: "For each starting merchant, keep adding until we hit S. Track the minimum length."

"That works," Yudhishthira said, "but it's O(n²). Let us do better."

"The key observation," said Nakula, who had a sharp mathematical mind, "is this: we should use a variable-size sliding window. Unlike the fixed-K problem, here we don't know the window size in advance. We must discover it."

Nakula laid out the algorithm:

"Expand the right boundary one merchant at a time, adding their provisions to our running sum. As soon as the sum reaches or exceeds S — we have found a VALID window. But is it the MINIMUM valid window?"

"No," Sahadeva said. "We should try to shrink from the left. While the sum remains ≥ S, remove the leftmost merchant. Each time we shrink while still valid, we record the length — it might be our new minimum."

"When the sum drops below S by shrinking, we stop shrinking and expand the right again."

Dhaumya demonstrated with provisions `[2, 1, 5, 2, 3, 2]` and target S = 7:

Right=0: sum=2. 2<7, expand. Right=1: sum=3. 3<7, expand. Right=2: sum=8. 8≥7! Window [0..2], length 3. Shrink: remove left(2), sum=6<7, stop shrinking. Min=3. Right=3: sum=8. 8≥7! Window [1..3], length 3. Shrink: remove left(1), sum=7≥7! Window [2..3], length 2. Shrink: remove left(5), sum=2<7, stop. Min=2. Right=4: sum=5. 5<7, expand. Right=5: sum=7. 7≥7! Window [3..5], length 3. Shrink: remove left(2), sum=5<7, stop. Min still 2.

"The minimum contiguous group is length 2 — merchants at positions 2 and 3, carrying 5 and 2 = 7 units," Dhaumya confirmed.

"And notice," Nakula added, "that even though we have nested loops (a while inside a for), each merchant's provision is ADDED once (when right crosses it) and REMOVED at most once (when left crosses it). So total operations = 2n. The algorithm is O(n) despite the nested appearance."

Yudhishthira nodded. "The two-pointer dance: right expands to find a valid window, left contracts to minimize it. Expand until valid, shrink while valid."

The Pandavas survived their exile through this principle — taking only the minimum that satisfied, wasting nothing, in harmony with the forest's limited gifts.

"This is the variable sliding window," Yudhishthira concluded. "Unlike the fixed-K window where we always drop exactly one element when we add one, here we drop as many as needed to minimize the window whenever the sum stays sufficient."

This is the variable Sliding Window technique for finding the smallest subarray with a given sum.

Dhaumya's First Instinct

Try every starting position, accumulate sum until it reaches target. Track minimum valid length. O(n²) due to nested loops over all start-end pairs.

java

public int minSubArrayLenBruteForce(int target, int[] nums) {
    int minLen = Integer.MAX_VALUE;
    
    for (int start = 0; start < nums.length; start++) {
        int sum = 0;
        for (int end = start; end < nums.length; end++) {
            sum += nums[end];
            if (sum >= target) {
                minLen = Math.min(minLen, end - start + 1);
                break;  // Any further extension only increases length
            }
        }
    }
    
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

Nakula's Wisdom

Nakula's insight: variable sliding window — expand right to reach the target, then shrink left to minimize length while the window remains valid (sum ≥ target). Each element is added and removed at most once, giving O(n) total. - `right` expands: adds `nums[right]` to `sum` - When `sum >= target`: record length, shrink `left` while still valid - Continue until `right` exhausts the array

java

public int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int sum = 0;
    int minLen = Integer.MAX_VALUE;
    
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];  // Expand: add rightmost merchant's provisions
        
        // Shrink from left while window is still valid (sum >= target)
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);  // Record current length
            sum -= nums[left];  // Remove leftmost merchant
            left++;             // Shrink window
        }
    }
    
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

// Test
public static void main(String[] args) {
    int[] provisions = {2, 3, 1, 2, 4, 3};
    System.out.println(new Solution().minSubArrayLen(7, provisions));  // 2 ([4,3])
    
    int[] p2 = {1, 4, 4};
    System.out.println(new Solution().minSubArrayLen(4, p2));  // 1 ([4])
}

Step-by-Step Walkthrough

nums = [2, 3, 1, 2, 4, 3],  target = 7

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=0: sum=0+2=2 < 7 → expand
right=1: sum=2+3=5 < 7 → expand
right=2: sum=5+1=6 < 7 → expand

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=3: sum=6+2=8 ≥ 7
  len=3-0+1=4, minLen=4
  shrink: sum=8-nums[0]=8-2=6 < 7 → stop
  left=1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=4: sum=6+4=10 ≥ 7
  len=4-1+1=4, minLen=4
  shrink: sum=10-nums[1]=10-3=7 ≥ 7
    len=4-2+1=3, minLen=3
  shrink: sum=7-nums[2]=7-1=6 < 7 → stop
  left=3

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=5: sum=6+3=9 ≥ 7
  len=5-3+1=3, minLen=3
  shrink: sum=9-nums[3]=9-2=7 ≥ 7
    len=5-4+1=2, minLen=2  ← NEW MIN!
  shrink: sum=7-nums[4]=7-4=3 < 7 → stop
  left=5

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Return 2  (subarray [4,3] = 7)

Deep Insight

**Why is this O(n) despite the nested while loop?**

Each element `nums[i]` is processed by `right` exactly once (added to sum) and by `left` at most once (removed from sum). Total operations across all iterations = at most 2n. Amortized O(1) per outer loop iteration.

**Variable window vs Fixed window:** - Fixed (sw-1): window size K is given, always drop exactly one element when you add one - Variable (sw-2): window size is unknown, expand until valid, shrink while valid to find minimum

**Edge cases:** - No valid subarray exists: `minLen` never updated from `Integer.MAX_VALUE`, return 0 - Single element equals target: minLen=1 - All elements less than target and their total < target: return 0 - Target = 1 with all positive elements: return 1 (any single element works)

**Why `while` not `if` for shrinking?** After removing one element, the sum might still be ≥ target. We want the minimum window, so we keep shrinking as long as valid.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n²)	O(1)	Nested loops try all O(n²) start-end pairs
Optimal	O(n)	O(1)	Each element added once and removed at most once = 2n total operations

Pattern Recognition

✅ Subarray with sum ≥ target (variable window)
✅ Minimize window length
✅ All positive numbers (required for variable window shrinking logic)
✅ Expand to find valid, shrink to minimize

**LeetCode Trigger Phrases:**
→ "minimum length subarray... sum ≥ target"
→ "smallest contiguous subarray with sum at least"
→ "minimize the subarray size" + sum constraint

Bhagavad Gita 3.9

यज्ञार्थात्कर्मणोऽन्यत्र लोकोऽयं कर्मबन्धनः। तदर्थं कर्म कौन्तेय मुक्तसङ्गः समाचर॥

Work done as a sacrifice for the divine is liberating; work done for any other purpose is bondage. Therefore, O son of Kunti, perform your duties as an offering, free from all attachment.

Connection: The algorithm takes exactly what it needs — the minimum window that satisfies the requirement — no more, no less. Like the Gita's teaching of offering without attachment, the sliding window expands only to fulfill the purpose (sum ≥ target) and then releases greedily, shrinking without hesitation. The Akshaya Patra gives exactly what is needed for satisfaction, not surplus. This is action without excess attachment to accumulation.