Largest Number (Arrange to Form Biggest)

🎯

Largest Number (Arrange to Form Biggest)

mediumGREEDYAmazonFacebookGoogle

Imagine you have a list of numbers and want to arrange them to form the largest possible number, like arranging puzzle pieces to create the biggest picture.

💡 This problem is about ordering numbers not by their numeric value alone, but by how their string concatenations compare. Beginners often struggle because normal sorting doesn't work; they must understand custom comparison logic.

📋

Problem Statement

Given a list of non-negative integers, arrange them such that they form the largest possible number. Return the result as a string. For example, given [3, 30, 34, 5, 9], the largest formed number is '9534330'.

1 ≤ n ≤ 10^50 ≤ nums[i] ≤ 10^9The result may be very large, so return a string instead of an integer.

💡

Example

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

Output"9534330"

By comparing concatenations, '9' + '5' > '5' + '9', so '9' comes before '5', and so on, resulting in '9534330'.

• All zeros → output should be '0'
• Single element array → output is that element as string
• Numbers with same prefix → e.g. [121, 12]
• Very large numbers → test string concatenation correctness

⚠️

Common Mistakes

Sorting numbers as integers instead of strings

Incorrect order leading to wrong largest number

✅ Convert numbers to strings and use custom comparator based on concatenation

Not handling all zeros case

Output like '000' instead of '0'

✅ Check if first sorted string is '0' and return '0' immediately

Using default sort without custom comparator

Lexicographical or numeric sort gives wrong answer

✅ Implement and use a custom comparator comparing concatenations

Comparing concatenations incorrectly (e.g., using numeric comparison)

Wrong ordering because numeric comparison truncates or overflows

✅ Compare concatenated strings lexicographically as strings

Not converting integers to strings before concatenation

Type errors or incorrect concatenation

✅ Always convert integers to strings before concatenation

🧠

Brute Force (Generate All Permutations)

💡 This approach exists to show the fundamental idea of trying all possible orders to find the maximum, which helps understand why sorting with a custom comparator is needed.

Intuition

Try every possible permutation of the numbers, convert each permutation to a concatenated string, and track the maximum string lexicographically.

Algorithm

1. Generate all permutations of the input list.
2. For each permutation, concatenate the numbers into a string.
3. Compare the concatenated string with the current maximum string.
4. Return the maximum concatenated string found.

💡 The brute force algorithm is straightforward but quickly becomes infeasible as permutations grow factorially.

</>

Code

from itertools import permutations

def largestNumber(nums):
    max_num = ''
    for perm in permutations(nums):
        candidate = ''.join(str(num) for num in perm)
        if candidate > max_num:
            max_num = candidate
    # Handle case where all are zeros
    return '0' if max_num[0] == '0' else max_num

# Driver code
if __name__ == '__main__':
    print(largestNumber([3,30,34,5,9]))  # Output: 9534330

Line Notes

from itertools import permutationsImport permutations to generate all possible orderings

for perm in permutations(nums)Iterate over every possible ordering of nums

candidate = ''.join(str(num) for num in perm)Concatenate current permutation into a string

if candidate > max_numUpdate max_num if current candidate is lexicographically larger

return '0' if max_num[0] == '0' else max_numHandle edge case where all numbers are zero

import java.util.*;

public class LargestNumberBrute {
    public static String largestNumber(int[] nums) {
        List<List<Integer>> permutations = new ArrayList<>();
        permute(nums, 0, permutations);
        String maxNum = "";
        for (List<Integer> perm : permutations) {
            StringBuilder sb = new StringBuilder();
            for (int num : perm) sb.append(num);
            String candidate = sb.toString();
            if (candidate.compareTo(maxNum) > 0) maxNum = candidate;
        }
        if (maxNum.length() > 0 && maxNum.charAt(0) == '0') return "0";
        return maxNum;
    }

