Find Minimum Sum Subarray

Title: Find Minimum Sum Subarray

In this guide, you’ll learn how to find the minimum sum subarray in an array of integers using a single efficient pass. This is a common array interview question that checks whether you can adapt Kadane's algorithm to minimize a sum instead of maximizing one.

We’ll write a complete Java program that returns the minimum sum along with the start and end indices of the subarray that produces it, trace the algorithm on a sample array one step at a time, and work through examples that cover arrays with mixed signs, all positive values, and all negative values.

Understanding the Problem

Given an array of integers, the task is to find the contiguous subarray, containing at least one element, whose sum is the smallest possible. The subarray does not have to be a single element; a run of several negative numbers in a row can easily beat any individual value.

A brute-force solution checks every subarray and costs O(n^2) time, or O(n^3) if each sum is recomputed from scratch. The efficient approach reuses the running-sum idea from the classic maximum subarray problem, just flipped to track the smallest sum instead of the largest.

Approach

1. Check for the boundary case first: if numbers is null or empty, throw an IllegalArgumentException since there is no subarray to return.
2. Initialize minEndingHere and minSoFar to numbers[0], and set start, end, and tempStart to 0.
3. Loop through the array starting at index 1.
4. At each index i, compare minEndingHere + numbers[i] against numbers[i] alone to decide whether extending the current run still gives a smaller sum.
5. If extending gives a smaller sum, add numbers[i] to minEndingHere; otherwise, restart the run by setting minEndingHere = numbers[i] and tempStart = i.
6. Whenever minEndingHere drops below minSoFar, update minSoFar and record start = tempStart and end = i.
7. After the loop finishes, minSoFar is the minimum subarray sum, and start/end mark its boundaries.

Java Program

public class MinimumSumSubarray {

    public static int[] findMinimumSumSubarray(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            throw new IllegalArgumentException("Input array must not be null or empty");
        }

        int minEndingHere = numbers[0];
        int minSoFar = numbers[0];
        int start = 0;
        int end = 0;
        int tempStart = 0;

        for (int i = 1; i < numbers.length; i++) {
            if (minEndingHere + numbers[i] < numbers[i]) {
                minEndingHere = minEndingHere + numbers[i];
            } else {
                minEndingHere = numbers[i];
                tempStart = i;
            }

            if (minEndingHere < minSoFar) {
                minSoFar = minEndingHere;
                start = tempStart;
                end = i;
            }
        }

        return new int[] {minSoFar, start, end};
    }

    public static void main(String[] args) {
        int[] numbers = {3, -4, 2, -3, -1, 7, -5};
        int[] result = findMinimumSumSubarray(numbers);

        System.out.println("Minimum sum: " + result[0]);
        System.out.println("Subarray starts at index: " + result[1]);
        System.out.println("Subarray ends at index: " + result[2]);
    }
}

Explanation of the Program

• minEndingHere tracks the smallest sum of any subarray that ends exactly at the current index.
• At every step, the algorithm checks whether continuing the previous run beats starting fresh at numbers[i].
• minSoFar remembers the best (smallest) sum found across all positions visited so far.
• tempStart records where the current run began, so start can be set correctly the moment minSoFar improves, without rescanning the array.
• The method returns the sum together with its boundary indices, so a caller can slice the actual subarray out of numbers if needed.

Step-by-Step Trace

For the array [8, -3, -5, 4, -2, 6, -7, 2], the algorithm finds a minimum sum of -8 coming from the subarray [-3, -5] at indices 1 and 2:

At the end of each iteration i, minSoFar holds the minimum subarray sum found anywhere within numbers[0..i].

Examples

The examples below use fresh inputs to show how the algorithm behaves when the array has mixed signs, only positive values, and only negative values.

Example 1: A Mix of Positive and Negative Numbers

With a short run of negative numbers surrounded by positive values, the minimum sum should come from just that negative run.

int[] numbers = {5, -2, -3, 10, -1};
int[] result = MinimumSumSubarray.findMinimumSumSubarray(numbers);
System.out.println("Minimum sum: " + result[0] + ", from index " + result[1] + " to " + result[2]);
// Output: Minimum sum: -5, from index 1 to 2

The subarray [-2, -3] at indices 1 to 2 sums to -5, which beats every other contiguous slice of this array.

