Teaching Kids Programming – Packing Boxes Algorithm using GroupBy

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integers nums, pack consecutive elements of the same value into sublists. Note: If there’s only one occurrence in the list it should still be in its own sublist.

Constraints
0 ≤ n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [4, 4, 1, 6, 6, 6, 1, 1, 1, 1]
Output

1 2 3 4 5 6

[     [4, 4],     [1],     [6, 6, 6],     [1, 1, 1, 1] ]

[
    [4, 4],
    [1],
    [6, 6, 6],
    [1, 1, 1, 1]
]

Example 2
Input
nums = [5, 5, 5, 5, 5, 5, 5, 5]
Output

1 2 3

[     [5, 5, 5, 5, 5, 5, 5, 5] ]

[
    [5, 5, 5, 5, 5, 5, 5, 5]
]

Example 3
Input
nums = [1]
Output

1 2 3

[     [1] ]

[
    [1]
]

Packing Boxes Algorithm (One Pass)

Let’s go through the boxes. If the current box is the same as the previous one, we push it to the current box. Otherwise we append the current box in the result, and then empty the current box.

We have to deal with the first and the last box and also we have to keep tracking the previous box.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def packBoxes(self, nums):
        ans = []
        cur = []
        prev = None
        for i in nums:
            if i == prev:
                cur.append(i)                
            else:
                if cur:
                    ans.append(cur)
                cur = [i]
            prev = i
        if cur:
            ans.append(cur)
        return ans

class Solution:
    def packBoxes(self, nums):
        ans = []
        cur = []
        prev = None
        for i in nums:
            if i == prev:
                cur.append(i)                
            else:
                if cur:
                    ans.append(cur)
                cur = [i]
            prev = i
        if cur:
            ans.append(cur)
        return ans

Time complexity is O(N) and the space complexity is O(N). Slightly concise implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def solve(self, nums):
        ans = []
        cur = []
        prev = None
        for i in nums:
            if i != prev:
                if cur:
                    ans.append(cur)
                cur = []
            cur.append(i)
            prev = i
        if cur:
            ans.append(cur)
        return ans

class Solution:
    def solve(self, nums):
        ans = []
        cur = []
        prev = None
        for i in nums:
            if i != prev:
                if cur:
                    ans.append(cur)
                cur = []
            cur.append(i)
            prev = i
        if cur:
            ans.append(cur)
        return ans

Python’s GroupBy Algorithm

Python’s groupby function from itertools can be used to solve this using one-liner. The groupby takes a list and returns a dictionary with key is the first element in each group, and the value is the iterator for the list of same elements in each group.

1
2
3

class Solution:
    def packBoxes(self, nums):
        return [list(y) for x, y in groupby(nums)]

class Solution:
    def packBoxes(self, nums):
        return [list(y) for x, y in groupby(nums)]

–EOF (The Ultimate Computing & Technology Blog) —