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).
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 (); } }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.