Skip to main content

80. Minimum Size Subarray Sum

mediumAsked at Datadog

Find the minimum length contiguous subarray whose sum is at least target. Datadog asks this for the variable-size sliding-window pattern — same shape as their alert-window optimization over a metric stream.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — direct alert-window analog.
  • Blind (2025-10)— Recurring Datadog problem.

Problem

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Constraints

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4

Examples

Example 1

Input
target = 7, nums = [2,3,1,2,4,3]
Output
2

Explanation: [4,3] has min length 2.

Example 2

Input
target = 4, nums = [1,4,4]
Output
1

Example 3

Input
target = 11, nums = [1,1,1,1,1,1,1,1]
Output
0

Approaches

1. Brute force

All (i, j) subarrays.

Time
O(n^2)
Space
O(1)
// Two loops; track min length where sum >= target.

Tradeoff: Quadratic — fails on 10^5 inputs.

2. Sliding window (optimal)

Expand right; when window sum >= target, shrink left while still >= target; track min length.

Time
O(n)
Space
O(1)
function minSubArrayLen(target, nums) {
  let left = 0, sum = 0, best = Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) {
      best = Math.min(best, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }
  return best === Infinity ? 0 : best;
}

Tradeoff: Single pass. Each element entered/exited once: O(n) total. Datadog-canonical variable-size window.

Datadog-specific tips

Datadog will follow up with: 'What if nums contains negatives?' Sliding window breaks — switch to prefix-sum + deque (monotonic). Articulate why: the shrink invariant relies on positive contributions.

Common mistakes

  • Using a fixed-size window — wrong, the size varies.
  • Shrinking eagerly while sum < target — could over-shrink.
  • Returning Infinity directly instead of 0 — the problem requires 0 when no answer.

Follow-up questions

An interviewer at Datadog may pivot to one of these next:

  • Subarray Sum Equals K (LC 560) — exact sum, prefix-sum + hashmap.
  • Longest Subarray with Sum <= K — sliding window inverse.
  • Datadog-style: minimum alert window over a positive-valued metric stream.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does sliding window work here?

All values are positive: extending right only grows sum, shrinking left only shrinks sum. So the window is monotonic.

What if all-zero or negatives?

Sliding window breaks. Use prefix-sum + monotonic deque or hashmap.

Practice these live with InterviewChamp.AI

Drill Minimum Size Subarray Sum and other Datadog interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →