Along one side of a road there is a sequence of vacant plots of land. Each plot has a different area (non-zero). So, the areas form a sequence A[1], A[2], … A[N].

You want to buy K acres of land to build a house. You want to find a segment of continguous plots (i.e., a subsection in the sequence) of minimum length whose sum is exactly K.

**Solution**

*First attempt*

Compute prefix sums. For each (i,j) check if A[j] - A[i] = K. Among all such sections, choose the one where j - i is minimized.

This takes time N^{2}. Can we do better?

The prefix sums form a sequence of values in ascending value:

P[1] < P[2] < … < P[N]

For each i, we want to find a j such that P[j] - P[i] = K. Since the prefix sums are sorted in ascending order, we can find the j for each i using binary search, instead of exhaustively scanning P[i+1], … P[N].

This improves the complexity to N log N.

Can we do it in time proportional to N?

For each i, compute if there is a segment starting at i that adds up to exactly K.

Start at A[1]. Add A[2], A[3], …

- If we reach A[j] such that sum till A[j] is exactly K, note this down.
- If the sum till A[j-1] is less than K and the sum till A[j] exceeds K, there is no solution starting from A[1].
- At this point, we subtract A[1] from the sum. We automatically have the sum starting from A[2] upto A[j].
- The sum from A[2] upto A[j-1] must be less than K (since the sum from A[1] to A[j-1] was less than K). If there is already a solution for A[2], it must be A[2] to A[j].
- If A[2] + … + A[j] is exactly K, note this down and subtract A[2] to get the sum from A[3].
- Otherwise, we continue to add A[j+1] etc until we reach a value where the sum crosses K and repeat the argument above.

Essentially we maintain a sliding window within which we maintain the sum. At each stage:

- if the sum of the window is less than K, expand the window to the right.
- if the sum of the window is greater to K, contract the window from the left.
- if the sum of the window is equal to K, note the left and right end points and contract the window from the left.

*Example*

K = 8 1 3 2 1 4 1 3 2 1 1 2

Expand window right till sum crosses K

1 3 2 1 4 1 3 2 1 1 2 |--->4--->6--->7-->11

Exceeds K, contract window from left

1 3 2 1 4 1 3 2 1 1 2 |------------>10

Exceeds K, contract window from left

1 3 2 1 4 1 3 2 1 1 2 |------->7

Less than K, expand window to right

1 3 2 1 4 1 3 2 1 1 2 |------------->8

Equals K, note left and right end points, contract from left

1 3 2 1 4 1 3 2 1 1 2 |-------->6

Less than K, expand window to right

1 3 2 1 4 1 3 2 1 1 2 |------------->9

Exceeds K, contract window from left

1 3 2 1 4 1 3 2 1 1 2 |-------->8

Equals K, note left and right end points, contract from left

1 3 2 1 4 1 3 2 1 1 2 |--->4

Less than K, expand window to right

1 3 2 1 4 1 3 2 1 1 2 |--->4--->6--->7--->8

Equals K, note left and right end points, contract from left

1 3 2 1 4 1 3 2 1 1 2 |------------->7

Less than K, expand window to right

1 3 2 1 4 1 3 2 1 1 2 |------------->7--->9

Exceeds K, contract window from left

1 3 2 1 4 1 3 2 1 1 2 |------------->7

Less than K, cannot expand window to right, stop

©IARCS 2012–2016

PÄ›stujeme web | visit: Skluzavky