Shortest Stretch Reaching a Total

Hard

A small coffee shop records its profit for each day in the array profits; bad days are negative. The owner wants the shortest stretch of consecutive days whose total profit is at least goal. Return the length of that stretch (the number of days in it, at least one). If no unbroken stretch reaches goal, return -1.

Example 1

profits=[3, -4, 2, 5, -1, 4], goal=7 → 2

The consecutive days 2, 5 add up to exactly 7, which is 2 days. A single day is not enough: the best day brings 5.

Example 2

profits=[4, -10, 4], goal=5 → -1

The two profitable days are split by a loss, and no unbroken stretch reaches 5. The answer is -1.

Example 3

profits=[1, 1, 1, 1], goal=4 → 4

Only all four days together reach 4.

Constraints

1 ≤ len(profits) ≤ 10⁵
-10⁵ ≤ profits[i] ≤ 10⁵
1 ≤ goal ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Queue Array Binary Search Prefix Sum Sliding Window Monotonic Queue Heap (Priority Queue)

Similar problems

Longest Affordable Run of Machines Hard Moving Window Maximum Hard A Dark Gap Between Street Lamps Hard Maximum Sum With Short Hops Hard Best Pair of Close Beacons Hard

Input

profits=[3, -4, 2, 5, -1, 4], goal=7

Expected

Run checks the first 3 tests in your browser. Submit checks all 126 tests on the server, hidden ones included.