Largest Number

179.Largest Number

Sorting

Greedy

Problem Statement:

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

Return the resulting number as a string. If the result is all zeros, return "0".

Algorithm:

1. Convert all integers to strings for custom sorting.
2. Sort the strings in a custom order such that for two strings a and b, the concatenation a + b is greater than b + a (in lexicographical order).
3. Build the result string from the sorted order of numbers.
4. If the result starts with "0" (e.g., all elements were 0), return "0".

Complexity:

Time: O(n log n), where n is the number of integers, due to sorting. | Space: O(n), for storing the string representations and result.

Java Implementation:

public class Solution {
    public String largestNumber(int[] nums) {
        // Use a priority queue (heap) with a custom comparator
        Queue heap = new PriorityQueue<>((o1, o2) -> {
            // Compare concatenated strings in reverse order
            BigInteger num1 = new BigInteger(o1 + o2);
            BigInteger num2 = new BigInteger(o2 + o1);
            return num2.compareTo(num1);
        });

        // Add all numbers as strings to the heap
        for (int num : nums)
            heap.add(String.valueOf(num));

        // Build the largest number by concatenating strings in heap order
        StringBuilder result = new StringBuilder();
        while (!heap.isEmpty())
            result.append(heap.poll());

        String answer = result.toString();

        // Handle cases with leading zeros
        if (answer.startsWith("0")) return "0";

        return answer;
    }
}
                

Python Implementation:

from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums):
        # Custom comparator for sorting
        def compare(x, y):
            if x + y > y + x:
                return -1
            elif x + y < y + x:
                return 1
            else:
                return 0

        # Convert numbers to strings and sort using the comparator
        nums = sorted(map(str, nums), key=cmp_to_key(compare))

        # Build the result and handle the "all zeros" case
        result = ''.join(nums)
        return '0' if result[0] == '0' else result
                

C++ Implementation:

class Solution {
public:
    string largestNumber(vector& nums) {
        // Convert numbers to strings
        vector numStrs;
        for (int num : nums)
            numStrs.push_back(to_string(num));

        // Custom comparator for sorting
        auto compare = [](const string& a, const string& b) {
            return a + b > b + a;
        };

        // Sort the strings
        sort(numStrs.begin(), numStrs.end(), compare);

        // Build the result
        string result;
        for (const string& num : numStrs)
            result += num;

        // Handle the "all zeros" case
        return result[0] == '0' ? "0" : result;
    }
};