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.
nums = [2, -1, 2], target = 3
answer = 3
nums = [84, -37, 32, 40, 95], target = 167
answer = 3In the second example, [32, 40, 95] is the shortest qualifying subarray.
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
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.
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
- Count Bounded Range Sums Hard Free Count signed subarray totals inside an inclusive band without enumerating quadratic pairs.
- Largest Rectangle in Histogram Hard Free The biggest rectangle that fits under the bars.
- Longest Well-Performing Interval Hard Free Longest stretch of days with more tiring days than easy ones.
- Sum of Subarray Minimums Hard Free Add the minimum of every contiguous subarray - by counting, not enumerating.