179. 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] <= 109

Approach 01:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

class Solution {
public:
    std::string largestNumber(std::vector<int>& numbers) {
        std::string result;

        // Sort the numbers based on the custom comparison logic
        std::sort(numbers.begin(), numbers.end(), [](int num1, int num2) {
            return std::to_string(num1) + std::to_string(num2) > std::to_string(num2) + std::to_string(num1);
        });

        // Concatenate sorted numbers into the result string
        for (const int number : numbers) {
            result += std::to_string(number);
        }

        // If the largest number starts with '0', return "0"
        return result[0] == '0' ? "0" : result;
    }
};

class Solution:
    def largestNumber(self, numbers: List[int]) -> str:
        # Sort the numbers based on custom comparison logic
        numbers = sorted(numbers, key=lambda num: str(num) * 10, reverse=True)

        # Concatenate sorted numbers into the result string
        result = ''.join(map(str, numbers))

        # If the largest number starts with '0', return "0"
        return result if result[0] != '0' else "0"

Time Complexity

• Sorting the numbers:

  The most expensive operation is sorting the array of numbers. The custom comparator compares two concatenated strings formed from two numbers. The time complexity of sorting is \(O(n \log n)\), where \(n\) is the number of elements in the input vector. Each comparison involves concatenating two numbers, which can take up to \(O(m)\) time, where \(m\) is the maximum number of digits in the numbers. Hence, the overall time complexity of sorting becomes \(O(n \log n \cdot m)\).

• Concatenating the result:

  After sorting, concatenating all numbers into the final string takes \(O(n \cdot m)\), where \(n\) is the number of elements and \(m\) is the maximum number of digits in the numbers.

• Overall Time Complexity:

  The overall time complexity is \(O(n \log n \cdot m)\).

Space Complexity

• Auxiliary space for sorting:

  The sorting operation requires \(O(n)\) additional space for the custom comparator and for rearranging the elements during the sort.

• Space for the result string:

  The result string will contain the concatenated numbers, which takes \(O(n \cdot m)\) space, where \(n\) is the number of elements and \(m\) is the maximum number of digits in the numbers.

• Overall Space Complexity:

  The overall space complexity is \(O(n \cdot m)\), accounting for both the sorting and result concatenation.