LeetCode - Largest Number

Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/largest-number

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

Explanation

Sorting using a custom comparator

To construct the largest number, we need to place the largest digits at the most significant bit.

We need to convert each integer to a string and then sort the array of strings.

Note We cannot perform sorting on the number of integers. For e.g., if we have numbers [9, 30, 15] and sort them in descending order it will result in [30, 15, 9] and the number constructed is 30159. The largest number is 93015.

Let's check the algorithm:

// largestNumber function
- if nums.size() == 0
  - return ""

- initialize vector<string> numbers
  i = 0

- loop for i < nums.size(); i++
  // convert integer to string and push in the array
  - numbers.push_back(std::to_string(nums[i]))

- sort(numbers.begin(), numbers.end(), cmp)

- set ans = ""

- loop for i = 0; i < numbers.size(); i++
  - ans = ans + numbers[i]

- return ans[0] == "0" ? "0" : ans

// cmp function
cmp(string a, string b)
- return a + b > b + a

C++ solution

class Solution {
static bool cmp(string a, string b){
    return a + b > b + a;
};

public:
    string largestNumber(vector<int>& nums) {
        if(nums.size() == 0){
            return "";
        }

        vector<string> numbers;
        int i = 0;

        for(; i < nums.size(); i++){
            numbers.push_back(std::to_string(nums[i]));
        }

        sort(numbers.begin(), numbers.end(), cmp);
        string ans = "";

        for(i = 0; i < numbers.size(); i++){
            ans += numbers[i];
        }

        return ans[0] == "0" ? "0" : ans;
    }
};

Golang solution

func largestNumber(nums []int) string {
    if len(nums) == 0 {
        return ""
    }

    numbers := make([]string, len(nums))
    i := 0

    for i < len(nums) {
        numbers = append(numbers, strconv.Itoa(nums[i]))
        i++
    }

    sort.Slice(numbers, func(a, b int) bool { return numbers[a] + numbers[b] > numbers[b] + numbers[a] })

    ans := ""

    for _, v := range numbers { ans += v }

    if ans[0] == '0' {
        return "0"
    }

    return ans
}

Javascript solution

var largestNumber = function(nums) {
    if( nums.length == 0 ) {
        return "";
    }

    let numbers = [];

    for( let i = 0; i < nums.length; i++ ) {
        numbers.push(nums[i].toString());
    }

    numbers.sort(function (x, y) {
        return x + y > y + x ? -1 : 1;
    });

    let ans = "";

    for( i = 0; i < numbers.length; i++ ){
        ans += numbers[i];
    }

    return ans[0] == "0" ? "0" : ans;
};

Let's dry-run our algorithm to see how the solution works.

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

Step 1: nums.size() == 0
        5 == 0
        false

Step 2: vector<string> numbers;
        int i = 0;

Step 3: loop i < nums.size()
        0 < 5
        true

        numbers.push_back(std::to_string(nums[i]))

        so the loop iterates from 0 to 4, and we append the string numbers

        numbers = ["3", "30", "34", "5", "9"]

Step 4: sort(numbers.begin(), numbers.end(), cmp)

// in cmp function
Step 5: return a + b > b + a

        so for first two element we check
        "3" + "30" > "30" + "3"
        "330" > "303"
        true

        "3" + "34" > "34" + "3"
        "334" > "343"
        false

        "5" + "34" > "34" + "5"
        "534" > "345"
        true

        "9" + "5" > "5" + "9"
        "95" > "59"
        true

        The final array is ["9", "5", "34", "3", "30"].

Step 6: string ans = ""

Step 7: loop for(i = 0; i < numbers.size(); i++)
            - ans += numbers[i]
        ans is set to "9534330"

Step 8: ans[0] == "0"
        "9" == "0"
        false
        return ans

So we return the result as "9534330".

Blog