Leetcode Daily Question 18/09/2024 - 179. Largest Number

Problem Description:

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it. Since the result may be very large, so you need to return a string instead of an integer.

from typing import List
from functools import cmp_to_key
class Solution:
  @staticmethod
  def compareConcatenations(a: str, b: str) -> int:
    if a + b > b + a:
      return -1
    elif b + a > a + b:
      return 1
    else:
      return 0
  
  def largestNumber(self, nums: List[int]) -> str:
    nums_strings = [str(num) for num in nums]
    nums_strings.sort(key=cmp_to_key(self.compareConcatenations))

    if nums_strings[0] == "0":
      return "0"

    return "".join(nums_strings)

Explanation:

This is a maths question. The idea is to use transitivity and associativity to your advantage.

Consider 3 num strings, a, b, c, and let * be the concatenation operator. So for example, if a = "50", b = "323". Then a * b = "50323".

Associativity means (a * b) * c = a * (b * c)

Transitivity means if a * b > b * a and b * c > c * a, then a * c > c * a.

Transitivity is harder to prove. But an easy way to convince yourself is to try concatenating different strings and observe how the concatenation is performed as strings and as integers.
(How do you concatenate integers like you would with strings?)

Once that is known, we can say if a*b > b*a and b*c > c*a, then a*c*b < b*c*a. This is the key to solving this question.

We use this property in conjunction with cmp_to_key in functools to sort the num strings.

First let's define the comparison function.

def compareConcatenations(a: str, b: str):
  if a + b < b + a:
    return -1
  elif b + a < a + b:
    return 1
  else:
    return 0

This comparison method tells us which num string contributes more in constructing the largest number.

A small thing to note. If we have an array of all "0"s, then we need to return "0". We can catch this case by checking if the first element of num_strings.

So the main function can be defined as

def largestNumber(nums):
  nums_strings = [str(num) for num in nums]
  nums_strings.sort(key = cmp_to_key(compareConcatenations))
  
  if nums_strings[0] == "0":
    return "0"
  
  return "".join(nums_strings)

The time complexity is O(n) where n is the length of nums. This is because we need to pass nums to create the nums_strings array and create the sorting order.

The space complexity is O(n) as well. This is because we need to store the nums as strings.

The full solution can be found near the top of the page.