    private static void permute(int[] nums, int start, List<List<Integer>> res) {
        if (start == nums.length) {
            List<Integer> perm = new ArrayList<>();
            for (int num : nums) perm.add(num);
            res.add(perm);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            permute(nums, start + 1, res);
            swap(nums, start, i);
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        System.out.println(largestNumber(new int[]{3,30,34,5,9})); // 9534330
    }
}

Line Notes

List<List<Integer>> permutations = new ArrayList<>()Store all permutations generated

permute(nums, 0, permutations)Generate all permutations starting from index 0

for (List<Integer> perm : permutations)Iterate over each permutation to build candidate string

if (candidate.compareTo(maxNum) > 0)Update maxNum if candidate is lexicographically larger

if (maxNum.length() > 0 && maxNum.charAt(0) == '0')Check if all numbers are zero to return '0'

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

void permute(vector<int>& nums, int start, vector<vector<int>>& res) {
    if (start == nums.size()) {
        res.push_back(nums);
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        permute(nums, start + 1, res);
        swap(nums[start], nums[i]);
    }
}

string largestNumber(vector<int>& nums) {
    vector<vector<int>> permutations;
    permute(nums, 0, permutations);
    string maxNum = "";
    for (auto& perm : permutations) {
        string candidate = "";
        for (int num : perm) candidate += to_string(num);
        if (candidate > maxNum) maxNum = candidate;
    }
    if (!maxNum.empty() && maxNum[0] == '0') return "0";
    return maxNum;
}

int main() {
    vector<int> nums = {3,30,34,5,9};
    cout << largestNumber(nums) << endl; // 9534330
    return 0;
}

Line Notes

void permute(vector<int>& nums, int start, vector<vector<int>>& res)Recursive function to generate all permutations

swap(nums[start], nums[i])Swap elements to generate new permutation

string candidate = ""; for (int num : perm) candidate += to_string(num);Concatenate permutation into string

if (candidate > maxNum) maxNum = candidate;Update maxNum if candidate is lexicographically larger

if (!maxNum.empty() && maxNum[0] == '0') return "0";Return '0' if all numbers are zero

function permute(nums, start, res) {
    if (start === nums.length) {
        res.push(nums.slice());
        return;
    }
    for (let i = start; i < nums.length; i++) {
        [nums[start], nums[i]] = [nums[i], nums[start]];
        permute(nums, start + 1, res);
        [nums[start], nums[i]] = [nums[i], nums[start]];
    }
}

function largestNumber(nums) {
    const permutations = [];
    permute(nums, 0, permutations);
    let maxNum = "";
    for (const perm of permutations) {
        const candidate = perm.map(String).join("");
        if (candidate > maxNum) maxNum = candidate;
    }
    return maxNum[0] === '0' ? '0' : maxNum;
}

// Test
console.log(largestNumber([3,30,34,5,9])); // 9534330

Line Notes

function permute(nums, start, res)Recursive function to generate all permutations

[nums[start], nums[i]] = [nums[i], nums[start]];Swap elements to create new permutation

const candidate = perm.map(String).join("");Concatenate permutation into string

if (candidate > maxNum) maxNum = candidate;Update maxNum if candidate is lexicographically larger

return maxNum[0] === '0' ? '0' : maxNum;Return '0' if all numbers are zero

⏱

Complexity

TimeO(n! * n * k) where n is number of elements and k is average digit length

SpaceO(n! * n) to store all permutations

Generating all permutations is factorial in n, and concatenation/comparison adds linear overhead.

💡 For n=10, factorial is 3,628,800, which is impractical to compute in interviews.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem's nature and motivates better solutions.

🧠

Sorting with Custom Comparator

💡 This approach introduces the key insight: sorting numbers as strings with a custom comparator based on concatenation order yields the largest number.

Intuition

Sort numbers as strings so that for any two numbers a and b, the order is decided by which concatenation a+b or b+a forms a larger number.

Algorithm

1. Convert all numbers to strings.
2. Sort the array with a comparator that compares concatenations (a+b vs b+a).
3. Concatenate the sorted array into the final string.
4. If the first character is '0', return '0' to handle all zero case.

💡 The key is the custom comparator that ensures the greedy choice leads to the global maximum.

</>

Code

def largestNumber(nums):
    nums_str = list(map(str, nums))
    # Correct comparator using functools.cmp_to_key
    from functools import cmp_to_key
    def compare(a, b):
        if a + b > b + a:
            return -1
        elif a + b < b + a:
            return 1
        else:
            return 0
    nums_str.sort(key=cmp_to_key(compare))
    result = ''.join(nums_str)
    return '0' if result[0] == '0' else result

# Driver code
if __name__ == '__main__':
    print(largestNumber([3,30,34,5,9]))  # Output: 9534330

Line Notes

nums_str = list(map(str, nums))Convert all integers to strings for concatenation comparison

from functools import cmp_to_keyImport helper to use custom comparator in sort

def compare(a, b)Define comparator that decides order based on concatenation

if a + b > b + aIf concatenation a+b is lexicographically larger, a should come before b

nums_str.sort(key=cmp_to_key(compare))Sort array using the custom comparator

return '0' if result[0] == '0' else resultHandle edge case where all numbers are zero

import java.util.*;

public class LargestNumberSort {
    public static String largestNumber(int[] nums) {
        String[] numsStr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) numsStr[i] = String.valueOf(nums[i]);
        Arrays.sort(numsStr, new Comparator<String>() {
            public int compare(String a, String b) {
                String order1 = a + b;
                String order2 = b + a;
                return order2.compareTo(order1); // descending order
            }
        });
        if (numsStr[0].equals("0")) return "0";
        StringBuilder sb = new StringBuilder();
        for (String s : numsStr) sb.append(s);
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(largestNumber(new int[]{3,30,34,5,9})); // 9534330
    }
}

