Introduction

The Largest Number problem involves arranging numbers such that they form the largest possible number.

Given:

  • an array of non-negative integers

the task is to:

  • arrange numbers
  • concatenate them
  • return the largest possible number

This problem is one of the most important applications of:

 Custom Sorting Comparator

This problem helps in understanding:

  • custom sorting
  • string comparison
  • greedy ordering
  • comparator logic

Example

Input:arr = [3, 30, 34, 5, 9]

Output:
"9534330"

Explanation:
Correct arrangement:
9 → 5 → 34 → 3 → 30

Largest number formed:
9534330

Constraints

1 <= arr.length <= 10^50 <= arr[i] <= 10^9

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Generate all permutations
  2. Form numbers using concatenation
  3. Track largest value

This works for small arrays but becomes extremely slow for large inputs.

Steps

  1. Generate all permutations.
  2. Concatenate numbers.
  3. Compare generated values.
  4. Store maximum number.
  5. Return largest result.

Dry Run

Input:[3, 30, 34]

Possible permutations:
33034
33430
30334
30343
34330
34303

Largest number:
34330

Final Result:
"34330"

Brute Force Code

Complexity Analysis

Time Complexity: O(n!)Explanation:
All permutations are generated.

Space Complexity: O(n)
Explanation:
Recursive stack and permutations are used.

Approach 2 : Custom Comparator Sorting

Explanation

The optimized solution uses:

 Custom Comparator

The idea is:

For two numbers:

  • x
  • y

compare:

 xy vs yx

Example:

"9" + "34" = "934""34" + "9" = "349"

Since:

 934 > 349

9 should come before 34.

Steps

  1. Convert numbers to strings.
  2. Apply custom sorting.
  3. Compare:
    • xy
    • yx
  4. Arrange largest combinations first.
  5. Join strings.
  6. Return result.

Dry Run

Input:[3, 30, 34, 5, 9]

Compare:
3 and 30
330 > 303

So:
3 comes before 30

Compare:
9 and 34
934 > 349

So:
9 comes before 34

Sorted order:
[9, 5, 34, 3, 30]

Final Result:
"9534330"

Custom Comparator Sorting Code

Complexity Analysis

Time Complexity: O(n log n)Explanation:
Custom sorting dominates the complexity.

Space Complexity: O(n)
Explanation:
Extra string storage is used.

Edge Cases

  1. All zeros
  2. Single element array
  3. Large numbers
  4. Duplicate numbers
  5. Numbers with same prefixes

Why This Problem is Important

Largest Number helps in understanding:

  1. Custom comparators
  2. String-based sorting
  3. Greedy ordering
  4. Comparator logic
  5. Sorting applications

It is one of the most important custom sorting interview problems.

Real-World Applications

Custom sorting concepts are used in:

  1. Ranking systems
  2. Priority ordering
  3. Search engines
  4. Recommendation systems
  5. Scheduling systems

Common Mistakes

  1. Incorrect comparator logic
  2. Forgetting string conversion
  3. Handling leading zeros incorrectly
  4. Wrong concatenation order

Interview Tips

Interviewers often expect:

  1. Custom comparator explanation
  2. xy vs yx comparison logic
  3. Sorting optimization understanding

Always explain:

  • why normal sorting fails
  • why concatenation comparison works
  • how greedy ordering forms maximum number

Related Questions

  1. Merge Intervals
  2. Quick Sort
  3. Sort Colors
  4. Partition Array
  5. Kth Largest Element

Final Takeaway

The Largest Number problem is a fundamental custom sorting problem that teaches comparator-based ordering and greedy arrangement techniques. Understanding this problem builds a strong foundation for advanced sorting and comparator interview problems.