179. Largest Number

Description of the Problem

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

Solution

Tags: Greedy

Explanation

Greediness of the Problem

Greedy-choice Properties

To acheive the largest number, we have to choose the most signficant digits that make the whole number largest. And

to choose the most signficant digits, simply pick the number in nums such that their "concatenation" is the largest.

For example, in [3,30,34,5,9], 9 is the suitable choice because:

9 3 _ > 3 9 _
9 3 0 > 3 0 9
9 3 4 > 3 4 9
9 5 _ > 5 9 _

i.e. If 9 is in position of the most signficant digits, the whole number is the largest.

Thus, before choosing numbers, we can sort the nums by their "concatenation value" in descending order.

Optimal Substructure Properties

After choosing the most signficant digits, the remaining problem is to find most signficant digits for remaining positions of the whole number.

Code (Rust)

impl Solution {
    pub fn largest_number(mut nums: Vec<i32>) -> String {
        nums
        .sort_by(
            |a,b| format!("{}", b)
            .cmp(
                &format!("{}", a)
            )
        );
        
        nums.into_iter()
        .fold( 
            String::from(""),
            |mut acc, x| 
                if acc == "0"  { 
                    x.to_string() 
                } 
                else { 
                    acc.push_str(&x.to_string()); 
                    acc 
                }
        )
    }
}

Complexity (\(n\) is length of the array)

Time complexity:

\( O(n \lg n) \)
- For any Greedy algorithm, \( O(n \lg n + f(n) ) \) is its time complexity where \( f(n) \) is the time to check whether the current choice match the requirement of the problem (Technically, it is to check whether the choice makes an Independent Set, see Wikipedia: Matroid). Since, any concatenation of numbers makes valid number, in this case \( f(n) = O(1) \)

Auxiliary Space:

\( O(n \lg n) \)
- My implementation creates \( O(n \lg n) \) String for numerical comparison in total although they are create temporarily and drop quickly after comparison.

Leetbook