Largest Number
Problem Description:
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.
Examples:
Input: nums = [10,2]
Output: "210"
Explanation: Arrange numbers as "2" + "10" to form the largest number.
Input: nums = [3,30,34,5,9]
Output: "9534330"
Explanation: Arrange numbers as "9" + "5" + "34" + "3" + "30" to form the largest number.
Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 10⁹
Brute Force Approach
Okay, so here's the thought process:
What comes to mind after reading the problem statement?
We are given an array of numbers, and we need to return the largest number by combining all these numbers one after the other in the form of a string.
One basic approach is to check all possibilities or all possible permutations of the numbers, store them, and finally return the largest one.
To achieve this, we can simply generate all the permutations of the numbers, concatenate them into strings, and at the end, return the largest permutation.
Let's understand with an example:
- Input Array: nums = [121, 12, 120]
- Generate Permutations:
Possible permutations: - [121, 12, 120] → "12112120"
- [121, 120, 12] → "12112012"
- [12, 121, 120] → "12121120"
- [12, 120, 121] → "12120121"
- [120, 121, 12] → "12012112"
- [120, 12, 121] → "12012121"
- Compare Strings:
- Compare all concatenated strings lexicographically:
- "12112120"
- "12112012"
- "12121120" → Largest so far
- "12120121"
- "12012112"
- "12012121"
- Largest String: "12121120"
Output: 12121120
The largest number formed by combining the numbers is "12121120".
How to code it up:
Here are the concise steps to code the solution:
- Convert the given integers in the array to strings to facilitate concatenation.
- Sort the input array in ascending order to prepare for generating all permutations.
- Use next_permutation to iterate through all possible arrangements of the numbers.
- For each permutation, concatenate the numbers into a single string.
- Compare each concatenated string with the current largest string and update if the new string is lexicographically larger.
- After all permutations are checked, return the largest string found.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
string largestNumber(vector<int>& nums) {
vector<string> permutations;
vector<int> temp = nums;
// Generate all permutations
sort(temp.begin(), temp.end());
do {
// Concatenate the current permutation into a string
string current = "";
for (int num : temp) {
current += to_string(num);
}
// Store the concatenated result
permutations.push_back(current);
} while (next_permutation(temp.begin(), temp.end()));
// Find the largest string
string largest = "";
for (const string& str : permutations) {
if (str > largest) {
largest = str;
}
}
return largest;
}
};2. Java Try on Compiler
import java.util.*;
class Solution {
public String largestNumber(int[] nums) {
List<String> permutations = new ArrayList<>();
// Convert integers to strings
String[] strNums = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strNums[i] = String.valueOf(nums[i]);
}
// Generate all permutations
Arrays.sort(strNums);
do {
// Concatenate the current permutation into a string
StringBuilder current = new StringBuilder();
for (String num : strNums) {
current.append(num);
}
permutations.add(current.toString());
} while (nextPermutation(strNums));
// Find the largest string
String largest = "";
for (String str : permutations) {
if (str.compareTo(largest) > 0) {
largest = str;
}
}
return largest;
}
// Helper function to generate the next permutation
private boolean nextPermutation(String[] nums) {
int i = nums.length - 1;
while (i > 0 && nums[i - 1].compareTo(nums[i]) >= 0) {
i--;
}
if (i <= 0) return false;
int j = nums.length - 1;
while (nums[j].compareTo(nums[i - 1]) <= 0) {
j--;
}
// Swap
String temp = nums[i - 1];
nums[i - 1] = nums[j];
nums[j] = temp;
// Reverse the suffix
int k = nums.length - 1;
while (i < k) {
temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;
i++;
k--;
}
return true;
}
}
3. Python Try on Compiler
from itertools import permutations
class Solution:
def largestNumber(self, nums):
# Convert integers to strings
str_nums = [str(num) for num in nums]
# Generate all permutations
all_permutations = permutations(str_nums)
# Find the largest string
largest = ""
for perm in all_permutations:
current = ''.join(perm)
if current > largest:
largest = current
return largest
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @return {string}
*/
var largestNumber = function(nums) {
// Convert integers to strings
let strNums = nums.map(String);
// Generate all permutations using a helper function
let permutations = permute(strNums);
// Find the largest string
let largest = '';
for (let perm of permutations) {
let current = perm.join('');
if (current > largest) {
largest = current;
}
}
return largest;
};
// Helper function to generate all permutations
function permute(nums) {
let results = [];
function backtrack(start) {
if (start === nums.length) {
results.push([...nums]);
return;
}
for (let i = start; i < nums.length; i++) {
[nums[start], nums[i]] = [nums[i], nums[start]]; // Swap
backtrack(start + 1);
[nums[start], nums[i]] = [nums[i], nums[start]]; // Backtrack
}
}
backtrack(0);
return results;
}
Time Complexity: O(n! * n)
- Generate Permutations:
The number of permutations of an array of n elements is n!.
Generating each permutation takes O(n) time (for rearranging the elements and generating the new arrangement).
So, the total time to generate all permutations is O(n! * n). - Concatenation and Comparison:
For each permutation, we concatenate the numbers into a string. The concatenation operation takes O(n) time (for concatenating n numbers).
We also compare the concatenated string with the largest string found so far, which also takes O(n) time for each string.
Therefore, the overall time complexity is: O(n! * n), where:
- n! is the number of permutations generated (since there are n! ways to arrange n elements).
- n is the time taken to concatenate each permutation (since each string is of length n).
Space Complexity: O(n! * n)
Auxiliary Space Complexity: O(n! * n)
Explanation: In the brute-force approach, you generate n! permutations of the array. For each permutation, you create a string of length n to store the result. The space for holding each permutation is O(n), and there are n! permutations generated. So, the auxiliary space for storing permutations is O(n! * n). You only need a few additional variables, this doesn't contribute significantly to the auxiliary space, so the total auxiliary space is dominated by the storage of permutations. A string to store the largest number (largest), which requires O(n) space. So, the auxiliary space complexity is O(n! * n).
Total Space Complexity: O(n! * n)
Explanation: The input array nums has n elements, which is O(n) space.
So, the total space complexity is O(n! * n) (from the permutations) + O(n) (for input array) = O(n! * n)
Therefore, the total space used by the algorithm is O(n! * n).
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n! * n), where n is the length of the nums array and n! represents the number of permutations. Each permutation requires n operations for concatenation.
For the brute force approach, generating all permutations of the array results in O(n! * n) operations. With n up to 100, n! grows extremely fast, making this solution infeasible for large values of n due to factorial complexity.
However, assuming smaller inputs (for example, n ≤ 10), this approach could be executed comfortably within typical time limits.
For n ≤ 10, the total number of operations would be approximately 10! * 10 (3,628,800 operations), which can be executed in a reasonable amount of time (typically within 1–2 seconds per test case).
For n = 100, the total number of operations would be approximately 100! * 100.100! grows exponentially and is approximately 9.33 × 10¹⁵⁴ (a 155-digit number). Even if we multiply it by 100, the result is still an astronomically large number of operations.
In most competitive programming environments, problems can handle up to 10⁶ operations per test case. But for n = 100, the O(n! * n) complexity becomes impractical due to the rapid growth of factorial numbers.
Thus, while the solution works efficiently for smaller inputs (with n ≤ 10), it would not perform well for the full constraint of n = 100 due to the extremely high computational cost of generating n! permutations.
Can we optimize it?
We can optimize the previous approach where we checked all the permutations of the array and combined them to find the largest number. The previous approach, with its time complexity of O(n! * n), is clearly too large to be practical.
To optimize, let's think of a more efficient way.
A common approach that comes to mind is, that instead of checking all permutations, we can sort the array based on the most significant digits of the numbers. This would bring us closer to the correct solution.
For example, consider the array [10, 2]. If we sort it based on the most significant digit, it would become [2, 10]. Combining these two numbers gives 210, which is the largest possible number.
However, this sorting approach won't work in every case. For instance, for the array [30, 3], sorting based on the most significant digit gives [30, 3], which results in 303, but the largest number for this array is 330.
So, we need to refine the approach further. Let’s say we have two numbers a and b. For example, 12 and 3. We can have two possible combinations:
- a + b = "123"
- b + a = "312"
Clearly, 312 is greater. So, the key insight here is to compare the two combinations of each pair of numbers: a + b and b + a. We place the larger combination first. This comparison will allow us to correctly order the numbers.
To implement this, we:
- Compare pairs of numbers a and b by checking whether a + b > b + a or vice versa.
- Sort the array based on this comparison.
- After sorting, simply concatenate all the numbers to form the largest possible number.
This approach ensures that the largest number is formed efficiently without the need for checking all permutations.
Let's understand with an example:
Dry Run of the Approach on Input:
Input: nums = [3,30,34,5,9]
Step 1: Convert all numbers to strings
- nums = [3, 30, 34, 5, 9] becomes ["3", "30", "34", "5", "9"]
Step 2: Sort based on custom comparator
Now, we sort the array using the custom comparator, which compares A + B with B + A for every pair of elements:
- "3" + "30" = "330" vs. "30" + "3" = "303" → "330" is greater, so "3" comes before "30".
- "3" + "34" = "334" vs. "34" + "3" = "343" → "343" is greater, so "34" comes before "3".
- "3" + "5" = "35" vs. "5" + "3" = "53" → "53" is greater, so "5" comes before "3".
- "3" + "9" = "39" vs. "9" + "3" = "93" → "93" is greater, so "9" comes before "3".
- "30" + "34" = "3034" vs. "34" + "30" = "3430" → "3430" is greater, so "34" comes before "30".
- "30" + "5" = "305" vs. "5" + "30" = "530" → "530" is greater, so "5" comes before "30".
- "30" + "9" = "309" vs. "9" + "30" = "930" → "930" is greater, so "9" comes before "30".
- "34" + "5" = "345" vs. "5" + "34" = "534" → "534" is greater, so "5" comes before "34".
- "34" + "9" = "349" vs. "9" + "34" = "934" → "934" is greater, so "9" comes before "34".
- "5" + "9" = "59" vs. "9" + "5" = "95" → "95" is greater, so "9" comes before "5".
After sorting, the array becomes: ["9", "5", "34", "3", "30"]
Step 3: Concatenate the numbers
Concatenate all the sorted strings:
- "9" + "5" + "34" + "3" + "30" = "9534330"
Step 4: Handle the case of leading zeroes
We check if the result starts with "0". Since "9534330" does not, we return the result as is.
Final Output: "9534330"
This is the largest number that can be formed from the array [3, 30, 34, 5, 9].
How to code it up?
Here are the concise steps to code the solution:
- Initialize variables:
- Get the length of the input array nums and store it in n.
- Initialize an empty array vec to hold string representations of the numbers.
- Convert integers to strings:
- Iterate through each number in the input array nums.
- Convert each number to a string and push it into the vec array.
- Sort the array using custom comparator:
- Use the sort() method to order the vec array. The comparator should compare concatenated strings in both possible orders (i.e., b + a vs. a + b) using localeCompare() to decide the order.
- This ensures the largest concatenated number is formed.
- Concatenate all strings:
- Join the elements of the sorted vec array into one large string using the join('') method.
- Check for leading zeros:
- If the first character of the concatenated string is '0', it means all numbers were zero, so return "0".
- Return the result:
- If no leading zeroes, return the concatenated result as the largest number.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
string largestNumber(vector<int>& nums) {
// Step 1: Get the size of the input vector
int n = nums.size();
// Step 2: Create a vector of strings to hold the string representations of the numbers
vector<string> vec;
// Step 3: Convert each integer in the input vector to a string and add to the 'vec' vector
for(auto &num: nums)
vec.push_back(to_string(num));
// Step 4: Sort the 'vec' vector based on the concatenation of the numbers
// The custom comparator checks which concatenation (a+b vs. b+a) is greater
sort(vec.begin(), vec.end(), [&](const string &a, const string &b){
return a + b > b + a; // Compare concatenated strings to determine the correct order
});
// Step 5: Create a new string 'ans' to concatenate the sorted numbers
string ans = "";
for(auto &v: vec) {
ans += v; // Append each number in the sorted vector to 'ans'
}
// Step 6: If the result starts with '0' (i.e., the numbers were all zeros), return "0"
if(ans[0] == '0')
return "0";
// Step 7: Return the concatenated string as the largest number
return ans;
}
};
2. Java Try on Compiler
import java.util.*;
class Solution {
public String largestNumber(int[] nums) {
int n = nums.length;
List<String> vec = new ArrayList<>();
// Convert each integer to string
for (int num : nums) {
vec.add(String.valueOf(num));
}
// Sort the list of strings based on the custom comparator
Collections.sort(vec, (a, b) -> (b + a).compareTo(a + b));
StringBuilder ans = new StringBuilder();
// Concatenate all the strings
for (String v : vec) {
ans.append(v);
}
// If the first character is '0', return "0"
if (ans.charAt(0) == '0') {
return "0";
}
return ans.toString();
}
}
3. Python Try on Compiler
class Solution:
def largestNumber(self, nums):
n = len(nums)
vec = []
# Convert each integer to string
for num in nums:
vec.append(str(num))
# Sort the list of strings based on the custom comparator
vec.sort(key=lambda x: x*10, reverse=True) # Multiply by 10 for correct lexicographic order
# Concatenate all the strings
ans = "".join(vec)
# If the first character is '0', return "0"
if ans[0] == '0':
return "0"
return ans
4. Javascript Try on Compiler
var largestNumber = function(nums) {
let n = nums.length;
let vec = [];
// Convert each integer to string
for (let num of nums) {
vec.push(num.toString());
}
// Sort the list of strings based on the custom comparator
vec.sort((a, b) => (b + a).localeCompare(a + b));
// Concatenate all the strings
let ans = vec.join('');
// If the first character is '0', return "0"
if (ans[0] === '0') {
return "0";
}
return ans;
};
Time Complexity: O(n + m)
- Converting integers to strings:
We iterate over all the n elements in the array and convert each integer to a string.
The time complexity of converting an integer to a string is O(d), where d is the number of digits in the integer.
For all elements, this results in a total time complexity of O(n * d), where d is the average number of digits in the integers. - Sorting the strings:
We sort the vec array using the custom comparator. The custom comparator compares two strings a and b by concatenating them in both possible orders and then comparing them. The time complexity of comparing two strings is proportional to their lengths, which is O(d).
Sorting the vec array takes O(n log n) time, and for each comparison, we perform a comparison of strings of length d, which leads to a total time complexity of O(n log n * d). - Concatenating the strings:
After sorting, we concatenate all the strings into the final result. This takes O(n * d) time, as we concatenate each string from the sorted array. - Edge case check:
Checking if the first character is '0' is a constant time operation, O(1).
Overall Time Complexity:
Considering all steps, the overall time complexity is:
- O(n * d) for converting integers to strings,
- O(n log n * d) for sorting,
- O(n * d) for concatenation.
Thus, the final time complexity is O(n log n * d), where:
- n is the number of elements in the array.
- d is the average number of digits in the numbers.
Since the number of digits in a number is at most log(n) where n is the value of the number, d is bounded by log(10⁹) = 9 for the given input range (as the maximum value of each number is 10⁹.).
So, the time complexity can be approximated as O(n log n).
Space Complexity: O(n)
Auxiliary Space Complexity: O(n)
Explanation: We use an additional vector vec to store the string representations of the numbers. The space required for this vector is O(n * d), where n is the number of elements in the input array and d is the average number of digits in the numbers. During the concatenation process, we build the result string ans. The space for this string is also O(n * d), as we concatenate all the strings from vec into and. Since d can be at most 9, the auxiliary space complexity will be O(n).
Total Space Complexity: O(n)
Explanation: The space for the input array nums is O(n)
The total space complexity is O(n).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given a string s, find the length of the longest substring without repeating characters.
2. Word Subsets
You are given two lists of words: words1 and words2.
A word from words2 is called a subset of a word in words1 if:All the letters in the word from words2 are present in the word from words1.
And each letter appears at least as many times in the word from words1 as it does in the word from words2.For example:
"wrr" is a subset of "warrior" (because "warrior" has at least 2 'r's and one 'w').
But "wrr" is not a subset of "world" (because "world" doesn’t have 2 'r's).A word from words1 is called universal if:
Every word in words2 is a subset of it.The goal is to return all the universal words from words1.