Kadane's AlgorithmMediumO(n) time · O(1) space

Minimum Subarray Sum

Mahabharata — Duryodhana's Counsel — Finding the Deepest Pandava Defeat in the Battle Record

न्यूनतमं दुःखं यत्र संग्रहीतम् एकत्र। तत् खण्डं जानन् नेता शत्रोः क्षतिं ज्ञायते॥

*The segment where the minimum accumulated suffering is concentrated — knowing it, the leader understands the enemy's deepest wound.*

The Story

While Vidura was showing Dhritarashtra the Pandava momentum peaks, Duryodhana entered the chamber with a counter-demand: "Show me the WORST stretch for the Pandavas. I want the contiguous sequence of battle actions that represents their deepest cumulative loss."

Sanjaya understood the request: find the contiguous subarray with the MINIMUM (most negative) sum.

"This is the mirror of Kadane's maximum algorithm," Vidura murmured. "Every 'max' becomes 'min', every advantage becomes disadvantage."

Duryodhana pointed to the battle record: `[3, -4, 2, -3, -1, 7, -5]`

"I want the worst stretch — the one where the Pandavas lost the most consecutively."

Vidura inverted Kadane's insight:

"At each position i, we ask: should the current 'loss streak' EXTEND the previous one, or START A NEW MINIMUM STREAK at position i?"

"A loss streak should be extended if it makes the sum even more negative — i.e., if `currMin + nums[i] < nums[i]`, meaning the accumulated negative momentum drags us even lower."

"This simplifies to: `currMin = min(nums[i], currMin + nums[i])`."

Vidura traced through `[3, -4, 2, -3, -1, 7, -5]`:

- i=0: currMin=3, minSum=3 - i=1: currMin=min(-4, 3-4)=min(-4,-1)=-4. minSum=-4 - i=2: currMin=min(2, -4+2)=min(2,-2)=-2. minSum=-4 - i=3: currMin=min(-3, -2-3)=min(-3,-5)=-5. minSum=-5 - i=4: currMin=min(-1, -5-1)=min(-1,-6)=-6. minSum=-6 - i=5: currMin=min(7, -6+7)=min(7,1)=1. minSum=-6 - i=6: currMin=min(-5, 1-5)=min(-5,-4)=-5. minSum=-6

"The minimum subarray sum is -6," Vidura announced. "The stretch `[-4, 2, -3, -1]` from indices 1 to 4."

Duryodhana was pleased. "So the Pandavas suffered a cumulative loss of 6 during that sequence."

"Yes. And notice," Vidura added, "the logic is perfectly symmetric with the maximum version:" - Maximum: `currSum = max(nums[i], currSum + nums[i])` — reset when sum goes negative - Minimum: `currMin = min(nums[i], currMin + nums[i])` — reset when sum goes positive

"For minimum, we reset when the running sum becomes POSITIVE — because positive momentum is a burden for the 'minimum seeker.'"

Duryodhana committed the stretch to memory. The counsel of Vidura had once again revealed the mathematical structure hidden within the chaos of battle.

"One pass, O(1) space, complete answer," Vidura said. "The minimum and maximum are both found by the same technique — just with inverted comparison operators."

This is Kadane's Algorithm inverted for finding the minimum subarray sum.

Sanjaya's First Instinct

Check every start-end pair. Compute sum for each. Track the minimum. O(n²) time.

java

int smallestSumSubarrayBruteForce(int[] a) {
    int minSum = Integer.MAX_VALUE;
    
    for (int start = 0; start < a.length; start++) {
        int sum = 0;
        for (int end = start; end < a.length; end++) {
            sum += a[end];
            minSum = Math.min(minSum, sum);
        }
    }
    
    return minSum;
}

Vidura's Inverted Wisdom

Mirror of Kadane's maximum algorithm. At each step: `currMin = min(nums[i], currMin + nums[i])` If `currMin > 0` (positive momentum), reset to just `nums[i]` — positive baggage hurts the minimum seeker. Track the global minimum across all steps.