Example 2: All Positive Elements

When every element is positive, extending a run only increases the sum, so the minimum sum subarray should collapse to the single smallest element.

int[] numbers = {4, 2, 6, 1, 3};
int[] result = MinimumSumSubarray.findMinimumSumSubarray(numbers);
System.out.println("Minimum sum: " + result[0] + ", from index " + result[1] + " to " + result[2]);
// Output: Minimum sum: 1, from index 3 to 3

The algorithm correctly isolates 1 at index 3 as its own one-element subarray, since adding any neighbor would only make the sum larger.

Example 3: All Negative Elements

When every element is negative, extending a run always decreases the sum further, so the minimum sum subarray should be the entire array.

int[] numbers = {-2, -5, -1, -4};
int[] result = MinimumSumSubarray.findMinimumSumSubarray(numbers);
System.out.println("Minimum sum: " + result[0] + ", from index " + result[1] + " to " + result[2]);
// Output: Minimum sum: -12, from index 0 to 3

The algorithm returns the full array as the minimum sum subarray, with a total sum of -12, confirming that extending never hurts when every value is negative.

Common Mistakes to Avoid

These are the mistakes that most often trip up learners solving this exact problem.

• Initializing minSoFar = 0 – fails on arrays where every element is positive, since 0 is wrongly reported as the minimum sum instead of the smallest actual element. Initialize minSoFar to numbers[0] instead.
• Forgetting to update tempStart on restart – the reported sum stays correct, but the returned start index points to the wrong element. Update tempStart every time minEndingHere resets to numbers[i].
• Using <= instead of < when deciding to extend – on a tie it needlessly extends the earlier run instead of restarting, producing a different but equally valid index range that will not match an expected dry-run trace. Use a strict < comparison.
• Confusing minimum subarray with minimum element – stopping at scanning for the single smallest value misses that several consecutive negative numbers can sum lower than any one of them. Always extend the running sum, not just track the smallest item seen.
• Skipping the null or empty array check – a null reference throws a NullPointerException deep inside the loop instead of a clear error at the boundary, and an empty array has no subarray to return. Validate the input first and throw IllegalArgumentException.

Edge Cases to Test

Walking through these inputs out loud is exactly what an interviewer wants to see before you call the problem solved.

• Empty array
• Single-element array
• All positive elements
• All negative elements
• All identical elements
• Minimum subarray at the start of the array
• Minimum subarray at the end of the array
• Null array reference

Additional Considerations

The algorithm runs in O(n) time since it visits each element exactly once, and it uses O(1) extra space beyond the input array, holding only a handful of scalar variables regardless of the array’s size.

Compare this to the brute-force approach, which costs O(n^2) or worse. The single-pass version trades a small amount of conceptual complexity, tracking two running values instead of one, for a large constant-factor and asymptotic win, which is exactly the kind of trade-off interviewers want you to identify unprompted.

Interview Follow-up Questions

Once you’ve solved the base problem, expect an interviewer to push further with questions like these.

• What if you need the minimum sum subarray of a fixed size k? – use a sliding window of width k, adding the entering element and subtracting the leaving element as the window moves, still O(n).
• What if the array is circular, wrapping from the last element back to the first? – the minimum circular subarray sum equals the total array sum minus the maximum subarray sum of the linear array, with a special case when every element is negative.
• What if the values arrive as a stream and the full array cannot be stored? – keep only minEndingHere and minSoFar and update them as each value arrives, since the recurrence never looks backward further than the previous element.
• What if you need the K smallest-sum subarrays instead of just one? – this is harder because candidate subarrays can overlap; a common approach tracks a bounded set of candidate sums rather than a single running minimum.
• What if you must solve it with read-only input and cannot use extra memory for indices? – drop start, end, and tempStart and keep only the two running sum scalars, returning just the minimum value.

Conclusion

Finding the minimum sum subarray is a short but effective test of whether you can bend a well-known pattern, Kadane’s algorithm, to a new goal instead of memorizing it for one specific problem. The same running-sum idea, minimizing instead of maximizing, shows up across many array problems once you recognize it.

Try adapting this code to return the subarray itself instead of just its indices, or to solve the fixed-size and circular-array follow-ups above. You can find more problems like this one in the Arrays category on this site.