Line Notes

String[] numsStr = new String[nums.length]Convert integers to strings for comparison

Arrays.sort(numsStr, new Comparator<String>()Sort using custom comparator

return order2.compareTo(order1)Compare concatenations in descending order to get largest number

if (numsStr[0].equals("0")) return "0"If highest number is zero, all are zero

StringBuilder sb = new StringBuilder()Efficiently build the final string

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

bool compare(string &a, string &b) {
    return a + b > b + a;
}

string largestNumber(vector<int>& nums) {
    vector<string> numsStr;
    for (int num : nums) numsStr.push_back(to_string(num));
    sort(numsStr.begin(), numsStr.end(), compare);
    if (numsStr[0] == "0") return "0";
    string result = "";
    for (string &s : numsStr) result += s;
    return result;
}

int main() {
    vector<int> nums = {3,30,34,5,9};
    cout << largestNumber(nums) << endl; // 9534330
    return 0;
}

Line Notes

bool compare(string &a, string &b)Custom comparator comparing concatenations

return a + b > b + aDecide order by which concatenation is lexicographically larger

sort(numsStr.begin(), numsStr.end(), compare)Sort strings using custom comparator

if (numsStr[0] == "0") return "0"Handle all zero case

for (string &s : numsStr) result += sConcatenate sorted strings to form result

function largestNumber(nums) {
    let numsStr = nums.map(String);
    numsStr.sort((a, b) => (b + a).localeCompare(a + b));
    if (numsStr[0] === '0') return '0';
    return numsStr.join('');
}

// Test
console.log(largestNumber([3,30,34,5,9])); // 9534330

Line Notes

let numsStr = nums.map(String)Convert numbers to strings for concatenation comparison

numsStr.sort((a, b) => (b + a).localeCompare(a + b))Sort with custom comparator based on concatenation order

if (numsStr[0] === '0') return '0'Return '0' if all numbers are zero

return numsStr.join('')Concatenate sorted strings to form final number

⏱

Complexity

TimeO(n log n * k) where n is number of elements and k is max digit length

SpaceO(n * k) for string conversions

Sorting dominates complexity; each comparison involves string concatenation of length up to 2k.

💡 For n=10^5 and k=10, this is efficient enough for interviews.

Interview Verdict: Accepted

This is the standard and efficient approach to solve the problem in interviews.

🧠

Optimized Sorting with Early Exit and Edge Handling

💡 This approach refines the custom comparator sorting by adding early exit for all zero case and minor optimizations to reduce overhead.

Intuition

After sorting with the custom comparator, if the first number is zero, the entire number is zero. We can also optimize string concatenations by caching or minimizing operations.

Algorithm

1. Convert numbers to strings.
2. Sort with custom comparator comparing concatenations.
3. If the first string is '0', return '0' immediately.
4. Concatenate all strings to form the largest number.

💡 The early exit prevents unnecessary concatenation when all numbers are zero, improving performance.

</>

Code

def largestNumber(nums):
    from functools import cmp_to_key
    nums_str = list(map(str, nums))
    def compare(a, b):
        return -1 if a + b > b + a else 1 if a + b < b + a else 0
    nums_str.sort(key=cmp_to_key(compare))
    if nums_str[0] == '0':
        return '0'
    return ''.join(nums_str)

# Driver code
if __name__ == '__main__':
    print(largestNumber([3,30,34,5,9]))  # 9534330

Line Notes

from functools import cmp_to_keyImport cmp_to_key for custom sorting

nums_str = list(map(str, nums))Convert integers to strings

def compare(a, b)Comparator returns -1, 1, or 0 based on concatenation comparison

nums_str.sort(key=cmp_to_key(compare))Sort using custom comparator

if nums_str[0] == '0'Early exit if all numbers are zero

return ''.join(nums_str)Concatenate sorted strings to form result

import java.util.*;

public class LargestNumberOptimized {
    public static String largestNumber(int[] nums) {
        String[] numsStr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) numsStr[i] = String.valueOf(nums[i]);
        Arrays.sort(numsStr, (a, b) -> (b + a).compareTo(a + b));
        if (numsStr[0].equals("0")) return "0";
        StringBuilder sb = new StringBuilder();
        for (String s : numsStr) sb.append(s);
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(largestNumber(new int[]{3,30,34,5,9})); // 9534330
    }
}

