# Pen Box

ArrayTwo PointersDP

## # Solution

Brute-force solution would take $O(n^2)$: calculate sum of all subarrays, cut at a point and take the min.

### # DP & Two Pointers

Divide the boxes array into two parts, find_min_len in each part and return minimum left_min[i]+right_min[i+1].

Note:

• find_min_len only calculates the min lengths expanding from left for left_min, but can calculate right_min after boxes is reversed and result is reversed.
• csum means current sum.
def minimumBoxes(self, boxes, target):
"""
@param boxes: number of pens for each box
@param target: the target number
@return: the minimum boxes
"""
n = len(boxes)
if n == 0:
return -1

left_min = self.find_min_len(boxes, target, n)
boxes.reverse()
right_min = self.find_min_len(boxes, target, n)
right_min.reverse()

res = sys.maxsize

for i in range(n-1):
res = min(res, left_min[i]+right_min[i+1])
if res == sys.maxsize:
return -1
return res

def find_min_len(self, boxes, target, n):
"""
returns an array in which each element records min length of subarray whose sum equals target
"""
left_min = [sys.maxsize for _ in range(n)]
# sum in current sliding window
csum = 0
left = 0

# left == right == 0
if csum == target:
left_min[0] = 1
for right in range(n):
csum += boxes[right]
# find window
while csum > target:
csum -= boxes[left]
left += 1
while left < right and boxes[left] == 0:
left += 1
# take last length if < target
if csum < target:
left_min[right] = left_min[right-1]
# take shorter length if == target
elif csum == target:
left_min[right] = min(left_min[right-1], right-left+1)

return left_min

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52