What is the brute force approach and complexity for Shortest Subarray with Sum at Least K?

Build prefix sums, then try every (start, end) pair with time complexity O(N²) and space complexity O(N).

What is the optimal approach and complexity for Shortest Subarray with Sum at Least K?

Deque of starts with increasing P; pop front when it reaches k, pop back when beaten with optimal time complexity O(N) and space complexity O(N).

Shortest Subarray with Sum at Least K

Q: How do you identify the pattern for Shortest Subarray with Sum at Least K?

Look for key signals in the prompt: "shortest subarray with sum at least k" indicates Looks exactly like a variable window problem (Minimum Size Subarray Sum)…; "values may be negative" indicates …but negatives break the window: removing an element can raise the sum. This is the signal to switch to prefix sums.; "smallest j − i with P[j] − P[i] ≥ k" indicates For each end, we want a start that is late and has a small P → keep starts in an increasing monotonic deque..

Hard·LeetCode #862 Pro OnlyTricky / Edge Case

LeetCode

Problem Statement

This one is rated Hard on LeetCode, and it is the trap question of this sub-pattern.

You are given an integer array nums (it can contain negative numbers) and a number k.

Find the shortest non-empty contiguous subarray whose sum is at least k. Return its length. If no such subarray exists, return -1.

Input

An integer array nums of length n (values may be negative), and an integer k.

Output

A single number: the length of the shortest subarray with sum ≥ k, or -1 if there is none.

Example 1

Input: nums = [1], k = 1

Output: 1

The only subarray is [1], and its sum 1 is at least 1.

Example 2

Input: nums = [1, 2], k = 4

Output: -1

The biggest possible sum is 1 + 2 = 3, which is less than 4.

Example 3

Input: nums = [2, -1, 2], k = 3

Output: 3

Only the whole array reaches 3. Note that the −1 sits in the middle and can't be skipped.

Example 4

Input: nums = [84, -37, 32, 40, 95], k = 167

Output: 3

[32, 40, 95] sums to exactly 167. The usual "shrink while sum ≥ k" window returns 5 here — see the trap visual.

Constraints

• 1 ≤ n ≤ 10^5
• −10^5 ≤ nums[i] ≤ 10^5
• 1 ≤ k ≤ 10^9
• Prefix sums can reach 10^10 in size — use a 64-bit type.

Pattern Recognition Clues

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

“shortest subarray with sum at least k”

→ Looks exactly like a variable window problem (Minimum Size Subarray Sum)…

“values may be negative”

→ …but negatives break the window: removing an element can raise the sum. This is the signal to switch to prefix sums.

“smallest j − i with P[j] − P[i] ≥ k”

→ For each end, we want a start that is late and has a small P → keep starts in an increasing monotonic deque.

Approach Complexity Ladder

Brute Force — every pair of prefix sumsO(N²)O(N)

Build prefix sums, then try every (start, end) pair

Better — increasing stack of starts + binary searchO(N log N)O(N)

Drop starts that a later start beats; binary search the rest for each end

Optimal — prefix sums + monotonic increasing dequeO(N)O(N)

Deque of starts with increasing P; pop front when it reaches k, pop back when beaten

Brute Force Intuition

Build the prefix sum array P. Every subarray nums[i … j−1] has sum P[j] − P[i]. Try every pair i < j, and keep the smallest j − i whose sum is at least k.

Recognition rule for this sub-pattern:

You need the max or min of the current window at every step. A deque keeps only elements that could still become the max/min.

Remember this · Sliding Window

Trigger

Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".

Think

Can I keep a valid range and move it, instead of checking every subarray from scratch?

Key question

When is my current window valid?

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 Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Maximum Number of Robots Within Budget