Largest Number

Arrangement/Sorting

Problem

Given a list of non-negative integers nums, arrange them such that they form the largest number.

Note: The result may be very large, so you need to return a string instead of an integer.

For example:

Input: nums = [10,2]
Output: "210"

Input: nums = [3,30,34,5,9]
Output: "9534330"

Input: nums = [1]
Output: "1"

Input: nums = [10]
Output: "10"

Though Process

• The idea here is to use a "comparison based" sorting algorithm

• Given two numbers A and B, we compare two numbers AB (B appended at the end of A) and BA (A appended at the end of B). If AB is larger, then this means in the output, A should come before B, else if AB isn't larger, then B should come before A.

  • Example: let A and B be 542 and 60. To compare A and B, we compare 54260 and 60542. Since 60542 is greater than 54260, we put B first.

Solution

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if str(nums[j])+ str(nums[i]) > str(nums[i]) + str(nums[j]):
                    nums[j], nums[i] = nums[i], nums[j]
        string = [str(i) for i in nums]
        a_string = "".join(string)
        if nums[0]==0:
            return '0'
        return(a_string)

Key Facts

• We are comparing two concatenated elements to each other to see if $AB > BA$ or $BA > AB$

• We are arranging the elements based on comparing their different concatenations

Time Complexity

• Time:$O(n^2)$

• Space: $O(1)$