# Pen Box

## # Solution

Brute-force solution would take : 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]*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