Largest Number (Arrange to Form Biggest)

📋

Problem

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.

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.

Edge cases: All zeros → output should be '0'Single element array → output is that element as stringNumbers with same prefix → e.g. [121, 12]

</>

IDE

def largestNumber(nums: list[int]) -> str:public String largestNumber(int[] nums)string largestNumber(vector<int>& nums)function largestNumber(nums)

def largestNumber(nums):
    # Write your solution here
    pass

class Solution {
    public String largestNumber(int[] nums) {
        // Write your solution here
        return "";
    }
}

#include <vector>
#include <string>
using namespace std;

string largestNumber(vector<int>& nums) {
    // Write your solution here
    return "";
}

function largestNumber(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 303Sorting numbers as integers or lex order without custom comparator leads to wrong order.✅ Implement comparator comparing concatenated strings x+y and y+x to decide order.

Wrong: 000Failing to handle all zeros case, returning concatenated zeros instead of '0'.✅ After sorting, if result starts with '0', return '0' instead of full string.

Wrong: 12112Incorrect ordering of numbers with same prefix due to lexicographic comparison only.✅ Comparator must compare concatenations x+y and y+x, not just prefixes.

Wrong: No handling of empty input, causing crash or empty output.✅ Add base case: if input is empty, return empty string.

Wrong: 9 91 90Sorting by first digit only, ignoring concatenation order.✅ Use custom comparator comparing x+y and y+x strings to order correctly.

✓

Test Cases

Now that basics work, test edge cases like empty input and all zeros to ensure robustness.

Focus on tricky cases with numbers sharing prefixes to catch subtle comparator bugs.

Optimize your solution to handle large inputs efficiently using sorting with a custom comparator.

t1_01basic

Input{"nums":[3,30,34,5,9]}

Expected"9534330"

⏱ Performance - must finish in 2000ms

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

💡 Try sorting numbers by comparing concatenated strings in both orders.

💡 Use a custom comparator that compares 'xy' and 'yx' where x and y are numbers as strings.

💡 Sort nums so that for any pair x,y, x+y > y+x means x comes before y.

Why it failed: Basic case failed - likely sorting comparator incorrect. Fix by comparing concatenations as strings: if x+y > y+x, x should come before y.

✓ Core custom comparator logic is correct.

t1_02basic

Input{"nums":[10,2]}

Expected"210"

⏱ Performance - must finish in 2000ms

Comparing '2'+'10' = '210' and '10'+'2' = '102', '210' > '102', so '2' comes before '10'.

💡 Check ordering by concatenating pairs in both possible orders.

💡 Ensure comparator returns correct order based on string concatenation comparison.

💡 Sort so that '2' precedes '10' because '210' > '102'.

Why it failed: Failed to order numbers correctly by concatenation comparison. Fix comparator to compare x+y and y+x strings properly.

✓ Comparator correctly orders numbers by concatenation.

t2_01edge

Input{"nums":[]}

Expected""

⏱ Performance - must finish in 2000ms

Empty input should return empty string as no numbers to arrange.

💡 Consider what to return if input list is empty.

💡 Check for empty input and return empty string immediately.

💡 Add a base case: if nums is empty, return ''.

Why it failed: Function crashes or returns invalid output on empty input. Fix by adding check: if not nums: return ''.

✓ Handles empty input gracefully by returning empty string.

t2_02edge

Input{"nums":[0]}

Expected"0"

⏱ Performance - must finish in 2000ms

Single element array returns that element as string.

💡 Check behavior when only one number is present.

💡 Return the single number as string without extra processing.

💡 If length is 1, return str(nums[0]).

Why it failed: Fails single element case by incorrect formatting or extra processing. Fix by returning str(nums[0]) directly.

✓ Correctly returns single element as string.

t2_03edge

Input{"nums":[0,0,0]}

Expected"0"

⏱ Performance - must finish in 2000ms

All zeros should return '0' instead of '000'.

💡 Check if all numbers are zero after sorting.

💡 If the highest number is '0', return '0' instead of concatenated zeros.

💡 Add a check: if result starts with '0', return '0'.

Why it failed: Returns multiple zeros instead of single '0'. Fix by returning '0' if the first character of result is '0'.

✓ Correctly returns single '0' for all zero inputs.

t3_01corner

Input{"nums":[121,12]}

Expected"12121"

⏱ Performance - must finish in 2000ms

Comparing '12112' and '12121', '12121' > '12112', so '12' should come after '121'.

💡 Beware of numbers with same prefix; compare concatenations carefully.

💡 Use custom comparator comparing x+y and y+x strings.

💡 Ensure '121' precedes '12' because '12112' < '12121'.

Why it failed: Incorrect ordering of numbers with same prefix due to lexicographic comparison only. Fix comparator to compare concatenated strings x+y and y+x.

✓ Correctly orders numbers with same prefix by concatenation comparison.

t3_02corner

Input{"nums":[8308,830]}

Expected"8308830"

⏱ Performance - must finish in 2000ms

Comparing '8308830' and '8308308', '8308830' > '8308308', so '8308' comes before '830'.

💡 Test cases where numbers share prefix but differ in length.

💡 Comparator must compare concatenations, not just prefixes.

💡 Sort so that '8308' precedes '830' because '8308830' > '8308308'.

Why it failed: Fails to order numbers with shared prefix and different lengths correctly. Fix comparator to compare full concatenations x+y and y+x.

✓ Handles prefix and length differences correctly in ordering.

t3_03corner

Input{"nums":[9,91,90]}

Expected"99190"

⏱ Performance - must finish in 2000ms

Ordering '9', '91', '90' by concatenation yields '99190' as largest number.

💡 Beware greedy approach that sorts only by first digit.

💡 Use full concatenation comparison to decide order.

💡 Sort so '9' > '91' > '90' because '991' > '919' and '9190' > '9091'.

Why it failed: Greedy approach sorting by first digit fails here. Fix by comparing concatenations x+y and y+x for ordering.

✓ Correctly orders numbers using concatenation comparator, avoiding greedy trap.

t4_01performance

Input{"nums":[999999937,999999929,999999893,999999883,999999857,999999853,999999841,999999829,999999823,999999809,999999797,999999787,999999773,999999763,999999757,999999749,999999743,999999727,999999719,999999713,999999701,999999689,999999683,999999671,999999659,999999653,999999647,999999631,999999623,999999617,999999607,999999599,999999589,999999577,999999571,999999563,999999547,999999541,999999533,999999523,999999517,999999509,999999503,999999491,999999487,999999479,999999467,999999461,999999457,999999449,999999443,999999437,999999433,999999421,999999419,999999413,999999401,999999397,999999389,999999383,999999379,999999371,999999367,999999359,999999353,999999347,999999341,999999337,999999331,999999323,999999317,999999311,999999307,999999301,999999293,999999289,999999283,999999277,999999271,999999263,999999259,999999253,999999247,999999241,999999239,999999233,999999229,999999223,999999217,999999211,999999209,999999203,999999199,999999197,999999191,999999187,999999181,999999179,999999173,999999169]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 and large numbers to test O(n log n * k) sorting with custom comparator within 2 seconds.

💡 Sorting with a custom comparator is O(n log n * k), where k is max digit length.

💡 Avoid brute force permutations which are O(n!).

💡 Use efficient string concatenation comparison and built-in sort.

Why it failed: TLE due to brute force or inefficient sorting. Fix by implementing custom comparator and using efficient sort (O(n log n * k)).

✓ Efficient sorting with custom comparator passes performance test.

Practice

1. Consider the following code snippet for the Jump Game problem. What is the value of maxReach after the third iteration (i = 2) when the input is [2, 3, 1, 1, 4]?

def canJump(nums):
    maxReach = 0
    for i, jump in enumerate(nums):
        if i > maxReach:
            return False
        maxReach = max(maxReach, i + jump)
        if maxReach >= len(nums) - 1:
            return True
    return False

easy

A. 3

B. 4

C. 5

D. 2

Solution

1. Step 1: Trace maxReach updates for each iteration

   i=0: maxReach = max(0, 0+2) = 2 i=1: maxReach = max(2, 1+3) = 4 i=2: maxReach = max(4, 2+1) = 4

2. Step 2: Identify maxReach after i=2

   After third iteration (i=2), maxReach remains 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   maxReach does not decrease; it stays at 4 after i=2 [OK]

Hint: maxReach never decreases, track max(i+jump) [OK]

Common Mistakes:

• Off-by-one in iteration count
• Confusing maxReach update with i only

2. Given the following code and input, what is the final output printed?

def maximumUnits(boxTypes, truckSize):
    boxTypes.sort(key=lambda x: x[1], reverse=True)
    totalUnits = 0
    for boxes, units in boxTypes:
        if truckSize == 0:
            break
        take = min(boxes, truckSize)
        totalUnits += take * units
        truckSize -= take
    return totalUnits

boxTypes = [[1,3],[2,2],[3,1]]
truckSize = 4
print(maximumUnits(boxTypes, truckSize))

easy

A. 7

B. 8

C. 9

D. 6

Solution

1. Step 1: Sort boxTypes by units descending

   Sorted list: [[1,3],[2,2],[3,1]] (already sorted)

2. Step 2: Iterate and pick boxes until truckSize=0

   Take 1 box with 3 units -> totalUnits=3, truckSize=3 left; take 2 boxes with 2 units -> totalUnits=3+4=7, truckSize=1 left; take 1 box with 1 unit -> totalUnits=7+1=8, truckSize=0 stop.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum matches manual calculation [OK]

Hint: Sort by units descending and pick greedily [OK]

Common Mistakes:

• Off-by-one in take calculation
• Not stopping when truckSize=0
• Incorrect sorting order

3. You are given a list of sticks with different lengths. You want to connect all sticks into one by repeatedly merging any two sticks, paying a cost equal to the sum of their lengths each time. Which algorithmic approach guarantees the minimum total cost to connect all sticks?

easy

A. Dynamic Programming that tries all possible merge sequences to find the minimum cost

B. Greedy algorithm using a min-heap to always merge the two shortest sticks first

C. Sorting the sticks once and merging them in sorted order from smallest to largest

D. Greedy algorithm that merges the two longest sticks first to reduce future costs

Solution

1. Step 1: Understand the problem goal

   The goal is to minimize the total cost of merging sticks, where each merge cost equals the sum of the two sticks merged.

2. Step 2: Identify the optimal strategy

   Merging the two shortest sticks first at each step minimizes incremental cost and leads to the global minimum total cost. This is efficiently done using a min-heap.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Min-heap merges shortest sticks first -> minimal total cost [OK]

Hint: Always merge shortest sticks first for minimal cost [OK]

Common Mistakes:

• Merging longest sticks first thinking it reduces future costs
• Sorting once and merging in order without reordering after merges
• Assuming brute force is needed for minimal cost

4. What is the time complexity of the peak-valley approach for the Best Time to Buy and Sell Stock II problem, and why might some candidates incorrectly think it is higher?

medium

A. O(1) since only constant extra space is used

B. O(n^2) because of nested while loops

C. O(n log n) due to sorting or searching steps

D. O(n) because each element is visited at most twice in the loops

Solution

1. Step 1: Identify loop behavior

   Though there are nested while loops, the index i only moves forward and never revisits elements.

2. Step 2: Conclude time complexity

   Each element is processed at most twice, so total time is linear O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Index i increments monotonically through array [OK]

Hint: Index i only moves forward, no repeated visits [OK]

Common Mistakes:

• Assuming nested loops multiply to O(n^2)
• Confusing space complexity with time complexity
• Thinking sorting is involved

5. Suppose the problem is modified: instead of finding the largest monotone increasing digits number ≤ n, you want the largest monotone increasing digits number ≤ n that can reuse digits any number of times (digits can be repeated arbitrarily). Which approach correctly adapts the algorithm?

hard

A. Use the original greedy algorithm but allow digits after marker to be any digit less than or equal to the digit at marker-1

B. Sort the digits of n and build the largest monotone number by repeating the smallest digit as many times as needed

C. Use a backtracking approach to generate all monotone numbers with digits ≤ those in n, allowing reuse, and pick the largest ≤ n

D. Modify the greedy algorithm to decrement digits and set trailing digits to the digit at marker-1 instead of 9

Solution

1. Step 1: Understand digit reuse changes problem nature

   Allowing reuse means digits can be repeated arbitrarily, so greedy digit decrement and trailing 9 assignment no longer guarantee largest monotone number ≤ n.

2. Step 2: Backtracking enumerates all monotone numbers with digit reuse

   Backtracking can generate all monotone numbers with digits ≤ those in n, allowing reuse, then pick the largest ≤ n.

3. Step 3: Other options fail to handle reuse or produce incorrect numbers

   Sorting digits or modifying trailing digits to marker-1 digit does not guarantee largest monotone number with reuse.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Backtracking correctly handles reuse and monotonicity constraints [OK]

Hint: Digit reuse breaks greedy; backtracking needed for correctness [OK]

Common Mistakes:

• Trying to adapt greedy without full enumeration
• Assuming trailing digits can be set to 9 or marker digit
• Ignoring exponential complexity of reuse