Log inSign up
mediumLeetCodeNot Started

Largest Number

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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 · Simple Two Number Ordering:

Input: nums = [10, 2]
Output: "210"
Explanation: Combining 2 and 10 gives 210, which is larger than 102.

Example 2 · Multi-digit Prefix Comparison:

Input: nums = [3, 30, 34, 5, 9]
Output: "9534330"
Explanation: 9 comes first, followed by 5, then 34, 3, and 30.

Example 3 · All Zeroes Edge Case:

Input: nums = [0, 0]
Output: "0"
Explanation: Combining [0, 0] produces "00", which should be simplified to "0".

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 109

Prerequisites

Before attempting this problem, you should be comfortable with:

  • String conversions and concatenation
  • Custom comparator sorting and strict weak ordering
  • Greedy strategy transitivity proofs

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why pairwise concatenation comparison (A+B vs B+A) is necessary and sufficient.
  • Learn to implement custom comparators across C++, Java, Python, and JavaScript.
  • Handle the all-zeroes edge case correctly.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Custom Sort StringReorganize StringCourse Schedule III (Greedy Sorting)

1. Permutation Generation (Brute Force)

Intuition

There are n! possible arrangements of n numbers. We can recursively construct all n! permutations, concatenate them into a full number string, and update the global maximum using lexicographical comparison.

When to apply: Use only for conceptual validation on tiny inputs (n <= 8).

All Permutations Concatenation (O(N!) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
First permutation candidate
Visual state
Values and pointers at this exact step
pointers
S
3
30
34
5
9
0
↑ perm0
1
2
3
4
Variables at this step
currentPerm
3303459
maxStr
3303459
Check / comparison
Generate permutation 0: "3" + "30" + "34" + "5" + "9" = "3303459"
Decision / next transition
Initialize maxStr = "3303459".
Why this step matters

First permutation candidate.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 private String maxNum = "0";
6
7 public String largestNumber(int[] nums) {
8 String[] strs = new String[nums.length];
9 for (int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]);
10 permute(strs, 0);
11 return maxNum.charAt(0) == '0' ? "0" : maxNum;
12 }
13
14 private void permute(String[] strs, int idx) {
15 if (idx == strs.length) {
16 StringBuilder sb = new StringBuilder();
17 for (String s : strs) sb.append(s);
18 String cand = sb.toString();
19 if (maxNum.equals("0") || cand.compareTo(maxNum) > 0) {
20 maxNum = cand;
21 }
22 return;
23 }
24 for (int i = idx; i < strs.length; i++) {
25 swap(strs, idx, i);
26 permute(strs, idx + 1);
27 swap(strs, idx, i);
28 }
29 }
30
31 private void swap(String[] strs, int i, int j) {
32 String temp = strs[i];
33 strs[i] = strs[j];
34 strs[j] = temp;
35 }
36 }
37
38 public static void main(String[] args) {
39 Solution sol = new Solution();
40 int[] nums = {3, 30, 34, 5, 9};
41 System.out.println("Largest Number: " + sol.largestNumber(nums));
42 }
43}

Time & Space Complexity

  • Time complexity: O(n! * n * k) — Generating all n! permutations and building concatenated strings of length n * k takes O(n! * n * k) time.
  • Space complexity: O(n * k) — Recursion depth and string buffers take O(n * k) memory.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Insertion Sort with Custom Order (Better)

Intuition

To determine if string a should appear before string b, we compare the two concatenated forms: (a + b) vs (b + a). If (a + b) > (b + a), then a should precede b. This comparison defines a strict weak ordering. Insertion sort builds the sorted prefix one element at a time.

When to apply: Use when demonstrating the total transitive order property of the concatenation comparison.

Standard Lexicographical Suffix Sort (Pitfall Demo)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Standard sorting compares character by character
Visual state
Values and pointers at this exact step
pointers
S
3
30
34
5
9
0
↑ raw
1
2
3
4
Variables at this step
strings
["3","30","34","5","9"]
Check / comparison
Convert integers to strings: ["3", "30", "34", "5", "9"]
Decision / next transition
Attempt sorting with standard descending string comparator.
Why this step matters