java

int smallestSumSubarray(int[] a) {
    int minSum = a[0];  // Best (most negative) sum seen so far
    int curr = a[0];    // Best minimum sum ending at current position
    
    for (int i = 1; i < a.length; i++) {
        // Extend previous OR start fresh — take the minimum
        curr = Math.min(a[i], curr + a[i]);
        minSum = Math.min(minSum, curr);
    }
    
    return minSum;
}

// Equivalent: reset when curr > 0
int smallestSumAlt(int[] a) {
    int minSum = a[0], curr = a[0];
    for (int i = 1; i < a.length; i++) {
        if (curr > 0) curr = 0;  // Positive momentum is a burden — reset
        curr += a[i];
        minSum = Math.min(minSum, curr);
    }
    return minSum;
}

// Test
public static void main(String[] args) {
    int[] a = {3, -4, 2, -3, -1, 7, -5};
    System.out.println(smallestSumSubarray(a));  // -6 (subarray [-4,2,-3,-1])
    
    int[] allPos = {1, 2, 3};
    System.out.println(smallestSumSubarray(allPos));  // 1 (single element, least positive)
}

Step-by-Step Walkthrough

a = [2, 3, -8, 1, -2]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=0 (init): curr=2, minSum=2

i=1: curr = min(3, 2+3) = min(3,5) = 3. minSum=2
  (both positive, must take smaller: fresh start at 3? No: both positive so fresh is 3, extend is 5. min=3)

i=2: curr = min(-8, 3+(-8)) = min(-8,-5) = -8. minSum=-8
  (starting fresh at -8 is worse than extending: -5 vs -8. Take -8)

i=3: curr = min(1, -8+1) = min(1,-7) = -7. minSum=-8

i=4: curr = min(-2, -7+(-2)) = min(-2,-9) = -9. minSum=-9

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Return -9  (subarray [-8,1,-2] = -9)

Deep Insight

**Symmetry with the maximum version:** | Maximum Kadane | Minimum Kadane | |---|---| | `max(nums[i], curr+nums[i])` | `min(nums[i], curr+nums[i])` | | Reset when `curr < 0` | Reset when `curr > 0` | | Track `maxSum` | Track `minSum` | | Initialize `maxSum = nums[0]` | Initialize `minSum = nums[0]` |

**All-positive arrays:** The minimum is the smallest single element (the algorithm always resets after a positive element since positive values drag the minimum up).

**Relationship to Maximum:** `min_subarray_sum(A) = -max_subarray_sum(-A)`. You can negate the array, find max, then negate back.

**Real-world use:** Financial analysis — find the worst consecutive period in a stock's returns. Load analysis — find the period of minimum resource consumption.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n²)	O(1)	All O(n²) subarrays checked
Optimal	O(n)	O(1)	Single pass, two variables: curr and minSum

Pattern Recognition

✅ Minimum sum contiguous subarray
✅ Array contains both positive and negative numbers
✅ Mirror of Kadane's maximum — just flip min/max and reset condition
✅ O(1) space DP

**LeetCode Trigger Phrases:**
→ "minimum subarray sum"
→ "most negative contiguous subarray"
→ "smallest sum subarray"

Bhagavad Gita 2.56

दुःखेष्वनुद्विग्नमनाः सुखेषु विगतस्पृहः। वीतरागभयक्रोधः स्थितधीर्मुनिरुच्यते॥

One who is not disturbed even in the threefold miseries, who is not elated when there is happiness, and who is free from attachment, fear, and anger, is called a sage of steady wisdom.

Connection: The minimum subarray algorithm seeks the deepest valley of negative accumulation — but like the sage of steady wisdom, the algorithm is not disturbed by it. It merely tracks the lowest point with equanimity, neither fleeing from negative values nor clinging to positive ones. When positive values arrive (which would 'raise' the minimum), the algorithm resets without attachment — exactly as the sage releases pleasure without becoming bound by it.