322. Smallest Sum Contiguous Subarray

Given an array of n integers (which may include negative numbers), find the minimum possible sum of any non-empty contiguous subarray.

Input: The first line contains an integer n. The second line contains n space-separated integers (which may be negative), the array. Output: Print a single integer - the minimum sum of any non-empty contiguous subarray.

1 <= n <= 10^5

Initializing BOTH the running current sum and the overall answer to arr[0] (not to 0) is essential, since the subarray must be NON-EMPTY - starting at 0 could incorrectly suggest an empty subarray is a valid (and possibly smaller) answer.

Find the minimum possible sum of any non-empty contiguous subarray. Brute force: Check every possible contiguous subarray directly (two nested loops) and track the minimum sum found - this costs O(n²), too slow for large arrays. Optimised: This is Kadane's algorithm mirrored for finding a MINIMUM - the exact same 'extend or restart' logic, just flipping max() to min(), directly finds the smallest contiguous sum in a single linear pass.

For every starting index i, extend an ending index j from i to the end of the array, maintaining a running sum as j advances, and keep track of the smallest sum encountered across every non-empty contiguous subarray. This is correct because it directly evaluates the sum of every possible contiguous subarray, but doing so for all O(n^2) start/end pairs means a lot of repeated summation work as ranges overlap. Time: O(n^2) Space: O(1)

Split the array into two halves, recursively find the minimum subarray sum entirely within the left half and entirely within the right half, and separately find the minimum sum of a subarray that crosses the midpoint by extending outward from the middle in both directions and tracking the best prefix sum on each side, then combine all three candidates by taking the overall minimum. This is correct because every subarray either lies fully in one half or straddles the midpoint, and these three cases together cover all possibilities; splitting the problem this way reduces the total comparison work compared to checking every pair of indices directly. Time: O(n log n) Space: O(log n)

Scan the array once while maintaining currentMin, the smallest sum of a subarray ending exactly at the current position, updated at each step as min(arr[i], currentMin + arr[i]), and a global minimum that is updated whenever currentMin improves on it. This works because at each position, the best subarray ending there either extends the best subarray ending at the previous position or starts fresh at the current element, whichever gives a smaller sum, and tracking just these two running values removes the need for any recursion or overlapping subproblem recomputation, solving the problem in a single linear sweep. Time: O(n) Space: O(1)

1. This is Kadane's algorithm run for a MINIMUM instead of a maximum: cur[i] = min(arr[i], cur[i-1] + arr[i]). 2. Either START a new subarray at i, or EXTEND the best (smallest) subarray ending at i-1. 3. Track the smallest cur value seen across the whole array as the running answer; initialize both to arr[0] since the subarray must be non-empty.

Time: O(n) - one single pass through the array. Space: O(1) - just two running trackers.

Test n = 1, an array of all positive numbers (the minimum is the smallest single element), an array of all negative numbers (the minimum is the whole array), and n at the upper bound of 10^5.

Be ready to explain that this is literally Kadane's algorithm with every max() swapped for min() - recognizing this direct mirror relationship instantly, rather than deriving the recurrence from scratch, is a strong efficiency signal.