Largest Number

---

Largest Number: 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.

Example 1:

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

---

Example 2:

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

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10^9

---

Try this Problem on your own or check similar problems:

1. Smallest Value of the Rearranged Number

Solution:

Java

public String largestNumber(int[] nums) {
  StringBuilder sb = new StringBuilder();

  nums = Arrays.stream(nums).boxed().sorted((a, b) -> {
      String valA = String.valueOf(a), valB = String.valueOf(b);
      String o1 = valA + valB, o2 = valB + valA;
      return o2.compareTo(o1);
  }).mapToInt(Integer::intValue).toArray();

  if(nums.length == 0 || nums[0] == 0) return "0";
  for(int num: nums) sb.append(num);
  return sb.toString();
}

JavaScript

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function (nums) {
  nums = nums.map(String);
  nums.sort((a, b) => {
    let o1 = a + b;
    let o2 = b + a;
    return o2.localeCompare(o1);
  });

  if (nums.length === 0 || nums[0] === "0") return "0";
  return nums.join("");
};

Python

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums = list(map(str, nums))
        maxlength = max(map(len, nums))
        nums.sort(key=lambda x:x*(maxlength // len(x) + 1), reverse=True)
        return ''.join(nums) if int(nums[0]) != 0 else '0'

C++

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        std::vector<std::string> numsStr(nums.size());
        std::transform(nums.begin(), nums.end(), numsStr.begin(), [](int num) {
            return std::to_string(num);
        });

        std::sort(numsStr.begin(), numsStr.end(), [](const std::string& a, const std::string& b) {
            return (a + b) > (b + a);
        });

        if (numsStr.empty() || numsStr[0] == "0") return "0";
        return std::accumulate(numsStr.begin(), numsStr.end(), std::string());
    }
};

---

Time/Space Complexity:

• Time Complexity: O(nlogn)
• Space Complexity: O(1)

---

Explanation:

We're converting the number to the string in custom comparison function but note that we have constant time/space complexity since the number of digits in a number is bound by the highest number by problem statement 10^9. To achieve the largest number, we sort the array using the lambda expression which compares two integers by concatenating their string representation in both order and then comparing their lexicographic order. This will sort the integers in descending order based on the lexicographic order of their concatenated string representations. If the largest number is still 0 after sorting, we return "0" otherwise we build the string in the decreasing order of elements in sorted array. Time complexity is governed by the sorting operation which is O(nlogn) (where n is the number of elements in the input array).