Largest Number
MedPrompt
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 <= 1000 <= nums[i] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach explores every possible arrangement of the given numbers. It generates all permutations of the input array, concatenates each permutation into a single number (represented as a string), and keeps track of the largest number found. While it is guaranteed to find the correct answer, its performance is prohibitively slow for anything but very small inputs.
Algorithm
- Create a recursive function to generate all permutations of the input
numsarray. - For each permutation, concatenate the numbers to form a single string.
- Keep a global variable to store the lexicographically largest string found so far.
- Compare each new permutation string with the current maximum and update it if the new one is larger.
- After exploring all
N!permutations, the global maximum string is the answer.
Walkthrough
The core idea is to use a backtracking algorithm to generate all N! permutations of the nums array. For each complete permutation, we build a string by joining the numbers. This string is then compared with the largest number string found so far. If the new string is lexicographically greater, we update our answer. This process continues until all permutations have been checked.
import java.util.ArrayList;import java.util.List; class Solution { String largestNumber = "0"; public String largestNumber(int[] nums) { List<Integer> currentPermutation = new ArrayList<>(); boolean[] used = new boolean[nums.length]; generatePermutations(nums, currentPermutation, used); return largestNumber; } private void generatePermutations(int[] nums, List<Integer> currentPermutation, boolean[] used) { if (currentPermutation.size() == nums.length) { StringBuilder sb = new StringBuilder(); for (int num : currentPermutation) { sb.append(num); } String currentNumber = sb.toString(); // Lexicographical comparison of strings if (currentNumber.compareTo(largestNumber) > 0) { largestNumber = currentNumber; } return; } for (int i = 0; i < nums.length; i++) { if (!used[i]) { used[i] = true; currentPermutation.add(nums[i]); generatePermutations(nums, currentPermutation, used); // Backtrack currentPermutation.remove(currentPermutation.size() - 1); used[i] = false; } } }}Complexity
Time
O(N! * N * L)
Space
O(N * L)
Trade-offs
Pros
Conceptually straightforward and easy to understand.
Guaranteed to find the correct solution by checking every possibility.
Cons
Extremely inefficient due to factorial time complexity.
Will result in a 'Time Limit Exceeded' error for the given constraints (N up to 100).
A much more efficient approach is to treat this as a sorting problem with a special comparison rule. Instead of generating all permutations, we can directly sort the numbers into the correct final order. The key insight is to define a custom comparison logic: for any two numbers a and b, a should be placed before b if the concatenated string a + b is lexicographically greater than b + a. By sorting the string representations of the numbers with this rule, we can construct the largest number greedily.
Algorithm
- Convert each integer in the input array
numsinto its string representation and store them in a new array, says_nums. - Implement a custom
Comparatorfor strings. - The comparison logic for two strings
aandbis based on the concatenated results:ashould come beforebifa + bis lexicographically greater thanb + a. - Sort the
s_numsarray using this custom comparator. - After sorting, if the first element is "0", it means all numbers were 0, so the result is simply "0".
- Otherwise, concatenate all the sorted strings to form the final result.
Walkthrough
The problem can be rephrased as finding an ordering of the numbers that results in the largest lexicographical string. This suggests that a greedy approach using a custom sorting rule might work. We define a new comparison relation for two numbers x and y: x is 'larger' than y if string(x) + string(y) is lexicographically greater than string(y) + string(x). This relation is transitive, which is a crucial property for a sorting comparator to work correctly. Sorting the numbers based on this custom rule arranges them in the optimal order to form the largest number.
import java.util.Arrays;import java.util.Comparator; class Solution { public String largestNumber(int[] nums) { // 1. Convert int array to String array String[] s_nums = new String[nums.length]; for (int i = 0; i < nums.length; i++) { s_nums[i] = String.valueOf(nums[i]); } // 2. Define a custom comparator Comparator<String> comp = (a, b) -> { String order1 = a + b; String order2 = b + a; // Sort in descending order based on the custom rule return order2.compareTo(order1); }; // 3. Sort the array with the custom comparator Arrays.sort(s_nums, comp); // 4. Handle the edge case where the input is [0, 0] // If the largest number after sorting is "0", the entire number is 0. if (s_nums[0].equals("0")) { return "0"; } // 5. Build the final string from sorted parts StringBuilder sb = new StringBuilder(); for (String s : s_nums) { sb.append(s); } return sb.toString(); }}Complexity
Time
O(N * log(N) * L)
Space
O(N * L)
Trade-offs
Pros
Highly efficient and optimal solution.
Passes all constraints with a time complexity of O(N log N).
The logic is elegant once the comparison rule is understood.
Cons
The correctness of the greedy choice (the custom comparison) is not immediately obvious and relies on the transitivity property of the defined comparison relation.
Requires extra space to store the string representations of the numbers.
Solutions
Solution
using System ; using System.Globalization ; using System.Collections.Generic ; using System.Linq ; using System.Text ; public class Comparer : IComparer < string > { public int Compare ( string left , string right ) { return Compare ( left , right , 0 , 0 ); } private int Compare ( string left , string right , int lBegin , int rBegin ) { var len = Math . Min ( left . Length - lBegin , right . Length - rBegin ); for ( var i = 0 ; i < len ; ++ i ) { if ( left [ lBegin + i ] != right [ rBegin + i ]) { return left [ lBegin + i ] < right [ rBegin + i ] ? - 1 : 1 ; } } if ( left . Length - lBegin == right . Length - rBegin ) { return 0 ; } if ( left . Length - lBegin > right . Length - rBegin ) { return Compare ( left , right , lBegin + len , rBegin ); } else { return Compare ( left , right , lBegin , rBegin + len ); } } } public class Solution { public string LargestNumber ( int [] nums ) { var sb = new StringBuilder (); var strs = nums . Select ( n => n . ToString ( CultureInfo . InvariantCulture )). OrderByDescending ( s => s , new Comparer ()); var nonZeroOccurred = false ; foreach ( var str in strs ) { if (! nonZeroOccurred && str == "0" ) continue ; sb . Append ( str ); nonZeroOccurred = true ; } return sb . Length == 0 ? "0" : sb . ToString (); } }class Solution {public String largestNumber(int[] nums) { List<String> vs = new ArrayList<>(); for (int v : nums) { vs.add(v + ""); } vs.sort((a, b)->(b + a).compareTo(a + b)); if ("0".equals(vs.get(0))) { return "0"; } return String.join("", vs); }}function largestNumber ( nums ) { nums . sort (( a , b ) => { const [ ab , ba ] = [ String ( a ) + String ( b ), String ( b ) + String ( a )]; return + ba - + ab ; }); return nums [ 0 ] ? nums . join ( '' ) : ' 0 ' ; }class Solution { public: string largestNumber ( vector < int >& nums ) { vector < string > vs ; for ( int v : nums ) vs . push_back ( to_string ( v )); sort ( vs . begin (), vs . end (), []( string & a , string & b ) { return a + b > b + a ; }); if ( vs [ 0 ] == "0" ) return "0" ; string ans ; for ( string v : vs ) ans += v ; return ans ; } };class Solution: def largestNumber(self, nums: List[int]) -> str: nums = [str(v) for v in nums] nums . sort(key=cmp_to_key(lambda a, b: 1 if a + b < b + a else - 1)) return "0" if nums[0] == "0" else "" . join(nums)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.