Standard sorting compares character by character.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public String largestNumber(int[] nums) {
4 String[] strs = new String[nums.length];
5 for (int i = 0; i < nums.length; i++) {
6 strs[i] = String.valueOf(nums[i]);
7 }
8 // Insertion sort with custom comparator
9 for (int i = 1; i < strs.length; i++) {
10 String key = strs[i];
11 int j = i - 1;
12 while (j >= 0 && (strs[j] + key).compareTo(key + strs[j]) < 0) {
13 strs[j + 1] = strs[j];
14 j--;
15 }
16 strs[j + 1] = key;
17 }
18 if (strs[0].equals("0")) return "0";
19 StringBuilder sb = new StringBuilder();
20 for (String s : strs) sb.append(s);
21 return sb.toString();
22 }
23 }
24
25 public static void main(String[] args) {
26 Solution sol = new Solution();
27 int[] nums = {3, 30, 34, 5, 9};
28 System.out.println("Largest Number: " + sol.largestNumber(nums));
29 }
30}

Time & Space Complexity

  • Time complexity: O(n^2 * k) — Insertion sort performs O(n2) comparisons, each comparing strings of length up to 2k.
  • Space complexity: O(n * k) — O(n * k) space to store string representations of the numbers.

3. Custom Comparator Sort (Optimal)

Intuition

1. Convert each integer to its string equivalent. 2. Sort the array using the custom rule: string a precedes b if (b + a) < (a + b). 3. Edge case: If the largest element after sorting is 0, the entire array consists of zeros; return 0 immediately. 4. Concatenate and return the result.

When to apply: Use as the gold-standard production solution for the Largest Number problem.

Custom Transitive Comparator Sort (O(N log N * L) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Sorting with this custom comparator guarantees the globally largest concatenation
Visual state
Values and pointers at this exact step
pointers
S
3
30
34
5
9
0
↑ raw
1
2
3
4
Variables at this step
comparator
(a+b) vs (b+a)
Check / comparison
Define comparator: given a, b, a comes before b if (a + b) > (b + a)
Decision / next transition
This relation is provably transitive and defines a total ordering.
Why this step matters

Sorting with this custom comparator guarantees the globally largest concatenation.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.Arrays;
2
3public class Main {
4 public static class Solution {
5 public String largestNumber(int[] nums) {
6 String[] strs = new String[nums.length];
7 for (int i = 0; i < nums.length; i++) {
8 strs[i] = String.valueOf(nums[i]);
9 }
10 Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
11 if (strs[0].equals("0")) {
12 return "0";
13 }
14 StringBuilder sb = new StringBuilder();
15 for (String s : strs) {
16 sb.append(s);
17 }
18 return sb.toString();
19 }
20 }
21
22 public static void main(String[] args) {
23 Solution sol = new Solution();
24 int[] nums = {3, 30, 34, 5, 9};
25 System.out.println("Largest Number: " + sol.largestNumber(nums));
26 }
27}

Time & Space Complexity

  • Time complexity: O(n log n * k) — Sorting takes O(n log n) comparisons, with each string comparison taking O(k) time where k is the maximum number of digits.
  • Space complexity: O(n * k) — O(n * k) space to store string representations and the output string.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — PermutationsO(N! * N * K)O(N * K)Generate all N! permutations of nums, concatenate each, and track maximum string.Generating N! permutations.
2.Better — Bubble Sort with ComparatorO(N^2 * K)O(N * K)Perform pairwise bubble swaps using (b + a > a + b) rule.Repeated adjacent swaps.
3.Optimal — Custom Comparator SortOptimalO(N log N * K)O(N * K)Sort strings using standard O(N log N) sorting with concatenation comparator.None; industry-standard optimal solution.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • All zeroes [0, 0, 0] must return 0, NOT 000.
  • Numbers with shared prefix but different lengths (e.g. 3 and 30, 3 and 34).
  • Single element array [0] returns 0, [9] returns 9.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Largest Number?

2.Why is the brute force approach suboptimal for large inputs in Largest Number?

3.Which data structure or technique enables the optimal solution for Largest Number?

Back to DSA Sheet