Skip to content
Katabench
Try free

Shortest Subarray With Sum at Least K

Hard About 45 min Free, no account needed

Find the shortest target-reaching interval when negative values break the usual window.

The brief

Given an integer array nums, which may contain positive numbers, zeroes, and negative numbers, and a positive long value target, return the length of the shortest non-empty contiguous subarray whose sum is at least target. Return -1 when no such subarray exists.

Use long arithmetic for running sums. The sum of several int values may be outside the int range.

Examples

Text
nums = [2, -1, 2], target = 3
answer = 3

nums = [84, -37, 32, 40, 95], target = 167
answer = 3

In the second example, [32, 40, 95] is the shortest qualifying subarray.

The performance bar

The honest obvious approach starts at every index and extends a running sum to each possible end. That checks quadratically many ranges and takes O(n²) time. The hidden test has 200,000 elements and makes that approach perform billions of additions.

The usual shrinking sliding window for positive numbers is not correct here. Adding a negative value can lower the sum, and removing a negative value can raise it. Find an O(n) approach that remains correct with either sign.

Starter code

C#
using System;

public class Solution
{
    // TODO: return the shortest non-empty subarray with sum at least target, or -1 if none exists.
    public int ShortestSubarray(int[] nums, long target)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Prefix sums
Carry running totals or prefix state so any range question becomes a lookup.
Monotonic stack
Keep a stack in sorted order to answer next-greater and span questions in one pass.

Do these first

Related katas