14.Largest Number

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

Example 1:
Input: nums = [10,2]
Output: "210"

Example 2:
Input: nums = [3,30,34,5,9]
Output: "9534330"

Example 3:
Input: nums = [1]
Output: "1"

Example 4:
Input: nums = [10]
Output: "10"

Solution I:

Approach: Sorting with a compare.

class Solution
{
public:
    string largestNumber(vector<int> &nums)
    {

        for (int i = 0; i < nums.size(); i++)
        {
            for (int j = i + 1; j < nums.size(); j++)
            {
                string a = to_string(nums[i]) + to_string(nums[j]);
                string b = to_string(nums[j]) + to_string(nums[i]);

                if (b > a)
                {
                    swap(nums[i], nums[j]);
                }
            }
        }

        if (nums[0] == 0)
        {
            return "0";
        }
        
        string res = "";
        for (int i = 0; i < nums.size(); i++)
        {
            res = res + to_string(nums[i]);
        }

        return res;
    }
};

Time Complexity: O(N^2)

Solution II:

class Solution
{
public:
    bool static compare(string a, string b)
    {
        string s1 = a + b;
        string s2 = b + a;
        if (s1 > s2)
        {
            return 1;
        }

        return 0;
    }

    string largestNumber(vector<int> &nums)
    {

        vector<string> v;
        for (int i = 0; i < nums.size(); i++)
        {
            string a = to_string(nums[i]);
            v.push_back(a);
        }

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

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

        string res = "";
        for (int i = 0; i < v.size(); i++)
        {
            cout << v[i] << " ";
            res = res + v[i];
        }

        return res;
    }
};

Time Complexity: O(N log n), Space Complexity: O(N)