Line Notes

String[] numsStr = new String[nums.length]Convert integers to strings

Arrays.sort(numsStr, (a, b) -> (b + a).compareTo(a + b))Sort with concise lambda comparator

if (numsStr[0].equals("0")) return "0"Early exit for all zero case

StringBuilder sb = new StringBuilder()Efficient string concatenation

for (String s : numsStr) sb.append(s)Build final result string

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

string largestNumber(vector<int>& nums) {
    vector<string> numsStr;
    for (int num : nums) numsStr.push_back(to_string(num));
    sort(numsStr.begin(), numsStr.end(), [](const string &a, const string &b) {
        return a + b > b + a;
    });
    if (numsStr[0] == "0") return "0";
    string result;
    for (const string &s : numsStr) result += s;
    return result;
}

int main() {
    vector<int> nums = {3,30,34,5,9};
    cout << largestNumber(nums) << endl; // 9534330
    return 0;
}

Line Notes

sort(numsStr.begin(), numsStr.end(), [](const string &a, const string &b)Use lambda for custom comparator

return a + b > b + aDecide order by concatenation comparison

if (numsStr[0] == "0") return "0"Early exit if all zeros

string result; for (const string &s : numsStr) result += sConcatenate sorted strings

vector<string> numsStr; for (int num : nums) numsStr.push_back(to_string(num))Convert integers to strings

function largestNumber(nums) {
    let numsStr = nums.map(String);
    numsStr.sort((a, b) => (b + a).localeCompare(a + b));
    if (numsStr[0] === '0') return '0';
    return numsStr.join('');
}

// Test
console.log(largestNumber([3,30,34,5,9])); // 9534330

Line Notes

let numsStr = nums.map(String)Convert numbers to strings

numsStr.sort((a, b) => (b + a).localeCompare(a + b))Sort with custom comparator based on concatenation

if (numsStr[0] === '0') return '0'Early exit for all zero case

return numsStr.join('')Concatenate sorted strings to form final number

⏱

Complexity

TimeO(n log n * k) where n is number of elements and k is max digit length

SpaceO(n * k) for string conversions

Same as previous approach but with minor optimizations and early exit.

💡 This approach is the practical and interview-ready solution.

Interview Verdict: Accepted

This is the optimal approach to implement in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always implement the custom comparator sorting approach (Approach 2 or 3) for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n! * n * k)	O(n! * n)	Yes (deep recursion)	Yes	Mention only - never code
2. Sorting with Custom Comparator	O(n log n * k)	O(n * k)	No	N/A	Code this approach
3. Optimized Sorting with Early Exit	O(n log n * k)	O(n * k)	No	N/A	Code this approach for best practice

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal approach, and prepare for common follow-ups and edge cases.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Explain the brute force approach to show understanding.Step 3: Introduce the custom comparator sorting approach.Step 4: Code the optimal solution with early exit.Step 5: Test with edge cases and discuss complexity.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of custom sorting, string manipulation, edge case handling, and efficiency.

