• Posts

Problem 179 Largest Number

Problem Statement

Link - Problem 179

Question

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

Solution

class Solution {
public:
    static bool compare(string sa, string sb) {
        if((sa + sb )> (sb + sa)){
            return true;
        }
        return false;
    }

    string largestNumber(vector<int>& nums) {
        vector<string>n;
        for(auto it:nums)
            n.push_back(to_string(it));

        sort(n.begin(), n.end(), compare);

        if (n[0] == "0") {
            return n[0];
        }

        string ans = "";
        for (auto num : n) {
            ans += num;
        }

        return ans;
    }
};

Complexity Analysis

| Algorithm      | Time Complexity | Space Complexity |
| -------------- | --------------- | ---------------- |
| Custom Sorting | O(n log n)      | O(n)             |

Explanation

Intial Thoughts

First, understand the goal of forming the largest number from a list of non-negative integers. Think about comparing numbers in a way that considers their potential as part of a larger number. Consider that numbers should be compared based on their contribution to the overall number, not just their individual size. Think about the role of sorting and how it can be customized to achieve the desired outcome. Consider how to handle the case when all numbers are 0.

Intuitive Analysis

To intuitively solve this problem, think of it as arranging words in a dictionary where each word represents a number. Compare these ‘words’ based on which one comes first when concatenated with another. Consider the impact of leading digits and how they affect the overall size of the number. Imagine using a custom sorting method that takes into account the concatenation of numbers. Think about how to identify and handle edge cases efficiently, such as when the largest number is 0. Consider the importance of string manipulation in solving the problem.

1. Intuition

• The problem requires arranging non-negative integers to form the largest possible number, which can be achieved by sorting the numbers based on a custom comparison function
• The comparison function should compare two numbers a and b by concatenating them in both orders (ab and ba) and choosing the order that produces the larger number
• This approach ensures that the resulting number is the largest possible, as it considers all possible orderings of the input numbers
• The key insight is that the comparison function should be based on the concatenated numbers, rather than their individual values
• This solution works because it uses a greedy approach, where the largest possible number is constructed by iteratively choosing the largest possible digit or number
• The algorithmic choice of using a custom comparison function with sorting allows for an efficient solution with a time complexity of O(n log n)
• The use of a string representation for the numbers allows for easy concatenation and comparison, and avoids potential issues with integer overflow

2. Implementation

• The compare function is defined as static bool compare(string sa, string sb), which takes two strings sa and sb as input and returns true if sa + sb is greater than sb + sa
• The largestNumber function converts the input integers to strings using to_string(it) and stores them in a vector n
• The sort function is used with the custom comparison function compare to sort the vector n in descending order
• The function checks if the first element of the sorted vector n is 0, in which case it returns 0 as the result
• The function constructs the largest possible number by concatenating the sorted numbers using ans += num
• The compare function is used as a lambda function in the sort function to compare the numbers based on their concatenated values
• The use of vector<string> allows for easy manipulation and sorting of the input numbers

Complexity Analysis

Time Complexity:

• The time complexity of the given algorithm is O(n log n) due to the sort(n.begin(), n.end(), compare) operation. This is because the sort function in C++ uses a variation of the Introsort algorithm, which has a worst-case time complexity of O(n log n).
• The comparison function compare has a constant time complexity of O(1) since it only involves string concatenation and comparison. However, this is dominated by the O(n log n) complexity of the sorting algorithm.
• The overall time complexity is O(n log n) since the sorting operation is the most computationally expensive part of the algorithm. This is justified by the fact that the number of comparisons and swaps performed by the sorting algorithm grows logarithmically with the size of the input.

Space Complexity:

• The space complexity of the algorithm is O(n) because it creates a new vector n to store the string representations of the input numbers. The size of this vector is proportional to the size of the input array nums.
• The sorting algorithm used by sort(n.begin(), n.end(), compare) may also use additional memory for temporary storage, but this is typically a constant factor that does not affect the overall space complexity.
• The output string ans also uses O(n) space since it is constructed by concatenating all the strings in the sorted vector n. However, this is not included in the space complexity analysis since it is part of the output, not the auxiliary space used by the algorithm.

Footnote

This question is rated as Medium difficulty.

Similar Questions: