Trim the Ends to a Target

Medium

Boxes stand in a row on a shelf; their weights are given in weights. In one move you take off an end box, either the leftmost or the rightmost one. You need to take off boxes whose total weight is exactly target. Return the fewest moves that achieve this, or -1 if a total of exactly target cannot be reached.

Example 1

weights=[3, 1, 7, 2, 2], target=6 → 3

Taking 3 and 1 from the left and 2 from the right gives 6 in three moves; fewer moves cannot reach exactly 6.

Example 2

weights=[4, 9, 4], target=5 → -1

From the ends you can reach 4, 8, 13 or 17, but never 5.

Example 3

weights=[2, 5, 1], target=8 → 3

Constraints

1 ≤ len(weights) ≤ 10⁵
1 ≤ weights[i] ≤ 10⁴
1 ≤ target ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Binary Search Prefix Sum Sliding Window

Similar problems

Shortest Stretch to the Goal Medium Windows With a Small Product Medium Windows With an Exact Alarm Count Medium Longest Run of Ones With k Fixes Medium Stretches With k Odd Numbers Medium

Input

weights=[3, 1, 7, 2, 2], target=6

Expected

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