Common Follow-ups

• What if numbers are very large? → Use strings to avoid overflow.
• Can you do this without converting to strings? → No, string comparison is essential.
• How to handle leading zeros? → Return '0' if first sorted string is '0'.
• What if input size is huge? → Sorting with custom comparator is efficient enough.

💡 These follow-ups test your grasp of edge cases, data types, and performance considerations.

🔍

Pattern Recognition

When to Use

1) Need to arrange numbers to form largest/smallest number; 2) Output is a string; 3) Normal sorting fails; 4) Custom comparator based on concatenation order is needed.

Signature Phrases

'arrange to form the largest number''concatenate numbers to form biggest string'

NOT This Pattern When

Sorting numbers normally or DP problems involving sums or subsets

Similar Problems

Form Largest Number from Array - same pattern of custom comparator sortingMinimum Number by Rearranging Digits - similar but for smallest numberLargest Number After Digit Swaps - involves rearranging digits greedily

Practice

1. You are given a numeric string and an integer k. The task is to remove exactly k digits from the string so that the resulting number is the smallest possible. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Backtracking to try all combinations of digits to remove

B. Dynamic Programming that tries all subsequences of length n-k and picks the smallest

C. Sorting the digits and removing the largest k digits

D. Greedy algorithm using a stack to maintain a monotonically increasing sequence of digits

Solution

1. Step 1: Understand the problem constraints

   The problem requires removing digits to minimize the resulting number, which suggests a greedy approach to decide which digits to remove as we scan the string.

2. Step 2: Why greedy with stack works

   The stack-based greedy approach maintains a monotonically increasing sequence by popping larger digits when a smaller digit is encountered, ensuring the smallest possible prefix at each step.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy stack approach is known optimal for this problem [OK]

Hint: Monotonic stack ensures smallest prefix greedily [OK]

Common Mistakes:

• Assuming sorting digits works ignores digit order
• Thinking DP is needed for this greedy problem
• Trying brute force is too slow for large inputs

2. Suppose the Gas Station problem is modified so that you can refill gas multiple times at the same station (i.e., unlimited reuse), and you want to find if any start station allows completing the circle with this new rule. Which approach correctly adapts to this variant?

hard

A. Check if total gas is at least total cost; if yes, return any station since reuse allows completion

B. Modify the algorithm to allow multiple passes over the stations until tank is non-negative

C. Use a graph cycle detection algorithm to find a feasible cycle with unlimited refills

D. Use the original greedy approach without changes; it still works correctly

Solution

