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

Minimum Size Subarray Sum

Mahabharata — Karna's Kavach-Kundal — The Smallest Regiment Whose Combined Valor Defeats Indra

वीरत्वस्य योगः S — न्यूनतमैः कः सिद्ध्यति। व्यूहो विस्तार्य पश्चात् न्यूनीकुरु — एष कौशलम्॥

*The sum of valor required is S — with how few can it be achieved? Expand the formation, then minimize — this is the skill.*

The Story

Karna stood on the battlefield, his divine armor (Kavach) and earrings (Kundal) radiating unbreakable light. Indra, king of the gods, needed to defeat Karna by stripping him of these gifts. But Indra was bound by a cosmic rule: he could only ask for a donation during a sacred yagna, and the donation must come from a CONTIGUOUS group of warriors whose combined valor-score reached at least S.

Indra's scouts had mapped out n warriors in sequence, each with a valor-score. They needed to find the MINIMUM number of consecutive warriors whose combined valor would reach S — the minimum donation threshold that could challenge Karna's divine armor.

"This is exactly the same as finding the minimum length subarray with sum ≥ target," the divine mathematician Brihaspati noted. "We have seen this pattern as sw-2."

Yudhishthira, who had studied both problems, confirmed: "sw-8 and sw-2 are identical. The algorithm is the same variable sliding window: expand right until sum ≥ target, then shrink from left while maintaining sum ≥ target. The minimum window length during valid windows is our answer."

The scouts demonstrated with valor-scores `[2, 3, 1, 2, 4, 3]` and target S = 7:

Expand and shrink: - right=0: sum=2 < 7 - right=1: sum=5 < 7 - right=2: sum=6 < 7 - right=3: sum=8 ≥ 7! len=4, minLen=4. Shrink: sum=6 < 7, stop. left=1. - right=4: sum=10 ≥ 7! len=4, minLen=4. Shrink: sum=7 ≥ 7! len=3, minLen=3. Shrink: sum=3 < 7, stop. left=3. - right=5: sum=6 < 7. Wait — sum=3+3=6? No: after left=3, window is [nums[3],nums[4]]=[2,4]=6. right=5 adds 3 → sum=9. Actually let me redo: after last shrink, sum=4 (nums[4]=4, window=[4]), left=4. right=5: sum=4+3=7 ≥ 7! len=2, minLen=2. Shrink: sum=3 < 7, stop. left=5.

Answer: 2 (subarray [4,3]).

"The smallest regiment is just 2 warriors," Brihaspati confirmed. "Warrior 5 (valor=4) and warrior 6 (valor=3) together reach S=7."

Indra used this minimum formation — just two warriors — to approach Karna during the yagna. Karna, true to his legendary generosity, could not refuse the donation despite knowing it was a trap. He gave away his Kavach and Kundal.

The minimum window had been found. Sometimes, the most powerful offering is the smallest one that still meets the threshold.

"This problem appears twice in our curriculum — sw-2 and sw-8 — as a reminder," Yudhishthira said. "A pattern seen twice is a pattern you must truly internalize. The variable sliding window is fundamental. See it once, recognize it forever."

This is the variable Sliding Window technique — same as sw-2 — for finding the minimum length subarray with sum ≥ target.

The Scout's First Instinct

Try every subarray. For each starting index, extend until sum ≥ target, recording the minimum length. O(n²) time.

java

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

Brihaspati's Wisdom

Expand right to reach the target sum, then shrink left to minimize the window while keeping sum ≥ target. Same algorithm as sw-2. Each element added and removed at most once — O(n) total.

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: include new warrior's valor
        
        // Shrink while window is valid (sum >= target)
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left++];  // Remove leftmost, advance left
        }
    }
    
    // If no valid window found, return 0
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

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

Step-by-Step Walkthrough

nums = [1, 4, 4],  target = 4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=0 (1): sum=1 < 4, no shrink
right=1 (4): sum=5 ≥ 4!
  len=1-0+1=2, minLen=2
  sum=5-1=4 ≥ 4!
    len=1-1+1=1, minLen=1  ← EARLY MIN FOUND!
  sum=4-4=0 < 4, stop. left=2
right=2 (4): sum=4 ≥ 4!
  len=2-2+1=1, minLen=1 (same)
  sum=4-4=0 < 4, stop. left=3

✅ Return 1  (single element 4 already = target)

Deep Insight

**Why is the shrinking loop correct?**

After each `sum -= nums[left++]`, if sum is still ≥ target, we found a SHORTER valid window. We keep shrinking to find the MINIMUM. This is correct because all numbers are positive — removing from the left always decreases the sum.

**Key difference from sw-2:** This problem is identical to sw-2 (Smallest Subarray with a Given Sum). They appear as separate problems in the curriculum to reinforce the pattern. Same algorithm, same complexity.

**Binary search alternative (for completeness):** For each left, use binary search to find the minimum right such that prefix_sum[right] - prefix_sum[left-1] ≥ target. O(n log n) time. The sliding window is faster at O(n).

**Why only works with positive numbers?** If numbers could be negative, shrinking from the left might increase the sum, making the invariant invalid. For negative numbers, use deque-based approaches or Kadane's algorithm variants.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n²)	O(1)	All possible subarrays checked
Optimal	O(n)	O(1)	Amortized O(1) per element: each added and removed at most once

Pattern Recognition

✅ Minimum length subarray with sum ≥ target
✅ All positive numbers (enables shrinking invariant)
✅ Variable sliding window: expand to reach target, shrink to minimize
✅ Identical pattern to sw-2

**LeetCode Trigger Phrases:**
→ "minimum size subarray sum"
→ "smallest contiguous subarray" + "sum at least"
→ "positive integers" + minimize subarray + sum constraint

Subhashitam (echoed in Gita 3.12)

दानं भोगो नाशस्तिस्रो गतयो भवन्ति वित्तस्य। यो न ददाति न भुङ्क्ते तस्य तृतीया गतिर्भवति॥

Wealth has three paths: giving, enjoying, or losing. One who neither gives nor enjoys — for them, the third fate (loss) is certain.

Connection: Karna's greatest virtue was his generosity — he gave the minimum that satisfied the divine requirement, and it was accepted in full. The algorithm finds the minimum window that meets the sum target, just as Karna found the minimum donation that fulfilled Indra's demand. True generosity (and true algorithmic efficiency) is not about giving the maximum — it is about finding the precise minimum that accomplishes the goal.