Largest Number
Problem link: https://leetcode.com/problems/largest-number/
Problem Statement
Given a list of non-negative integers nums, arrange them such that they form the largest number and return it as a string.
Since the result may be very large, you need to return a string instead of an integer.
Input
An array of non-negative integers nums.
Output
A string representing the largest possible number.
Example
Input: nums = [3,30,34,5,9] Output: "9534330"
Explanation
When comparing 3 and 30:
- 3 + 30 = "330"
- 30 + 3 = "303" Since 330 > 303, 3 comes before 30.
Brute Force
Intuition
Generate all possible permutations of the numbers, concatenate them into strings, and find the maximum one.
Approach
- Use recursion to find all permutations of the array.
- For each permutation, join the numbers into a single string.
- Compare all resulting strings and keep track of the largest.
Dry Run
nums = [10, 2] Perms: [10,2] -> "102", [2,10] -> "210" Max: "210"
Code (Java)
Complexity Analysis
There are N! permutations for an array of size N.
Optimal Solution
Intuition
Instead of checking all permutations, we define a custom comparison rule between any two numbers A and B: compare (A + B) with (B + A). If (B + A) is greater, then B should come before A. This rule is transitive, allowing us to use standard sorting algorithms.
Approach
- Convert all integers in the array to strings.
- Sort the string array using a custom comparator:
(s1, s2) -> (s2 + s1).compareTo(s1 + s2). - After sorting, if the largest number (first element) is "0", the entire result is "0".
- Join all sorted strings into one and return.
Dry Run
nums = [3, 30]
- Strings: "3", "30"
- Compare "330" and "303": "330" is larger.
- Sorted order: ["3", "30"]
- Result: "330"
Code (Java)
import java.util.*;
class Solution {
public String largestNumber(int[] nums) {
String[] asStrs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
asStrs[i] = String.valueOf(nums[i]);
}
Arrays.sort(asStrs, (a, b) -> (b + a).compareTo(a + b));
if (asStrs[0].equals("0")) return "0";
StringBuilder sb = new StringBuilder();
for (String s : asStrs) sb.append(s);
return sb.toString();
}
}
Complexity Analysis
Sorting takes O(N log N) comparisons, and each comparison involves string concatenation and comparison of length K (where K is avg number of digits). Space is used to store the string versions of numbers.
Quick Revision (Brute Force)
- Generate all permutations
- Very slow: O(N!)
Quick Revision (Optimal)
- Custom sort comparator
- Compare (b+a) with (a+b)
- Handle leading zero edge case
- O(N log N) time