179. Largest Number

Medium

Problem:

Print the largest number that can be made by combining the items.

Example 1:

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

Example 2:

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

https://leetcode.com/problems/largest-number

What to learn:

str(int(''.join(map(str, nums))))

  1. map() function: The map() function applies a specified function to all the items in an input list. Here, map(str, nums) applies the str function to each number in the nums list, converting each number to its string representation. This is done so that you can concatenate the numbers as strings.

    For example: If nums = [3, 30, 34, 5, 9], then map(str, nums) results in ['3', '30', '34', '5', '9'].

  2. join() method: The str.join() method is a string method that concatenates all the elements in an iterable (like a list), separated by the string it was called on.

    ''.join(['3', '30', '34', '5', '9']) would result in '3303459'.

  3. int() and str() conversion: The reason for the int() and then str() conversion is to handle cases where the result might start with one or multiple '0's due to the arrangement. By converting to an integer and then back to a string, you are effectively stripping those leading zeros.

    For instance, if nums are such that the result is '00...00123', the int('00...00123') will convert it to the integer 123, and then str(123) will give '123'.

    This is to ensure the result doesn't return as '00...00123' but rather as '123'.

Solution:

Starting from the beginning, compare digit by digit and sort in order of size. Since the leading digit of 9 is larger than that of 30, 9 should come first.

Do you think "100" > "20"?

In Python, when comparing strings lexicographically, it's character by character based on ASCII values. Let's break down the comparison of the strings "100" and "20".

  1. The first characters of both strings are compared: '1' vs '2'. Using ASCII values, '1' (49) is less than '2' (50).

  2. Since '1' < '2', the comparison stops here and the result is determined by this character comparison.

class Solution:
    @staticmethod
    def to_swap(n1: int, n2: int) -> bool:
        return str(n1) + str(n2) < str(n2) + str(n1)

    def largestNumber(self, nums: List[int]) -> str:
        i = 1
        while i < len(nums):
            j = i
            while j > 0 and self.to_swap(nums[j-1], nums[j]):
                nums[j], nums[j-1] = nums[j-1], nums[j]
                j -= 1
            i += 1
        return str(int(''.join(map(str, nums))))

Last updated