Shortest run that adds up to the target

Scenario

A banking app records the change in a balance at the end of each day. A deposit is a positive number and a withdrawal is a negative number.

A user sees that the balance moved by an amount they do not recognise and taps "Explain this change". The app looks for the shortest stretch of consecutive days whose changes add up to exactly that amount. A short stretch is the easiest for the user to check. A stretch that only comes close, or goes past the amount, explains nothing.

Your task

Write shortest_run(changes, target).

changes[i] is the change in the balance on the (i + 1)-th day. It can be negative or zero.
A stretch is one or more consecutive days. An empty stretch does not count.
Return the length of the shortest stretch whose changes add up to exactly target.
Return -1 when no stretch adds up to target.

Examples

Example 1 (traced)#

text2 lines

Input:  changes = [-3, -3, 1, 2, -3, 3], target = 3
Output: 1

The trace keeps the running total and, for each total, the latest position where it occurred. Position 0 is the empty start, with total 0. A stretch ends at the current position for each earlier position whose total is total - 3.

Position	Change	Running total	Looks up (total − 3)	Found at	Best length	Latest positions after
0	start	0			none	0: 0
1	−3	−3	−6, not there		none	adds −3: 1
2	−3	−6	−9, not there		none	adds −6: 2
3	1	−5	−8, not there		none	adds −5: 3
4	2	−3	−6	position 2	2	−3: 4
5	−3	−6	−9, not there		2	−6: 5
6	3	−3	−6	position 5	1	−3: 6

At position 4, the third and fourth days (changes 1 and 2) add up to 3. At position 6, the total −6 was last seen at position 5, so the sixth day alone adds up to 3. The output is 1.

Example 2#

text2 lines

Input:  changes = [1, 2, 3], target = 10
Output: -1

The whole list adds up to 6, so no stretch reaches 10.

Example 3#

text2 lines

Input:  changes = [5, 0, -5], target = 0
Output: 1

The second day alone has change 0. The whole list also adds up to 0, but it is longer.

Constraints

0 ≤ changes.length ≤ 100,000 (days in the history)
-10^6 ≤ changes[i] ≤ 10^6 (change of one day)
-10^9 ≤ target ≤ 10^9

What does n ≤ 10^5 tell you?

Trying every start and extending the stretch one day at a time costs about n × n / 2 steps. For 100,000 days that is about 5 × 10^9, far over the budget of about 10^8 a second. Running totals can reach 10^11, so they need 64 bits in Java and C++.

Scenario

A banking app records the change in a balance at the end of each day. A deposit is a positive number and a withdrawal is a negative number.

Your task

Write shortest_run(changes, target).

changes[i] is the change in the balance on the (i + 1)-th day. It can be negative or zero.
A stretch is one or more consecutive days. An empty stretch does not count.
Return the length of the shortest stretch whose changes add up to exactly target.
Return -1 when no stretch adds up to target.

Examples

Example 1 (traced)#

text2 lines

Input:  changes = [-3, -3, 1, 2, -3, 3], target = 3
Output: 1

Position	Change	Running total	Looks up (total − 3)	Found at	Best length	Latest positions after
0	start	0			none	0: 0
1	−3	−3	−6, not there		none	adds −3: 1
2	−3	−6	−9, not there		none	adds −6: 2
3	1	−5	−8, not there		none	adds −5: 3
4	2	−3	−6	position 2	2	−3: 4
5	−3	−6	−9, not there		2	−6: 5
6	3	−3	−6	position 5	1	−3: 6

At position 4, the third and fourth days (changes 1 and 2) add up to 3. At position 6, the total −6 was last seen at position 5, so the sixth day alone adds up to 3. The output is 1.

Example 2#

text2 lines

Input:  changes = [1, 2, 3], target = 10
Output: -1

The whole list adds up to 6, so no stretch reaches 10.

Example 3#

text2 lines

Input:  changes = [5, 0, -5], target = 0
Output: 1

The second day alone has change 0. The whole list also adds up to 0, but it is longer.

Constraints

0 ≤ changes.length ≤ 100,000 (days in the history)
-10^6 ≤ changes[i] ≤ 10^6 (change of one day)
-10^9 ≤ target ≤ 10^9

What does n ≤ 10^5 tell you?