Smallest sum contiguous subarray

The problem, simply

You get a list of whole numbers, some positive and some negative. Look at every stretch of numbers that sit next to each other (at least one number). Give back the smallest sum any stretch can have.

It is the mirror image of the famous "largest sum stretch" problem.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every start. From each start, walk right and keep a running sum. Every time the running sum is a new low, remember it.

1. For each start i, set sum = 0.
2. For each end j from i onward, add a[j] and compare sum with the smallest seen.

class Solution {
    public int smallestSumSubarray(int[] a) {
        int best = Integer.MAX_VALUE;
        for (int i = 0; i < a.length; i++) {        // every start
            int sum = 0;
            for (int j = i; j < a.length; j++) {    // every end
                sum += a[j];
                best = Math.min(best, sum);
            }
        }
        return best;
    }
}

How long it takes: about n * n / 2 stretches, O(n^2). Extra room: two numbers, O(1).

Way 2: the clever way

Keep the worst streak that ends today, and the worst streak ever.

1. Start both at a[0].
2. For each next number x: endHere = min(x, endHere + x). Either start fresh with x, or carry yesterday's streak.
3. best = min(best, endHere).

Each endHere only needs the one before it, so this is a tiny DP with one box of memory.

class Solution {
    public int smallestSumSubarray(int[] a) {
        int endHere = a[0];      // smallest sum of a stretch ending at this day
        int best = a[0];         // smallest sum seen anywhere
        for (int i = 1; i < a.length; i++) {
            endHere = Math.min(a[i], endHere + a[i]);  // start fresh or carry on
            best = Math.min(best, endHere);
        }
        return best;
    }
}

How long it takes: one walk, O(n). Extra room: two numbers, O(1).

Watch out for

• The stretch must be at least one number long. An empty stretch with sum 0 does not count.
• Resetting to 0 instead of to a[i]. The textbook "reset when positive" version works only if you compare before resetting. min(a[i], endHere + a[i]) avoids the trap.
• Very large sums can overflow int. Use long if numbers can be near a billion.

What interviewers ask next

• Can you reuse the largest sum code? Yes. Flip the sign of every number, find the largest sum stretch, and flip the answer back.
• Return the start and end of the stretch. Remember where the current streak started each time you start fresh, and copy it when you find a new best.
• Maximum sum in a circular array (LeetCode 918). The best wrap around stretch is total - smallest stretch. So you need exactly this problem.
• Smallest sum stretch of length at least k. Use running totals (prefix sums) and keep the largest prefix that is at least k positions back.

Remember this

Grown-up words: a stretch is a contiguous subarray, the worst streak ending today is the DP state minEndingHere, the whole trick is Kadane's algorithm, and running totals are prefix sums.