See all coding puzzles and patterns here.

Problem Definition

Given an array of numbers, rearrange the array so that if the numbers were joined according to their position, they form the largest possible number.

Examples

Some test cases to verify our solution.

assert largest_num([2, 900, 51]) == [900, 51, 2]
assert largest_num([4, 49, 74, 8, 55]) == [8, 74, 55, 49, 4]

Solution

We work backwards from the end solution. For every position in the result array, we have to compare the combination of the two elements starting at that position to see which is bigger.

The invariant in this case is that for every $i$ position in the result array res, res[i]res[i+1] > res[i+1]res[i]. And in fact, this is true for all $j > i$.

In effect, this is a sorting problem where the comparison is res[i]res[i+1] > res[i+1]res[i]. Because we are implementing a merge-sort algorithm here, it's a divide & conquer solution. 

def merge(arr1, arr2):
    res = []
    arr1_idx = 0
    arr2_idx = 0
    arr1_len = len(arr1)
    arr2_len = len(arr2)
    while arr1_idx < arr1_len and arr2_idx < arr2_len:
        arr1_item = str(arr1[arr1_idx])
        arr2_item = str(arr2[arr2_idx])
        if int("".join((arr1_item, arr2_item))) < int("".join((arr2_item, arr1_item))):
            res.append(arr2[arr2_idx])
            arr2_idx += 1
        else:
            res.append(arr1[arr1_idx])
            arr1_idx += 1
    while arr1_idx < arr1_len:
        res.append(arr1[arr1_idx])
        arr1_idx += 1
    while arr2_idx < arr2_len:
        res.append(arr2[arr2_idx])
        arr2_idx += 1
    return res

def largest_num(arr):
    if len(arr) < 2:
        return arr
    mid = len(arr) // 2
    return merge(largest_num(arr[:mid]), largest_num(arr[mid:]))

Complexity

Let $n = $ len(arr).

Runtime complexity should be $O(n \cdot log(n))$.

Space complexity should be $O(n)$ since we are keeping another copy of the whole array during merges. We can cut down the space complexity by doing a merge in place, but that is significantly more complicated.