Shortest Subarray with Sum at Least K - Practice Coding Problems

Shortest Subarray with Sum at Least K - Problem

Array Binary Search Queue Sliding Window Heap (Priority Queue) Prefix Sum Monotonic Queue Hard

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

Input & Output

Example 1 — Basic Case

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

› Output: 1

💡 Note: The subarray [4] has sum 4 which is ≥ 4, and length 1 is the shortest possible

Example 2 — Multiple Elements Needed

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

› Output: 3

💡 Note: The subarray [2,1,2] has sum 5 ≥ 4, and we need all 3 elements to reach the target

Example 3 — No Valid Subarray

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

› Output: -1

💡 Note: No subarray has sum ≥ 4, so we return -1

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁵ ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,4,0,-1] and target k=4

Process

Find shortest subarray with sum ≥ 4

Output

Return length 1 (subarray [4])

Key Takeaway

🎯 Key Insight: Use prefix sums with monotonic deque to efficiently track optimal starting positions for minimum length subarrays

Asked in

G Google 45 a Amazon 38 f Meta 32 M Microsoft 28

The key insight is to use prefix sums to convert the problem into finding the shortest distance between two prefix sum values that differ by at least k. The optimal approach uses a monotonic deque to maintain candidates efficiently. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum with Monotonic Deque	O(n)	O(n)	Use prefix sums and monotonic deque to find optimal subarray efficiently
Brute Force	O(n²)	O(1)	Check all possible subarrays and find the shortest one with sum ≥ k

Prefix Sum with Monotonic Deque — Algorithm Steps

Build prefix sum array
Use deque to store indices in increasing order of prefix sums
For each position, find valid starting points using deque
Update minimum length and maintain deque property

Visualization

Tap to expand

Step-by-Step Walkthrough

Prefix Sums

Convert to prefix sum problem

Monotonic Deque

Maintain optimal candidates

Result

Find minimum length efficiently

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int numsSize, int k) {
    long long* prefix = (long long*)calloc(numsSize + 1, sizeof(long long));
    
    // Build prefix sum array
    for (int i = 0; i < numsSize; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    
    int minLen = INT_MAX;
    int* dq = (int*)malloc((numsSize + 1) * sizeof(int));
    int front = 0, back = 0;
    
    for (int j = 0; j <= numsSize; j++) {
        // Remove indices where prefix[j] - prefix[dq[front]] >= k
        while (front < back && prefix[j] - prefix[dq[front]] >= k) {
            int len = j - dq[front];
            if (len < minLen) {
                minLen = len;
            }
            front++;
        }
        
        // Maintain monotonic property
        while (front < back && prefix[dq[back - 1]] >= prefix[j]) {
            back--;
        }
        
        dq[back++] = j;
    }
    
    free(prefix);
    free(dq);
    return minLen == INT_MAX ? -1 : minLen;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, each element added/removed from deque at most once

✓ Linear Growth

Space Complexity

O(n)

Prefix sum array and deque both store up to n elements

⚡ Linearithmic Space

78.4K Views

Medium Frequency

~35 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum with Monotonic Deque — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler