Amazon Online Assessment (OA)  Minimum Total Container Size
You want to move N
items in k days (N >= k)
. You have to move at least one item per day.
The items are listed in array P
, where P[i]
is size of item i
.
You can move item i
only if all items from 0
to [i  1]
are already moved.
Every day you need a container to pack the item and move it. The container size needed for day i
is the maximum item size moved on that day.
Given k days
and array P
as the item sizes, find out the minimum total container size required to move all the items.
Examples
Example 1:
Input: P = [10, 2, 20, 5, 15, 10, 1]
, d = 3
Output: 31
Explanation:
 day 1 
[10, 2, 20, 5, 15]
.ContainerSize = 20
 day 2 
[10]
.ContainerSize = 10
 day 3 
[1]
.ContainerSize = 1
Total = 20 + 10 + 1 = 31
Example 2:
Input: P = [10, 2, 20, 5, 15, 10, 1]
, d = 5
Output: 43
Explanation:
 day 1 
move [10]
.ContainerSize = 10
 day 2 
move [2]
.ContainerSize = 2
 day 3 
move [20, 5, 15]
.ContainerSize = 20
 day 4 
move [10]
.ContainerSize = 10
 day 5 
move [1]
.ContainerSize = 1
Total = 10 + 2 + 20 + 10 + 1 = 43
Example 3:
Input: P = [5, 4, 2, 4, 3, 4, 5, 4]
, d = 4
Output: 16
Explanation:
 day 1 
[5, 4]
,containerSize = 5
 day 2 
[2]
,containerSize = 2
 day 3 
[4, 3]
,containerSize = 4
 day 4 
[4, 5, 4]
,containerSize = 5
 day 5 
move [1]
.ContainerSize = 1
Total = 5 + 2 + 4 + 5 = 16
Example 4:
Input: P = [22, 12, 1, 14, 17]
, d = 2
Output: 39
Explanation:
 day 1 
[22, 12]
,containerSize = 22
 day 2 
[1, 14, 17]
,containerSize = 17
Total = 22 + 17 = 39
Try it yourself
Solution
Assume 0based indexing and leftinclusive, rightexclusive ranges.
Imagine we have moved i
items in total after d
days,
and the total container size we have used is s(d, i)
.
Notice that for fixed i
and d
,
having a lower s
is always better than a higher s
(since the available choices for later days are the same).
For d > 0
,
we must have moved some number of items during the last day,
let's say k
items.
Then s(d, i)
is the sum of s(d  1, i  k)
(the total container size when we moved i  k
items after d  1
days)
and the max of container sizes from item i  k
to item i
(container size we used during the last day).
So the minimum possible s(d, i)
is the minimum of all s(d  1, i  k) + max(sizes[i  k..i])
for all k
in 1..i + 1
(at least 1 every day, and at most all items).
For d = 0
,
we haven't moved anything yet,
so s(d=0, i=0) = 0
(total container size 0),
and s(d=0, i)
is impossible for i != 0
(moved non0 items in 0 days)
which we will represent with infinity / int max
(since we want minimum).
So we have an recurrence relation:
s(d=0, i=0) = 0
s(d=0, i!=0) = inf
s(d!=0, i) = min(s(d  1, i  k) + max(sizes[i  k..i]) for k = 1..i + 1)
We can write this out as a (memoized) recursive function (topdown dynamic programming):
1  + 
 
2  + 
 
1  3 
 
2  4  
3  5 
 
4   
 
6  + 
 
5   
 
7  + 
 
8  + 
 
9  + 
 
10  +  
11  + 
 
12  + 
 
13  + 
 
14  + 
 
15  + 
 
16  + 
 
17  + 
 
18  + 
 
19  + 
 
20  +  
21  + 
 
22  +  
6  23 
 
7  24 
 
8  25 
 
9  26 
 
10  27 

The above solution will indeed give the correct answer, but we can do better.
Notice that the value of s
on day d
only depends on the values of s
on day d  1
.
This means that if we calculate all the s
of a day before moving onto the next day
(bottomup dynamic programming),
we can discard the data from 2 or more days ago and save space.
This reduces the auxiliary space from O(d * P)
to O(P)
,
where d
is the value of input d
and P
is the size of input P
(see pseudopolynomial).
Another thing to notice is that for each k
,
the naive approach of calculating max(sizes[i  k..i])
involves a loop —
but we are already looping through k
one by one!
So rather than repeatedly searching for the max of size[i  k..i]
for each k
,
we keep the current max outsize of the loop,
so when we increment k
,
the new max size[i  k..i]
is the max of old max and size[i  k]
.
This reduces the runtime from O(d * P^3)
to O(d * P^2)
.