Minimum Size Subarray Sum
Medium About 20 min Free, no account needed
The shortest window of positive numbers reaching a target sum.
The brief
Given an array of positive integers nums and a positive target, return
the length of the shortest contiguous subarray whose sum is at least
target, or 0 if none exists.
The obvious approach grows a sum from every starting index, O(n2) when the qualifying windows are long. The hidden test needs windows of 100,000 elements out of 200,000, so the quadratic version is too slow. You will need an approach where the work stays close to O(n).
Starter code
using System;
public class Solution
{
// TODO: return the length of the shortest contiguous subarray summing to at least target (0 if none).
public int MinSubarrayLen(int[] nums, int 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
- Sliding window
- Grow and shrink a contiguous range while maintaining its state incrementally.
Related katas
- Find All Anagram Start Indices Medium Free Every position where an anagram of the pattern begins.
- Fruit Into Baskets Medium Free Longest stretch of trees using at most two fruit types.
- Longest Repeating Character Replacement Medium Free Longest uniform run you can create with k character replacements.
- Longest Rising Streak Easy Free Measure a consecutive telemetry climb without rescanning every possible starting point.