# Largest Number
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/largest-number)
Canonical: https://scaleengineer.com/dsa/problems/largest-number
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, String
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Huawei](https://scaleengineer.com/companies/huawei), [Myntra](https://scaleengineer.com/companies/myntra), [Oracle](https://scaleengineer.com/companies/oracle), [Paytm](https://scaleengineer.com/companies/paytm), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Siemens](https://scaleengineer.com/companies/siemens), [Visa](https://scaleengineer.com/companies/visa), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [josh technology](https://scaleengineer.com/companies/josh-technology), [Salesforce](https://scaleengineer.com/companies/salesforce), [Works Applications](https://scaleengineer.com/companies/works-applications), [Nykaa](https://scaleengineer.com/companies/nykaa), [Zalando](https://scaleengineer.com/companies/zalando), [Graviton](https://scaleengineer.com/companies/graviton)
---
## Problem
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 <= 100`
* `0 <= nums[i] <= 109`

# Approaches
## Brute Force by Generating All Permutations
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.
**Time:** O(N! * N * L) · **Space:** O(N * L)
**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).
### Explanation
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.

```java
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;
            }
        }
    }
}
```
### Algorithm
- Create a recursive function to generate all permutations of the input `nums` array.
- 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.

## Custom Sorting Logic
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.
**Time:** O(N * log(N) * L) · **Space:** O(N * L)
**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.
### Explanation
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.

```java
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();
    }
}
```
### Algorithm
- Convert each integer in the input array `nums` into its string representation and store them in a new array, say `s_nums`.
- Implement a custom `Comparator` for strings.
- The comparison logic for two strings `a` and `b` is based on the concatenated results: `a` should come before `b` if `a + b` is lexicographically greater than `b + a`.
- Sort the `s_nums` array 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.

# Solutions
### CSharp

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

### Java

```java
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);
  }
}

```

### JavaScript

```javascript
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 ' ; }
```

### CPP

```cpp
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 ; } };
```

### Python

```python
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)

```