Problem statement

https://binarysearch.com/problems/Sorting-Mail/

Solution

We can use multisourse bfs here: put all starting values to the list first. Then on each step if we have next element, put it in the end of queue.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, mailboxes):
        locs = [(i, 0) for i in range(len(mailboxes))]
        ans = []
        for i, j in locs:
            if mailboxes[i][j] != "junk":
                ans += [mailboxes[i][j]]
            if j + 1 < len(mailboxes[i]):
                locs += [(i, j + 1)]
        return ans