Shortest Stretch With Losses

HardSliding Window

Problem

A trader's daily profit and loss is recorded in nums; values can be negative. Find the shortest run of consecutive days whose total profit is at least `target`.

Return its length, or -1 if no run reaches target.

Example 1

Input:
nums = [3, -2, 4, -1, 2], target = 5
Output:
3

3 - 2 + 4 = 5 and 4 - 1 + 2 = 5. No two adjacent days add up to 5.

Example 2

Input:
nums = [1, 2], target = 4
Output:
-1

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • -10^5 ≤ nums[i] ≤ 10^5
  • 1 ≤ target ≤ 10^9

Hint

Show the first hint

With negatives, shrinking the window can raise the sum, so the usual two pointers fail. Think in prefix sums: the sum of nums[i..j-1] is P[j] - P[i].

Walkthrough

How to approach it

01Clarify before coding

  • Can values be negative? Yes; that rules out the simple shrinking window.
  • Can target be ≤ 0? No, target ≥ 1 here.
  • What if nothing qualifies? Return -1.

02Brute force

Compute prefix sums, then for every pair i < j test P[j] - P[i] ≥ target and keep the smallest j - i.

Cost: O(n²) time, 5·10^9 pairs at n = 10^5.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.