DEV Community

loading...

The largest number problem

jpantunes profile image JP Antunes ・1 min read

Today I'm sharing a simple solution to the largest number problem on Leetcode.

The problem statement asks us to sort a given list of positive integers such that it forms the largest possible number, returning it as a string.
In the examples provided, we see that with the input [10,2] the expected output is "210" and with [3,30,34,5,9] it's "9534330".

At first glance, I thought that the default dictionary sort() we get for "free" in JS and the Array reverse() method would do the trick because of the implicit type coercion that often surprises people. See, if we have an array nums = [10, 2], then nums.sort() will output [ 10, 2] because Javascript compares "10" to "2" as strings, not as numbers. This means that nums.sort().reverse().join('') outputs "210" which is in fact the droid largest number we are looking for.

There's a catch though, the largest number possible from an array of integers isn't the same as the array lexicographically sorted in descending order. For instance, nums = [3, 10, 2, 1, 100] once sorted, reversed and formatted into a string returns "32100101" but the highest possible number is "32110100"!

Here's what I came up with:

var largestNumber = function(nums) {
  if (Math.max(...nums) == 0) return '0';   

  const res = nums.map(String).sort((a, b) => {
    if (a.length !== b.length) {
      const aStr = a + b;
      const bStr = b + a;
      return bStr - aStr;
    }
    return b - a;
  }).join('');

  return res;    
};

//Runtime: 60 ms, faster than 91.89%
//Memory Usage: 35.3 MB, less than 100.00%

Discussion

pic
Editor guide