Largest Number Leetcode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple ByteDance eBay Facebook Google Microsoft Oracle Salesforce Samsung Tesla Uber Visa VMware
Goldmann Sachs Greedy Sorting StringViews 7235

Problem Statement

The Largest Number LeetCode Solution – “Largest Number” states that given a list of non-negative integers nums, we need to arrange the numbers in such a way 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:

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

Explanation:

  • All possible strings are [“102″,”210”].
  • We can see that the second string “210” forms the largest number.
Input:  nums = [3,30,34,5,9]
Output: "9534330"

Explanation:

  • We can form 5! = 120 different types of numbers.
  • Among them, the largest number is “9534330”.

Approach

Idea:

  1. The main idea to solve this problem is to use Sortings, with the lambda function.
  2. Here, the key idea is to understand among two numbers n1 and n2, which would come first?
  3. Consider two possibilities for these two numbers:
    1. n1 comes before n2, so the resulting string is n1 + n2.
    2. n2 comes before n1, so the resulting string is n2 + n1.
  4. We need to compare the string representation of (n1+n2) and (n2+n1) and check which string representation will give the largest possible number.
  5. Let’s sort the input array and we’ll use the lambda function to compare two numbers. Compare string representation of n1 + n2 with n2 + n1.
  6. If the string representation of n1 + n2 is greater than n2 + n1 return true, otherwise return false.
  7. Append all the string representations of numbers starting from the beginning.

Code

Largest Number Leetcode C++ Solution:

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end(),[&](const int& a,const int& b){
            string s1 = to_string(a) + to_string(b);
            string s2 = to_string(b) + to_string(a);
            return s1 > s2;
        });
        string ans = "";
        for(auto& c:nums){
            ans += to_string(c);
        }
        if(ans[0]=='0'){
            return "0";
        }
        return ans;
    }
};

Largest Number Leetcode Java Solution:

class Solution {
    public String largestNumber(int[] nums) {
        String[] str = new String[nums.length];
        for(int i=0;i<nums.length;i++){
            str[i] = String.valueOf(nums[i]);
        }
        Arrays.sort( str, (s1, s2) -> (s2+s1).compareTo(s1+s2) );
        if(str[0].charAt(0)=='0'){
            return "0";
        }
        StringBuilder ans = new StringBuilder();
        for(String s:str){
            ans.append(s);
        }
        return ans.toString();
    }
}

Complexity Analysis for Largest Number Leetcode Solution

Time Complexity

The time complexity of the above code is O(KNlogN) where N is the size of the input array and K is the maximum length of the input string.

Sorting takes O(NlogN) time and each comparison takes O(K) time. Hence, the time complexity is O(KNlogN).

Space Complexity

The space complexity of the above code is O(1). Here we aren’t considering the space used to store the answer.

Translate »