1. Step 1: Understand unlimited refill effect

   With unlimited refills, the only constraint is total gas >= total cost; any station can be start.

2. Step 2: Simplify solution

   Since reuse removes the need to track tank drops, just check total gas vs cost and return any index if feasible.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Unlimited refill means any station works if total gas suffices [OK]

Hint: Unlimited refill means total gas check suffices [OK]

Common Mistakes:

• Trying to simulate multiple passes
• Using original greedy without adaptation
• Overcomplicating with graph algorithms

3. Suppose the problem is modified so that characters can be reused in multiple partitions (i.e., the constraint that each letter appears in at most one part is removed). Which of the following approaches correctly adapts the algorithm to find the minimum number of partitions such that each partition contains unique characters (no repeats within the partition)?

hard

A. Use backtracking to try all partitions and select the minimal count

B. Use the original greedy approach with last occurrence map unchanged

C. Use a sliding window approach expanding partitions until a repeated character is found, then start a new partition

D. Sort characters by frequency and greedily assign them to partitions

Solution

1. Step 1: Understand new constraint

   Characters can appear in multiple partitions, but no repeats allowed within a partition.

2. Step 2: Identify suitable approach

   Sliding window expanding until a repeated character is found ensures partitions with unique characters; then start a new partition.

3. Step 3: Why original greedy fails

   Original approach relies on last occurrence to avoid repeats across partitions, which is irrelevant here.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Sliding window detects repeats within partition, minimal partitions formed [OK]

Hint: Sliding window for unique chars per partition [OK]

Common Mistakes:

• Using last occurrence map which is irrelevant here
• Trying backtracking which is inefficient
• Sorting characters which doesn't solve partitioning

4. Suppose the problem is modified so that characters can be reused unlimited times (infinite supply), and you want to generate a string of length n with no two adjacent characters the same. Which modification to the max heap approach is necessary to handle this variant correctly?

hard

A. No change needed; the original heap approach works as is for infinite reuse

B. Track only the last used character and pick any other character from the set for the next position

C. Use a queue instead of a heap to cycle through characters ensuring no adjacency

D. Remove frequency counts and always push characters back immediately after use to allow reuse

Solution

1. Step 1: Understand infinite reuse implication

   Since characters can be reused infinitely, frequency counts are irrelevant; characters must be available again immediately after use.

2. Step 2: Modify heap usage

   Remove frequency decrement logic and always push characters back immediately after use to allow reuse while avoiding adjacency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Immediate pushback enables infinite reuse without adjacency violation [OK]

Hint: Infinite reuse means no frequency decrement [OK]

Common Mistakes:

• Assuming original approach works unchanged
• Using queue without frequency logic
• Ignoring adjacency constraints

5. If tasks can be reused infinitely (i.e., unlimited supply of each task type), how should the Task Scheduler algorithm be modified to find the minimum total time with cooldown n?

hard

A. Use the same max-heap approach but reset frequencies after each full cycle

B. Calculate the minimal cycle length as (n + 1) and multiply by the number of unique tasks

C. Since tasks are infinite, schedule tasks in a fixed repeating pattern of length (n + 1) without heap

D. The problem reduces to scheduling one task repeatedly with cooldown, so total time is tasks count

Solution

1. Step 1: Understand infinite reuse implication

   With infinite supply, the scheduler can always pick a different task to fill cooldown slots.

2. Step 2: Optimal scheduling pattern

   Tasks can be scheduled in a fixed repeating pattern of length n + 1, cycling through unique tasks to avoid idle time.

3. Step 3: Algorithm modification

   No need for frequency tracking or heap; just cycle through unique tasks repeatedly.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Infinite tasks allow fixed pattern scheduling without heap [OK]

Hint: Infinite tasks -> fixed repeating pattern of length n+1 [OK]

Common Mistakes:

• Trying to use heap with infinite tasks
• Multiplying cycles incorrectly
• Ignoring cooldown constraints