What is the brute force approach and complexity for Minimum Sum Subarray?

For each start, add one number at a time and keep the smallest sum with time complexity O(N^2) and space complexity O(1).

What is the optimal approach and complexity for Minimum Sum Subarray?

Track the smallest sum that ends at each index: extend it or restart with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Minimum Sum Subarray?

Look for key signals in the prompt: "contiguous subarray" indicates A run of neighbours, so think of the smallest run that ends at each index.; "smallest sum" indicates The Kadane rule with min instead of max. Flip the comparison and keep the same shape.; "non-empty" indicates A run must hold at least one number, so `best` starts at a real sum, not at 0..

Minimum Sum Subarray

Easy·GeeksforGeeks Pro OnlyBasic Reinforcement

GeeksforGeeks

Problem Statement

You are given an integer array a of length n. Find a contiguous part of it, a subarray with at least one number, whose sum is as small as possible. Return that smallest sum.

A subarray is a run of neighbouring numbers. It must hold at least one number, so an empty run (sum 0) is not allowed.

GFG's function is int minSubarraySum(vector<int>& arr). The code here returns long long: with up to 10^6 numbers of size 10^7, a sum can reach 10^13, which doesn't fit in an int.

Input

An integer array a of length n.

Output

One number: the smallest sum of any non-empty subarray.

Example 1

Input: a = [3, -4, 2, -3, -1, 7, -5]

Output: -6

The run [-4, 2, -3, -1] adds up to -6. No other run of neighbours goes lower.

Example 2

Input: a = [2, 6, 8, 1, 4]

Output: 1

Every number is positive, so the smallest run is the single smallest number, 1. Adding more numbers only makes the sum bigger.

Example 3

Input: a = [-1, -2, -3]

Output: -6

The whole array is the smallest run: -1 - 2 - 3 = -6.

Constraints

• 1 ≤ n ≤ 10^6
• −10^7 ≤ a[i] ≤ 10^7

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“contiguous subarray”

→ A run of neighbours, so think of the smallest run that ends at each index.

“smallest sum”

→ The Kadane rule with min instead of max. Flip the comparison and keep the same shape.

“non-empty”

→ A run must hold at least one number, so `best` starts at a real sum, not at 0.

Approach Complexity Ladder

Brute Force — running sum from each startO(N^2)O(1)

For each start, add one number at a time and keep the smallest sum

Optimal — min-KadaneO(N)O(1)

Track the smallest sum that ends at each index: extend it or restart

Brute Force Intuition

Try every start l. From each start, add the numbers one at a time, so each new sum is the old sum plus one number, and remember the smallest total.

Recognition rule for this sub-pattern:

cur = max(x, cur + x); best = max(best, cur).

Remember this · DP — Kadane / Subarray

Trigger

Maximum (or minimum) sum/product of a contiguous subarray, stock buy/sell, circular arrays.

Think

Is the best subarray ending at i either "i alone" or "best ending at i−1, plus i"?

Key question

Should I extend or restart?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Kadane / Subarray translate into production architectures and low-level memory mechanics.

LLD Architecture