Shortest stretch that reaches the target

Medium

2000 ms limit256 MB memoryArrays Sliding window

Stuck?

Show a hint

Grow the window on the right until the sum reaches the target, then shrink from the left while it still does, recording the length each time.

The ideas behind this problem

Two pointers: replacing a nested loop with a single pass Sliding windows: fixed size, then variable Carrying an answer forward: Kadane's algorithm Binary search on the answer, when nothing is sorted

Next in this lesson

Longest stretch with no repeats

Given a list of positive numbers and a target, find the length of the shortest run of neighbouring values whose sum is at least the target. Return 0 if no run reaches it.

Worked example#

For target 7 and [2, 3, 1, 2, 4, 3], grow a window on the right, and whenever it reaches the target, shrink it from the left for as long as it still reaches:

add	window	sum	at target?	action
2	[2]	2	no	keep growing
3	[2, 3]	5	no	keep growing
1	[2, 3, 1]	6	no	keep growing
2	[2, 3, 1, 2]	8	yes	length 4 is the best so far, now shrink
	[3, 1, 2]	6	no	stop shrinking, grow again
4	[3, 1, 2, 4]	10	yes	shrink
	[1, 2, 4]	7	yes	length 3, still at target, shrink
	[2, 4]	6	no	grow
3	[2, 4, 3]	9	yes	shrink
	[4, 3]	7	yes	length 2, shrink
	[3]	3	no	grow, input ends

The answer is 2.

All the values are positive, which is what makes the window work: adding on the right can only raise the sum, and removing from the left can only lower it. So once the window falls below the target there is no reason to shrink further, and once it reaches the target there is no reason to grow. Each index is added once and removed once, so this is one pass no matter how much the window moves.

Constraints#

1 <= n <= 200000
1 <= nums[i] <= 10000
1 <= target <= 1000000000

Input

target is one integer, then nums is a count followed by that many integers.

Output

The shortest qualifying length, or 0 if there is none.

Examples

Input

7
6
2 3 1 2 4 3

Output

The run [4, 3] sums to 7, and no single value reaches 7.

Input

4
3
1 4 4

Output

The single value 4 already reaches the target.

Input

11
8
1 1 1 1 1 1 1 1

Output

Everything together only sums to 8, so nothing reaches 11.

Something wrong with this problem? Report an issue

Ready to try it

Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.

Create a free account Sign in

Free, and it stays free. No card.