Smallest sum contiguous subarray

Problem Statement

Given an array of integers, find the contiguous subarray with the smallest (minimum) sum.

Example:

• Input: arr = [3, -4, 2, -3, -1, 7, -5]
• Output: -6 (The subarray [-4, 2, -3, -1] has the smallest sum = -6)

Noob-Friendly Explanation

This is the opposite of the famous "Largest Sum Subarray" problem. Instead of finding the stretch with the maximum total, we want to find the stretch with the minimum total. Think of it like finding the deepest valley in a mountain range — which consecutive section dips the lowest? We use a flipped version of Kadane's algorithm to solve this efficiently.

Approach 1: Brute Force

Intuition

Check every possible subarray, calculate its sum, and track the minimum.

Algorithm

1. For each starting index i, iterate through all ending indices j.
2. Keep a running sum and compare with the global minimum.
3. Return the smallest sum found.

class Solution {
    public static int smallestSumBrute(int[] arr) {
        int n = arr.length;
        int minSum = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += arr[j];
                minSum = Math.min(minSum, currentSum);
            }
        }

        return minSum;
    }

    public static void main(String[] args) {
        int[] arr = {3, -4, 2, -3, -1, 7, -5};
        System.out.println(smallestSumBrute(arr)); // Output: -6
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - two nested loops
• Space Complexity: O(1) - only a few variables

Approach 2: Optimal (Reverse Kadane's Algorithm)

Intuition

This is just Kadane's algorithm flipped. At each position, we either extend the current subarray or start a new one. If the running sum becomes positive, reset to 0 because a positive sum would only increase any future subarray sum (and we want to minimize).

Algorithm

1. Initialize currentMin = arr[0] and globalMin = arr[0].
2. For each element from index 1:
   • currentMin = min(arr[i], currentMin + arr[i]).
   • globalMin = min(globalMin, currentMin).
3. Return globalMin.

class Solution {
    public static int smallestSumSubarray(int[] arr) {
        int currentMin = arr[0];
        int globalMin = arr[0];

        for (int i = 1; i < arr.length; i++) {
            // Either start a new subarray at arr[i] or extend the previous one
            currentMin = Math.min(arr[i], currentMin + arr[i]);
            // Update the global minimum
            globalMin = Math.min(globalMin, currentMin);
        }

        return globalMin;
    }

    public static void main(String[] args) {
        int[] arr = {3, -4, 2, -3, -1, 7, -5};
        System.out.println(smallestSumSubarray(arr)); // Output: -6
    }
}

Complexity Analysis

• Time Complexity: O(n) - single pass through the array
• Space Complexity: O(1) - only two variables used