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. You are given a string and need to partition it into as many parts as possible so that each letter appears in at most one part. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm using last occurrence indices to determine partition boundaries

B. Backtracking to try all possible partitions and select the best

C. Sliding window technique to find maximum substring without repeating characters

D. Dynamic Programming with memoization to find all valid partitions

Solution

1. Step 1: Understand problem constraints

   The problem requires partitions where no character appears in more than one part, so we must know the last occurrence of each character.

2. Step 2: Identify approach that uses last occurrence

   The greedy approach that tracks last occurrence indices and extends partitions accordingly guarantees optimal partitions without overlap.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy with last occurrence indices ensures minimal partitions covering all characters [OK]

Hint: Use last occurrence map to greedily partition [OK]

Common Mistakes:

• Assuming DP is needed for optimal partitions
• Using sliding window for unique substrings instead
• Trying backtracking which is inefficient here

2. What is the time complexity of the optimal two-pass greedy candy distribution algorithm for an input array of length n?

medium

A. O(n) because each pass scans the array once

B. O(n^2) due to nested loops in adjustment

C. O(n log n) due to sorting or priority queue usage

D. O(n) but with O(n) auxiliary space for candies array

Solution

1. Step 1: Identify loops in the algorithm

   Two separate passes over the array, each iterating from start to end or end to start once.

2. Step 2: Analyze complexity of each pass

   Each pass is O(n), no nested loops or sorting involved, so total time is O(n). Also, the candies array requires O(n) auxiliary space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two linear scans and O(n) space for candies array [OK]

Hint: Two linear passes -> O(n) time and O(n) space [OK]

Common Mistakes:

• Confusing repeated adjustment brute force with optimal approach
• Assuming sorting is needed
• Ignoring that passes are sequential, not nested

3. Identify the bug in the following code snippet for the Minimum Domino Rotations problem:

def minDominoRotations(A, B):
    def check(x):
        rotations_a = rotations_b = 0
        for i in range(len(A)):
            if A[i] != x and B[i] != x:
                return 0  # Bug here
            elif A[i] != x:
                rotations_a += 1
            elif B[i] != x:
                rotations_b += 1
        return min(rotations_a, rotations_b)

    rotations = check(A[0])
    if rotations != -1:
        return rotations
    else:
        return check(B[0])

medium

A. Incorrect initialization of rotations_a and rotations_b

B. Not incrementing rotations when both sides equal x

C. Returning rotations without checking both candidates

D. The return value 0 instead of -1 when no domino can be rotated to x

Solution

1. Step 1: Analyze early return condition

   If neither side matches candidate x, the function should return -1 to indicate failure, not 0.

2. Step 2: Impact of returning 0

   Returning 0 falsely indicates zero rotations needed, causing incorrect positive results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Returning -1 signals no solution; 0 misleads caller [OK]

Hint: Return -1 on failure, not 0 [OK]

Common Mistakes:

• Returning 0 instead of -1 on failure
• Overcounting rotations when both sides equal candidate

4. Suppose the problem is modified so that you can buy and sell the same stock multiple times on the same day (i.e., unlimited transactions including multiple buys and sells per day). Which of the following algorithmic changes correctly adapts the solution?

hard

A. Add all positive differences between consecutive prices and also consider zero differences as profitable

B. Sum all positive differences between consecutive days as before, no change needed

C. Use a dynamic programming approach to consider multiple transactions per day explicitly

D. Modify the code to add all positive differences between consecutive prices including zero differences

Solution

1. Step 1: Understand the new constraint

   Allowing multiple transactions per day does not change the fact that profit comes from positive price differences.

2. Step 2: Check if algorithm needs change

   Summing all positive consecutive differences already accounts for all profitable transactions, including multiple per day.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Algorithm already sums all positive increments, no modification needed [OK]

Hint: Unlimited transactions per day still sum positive differences [OK]

Common Mistakes:

• Adding zero or negative differences incorrectly
• Overcomplicating with DP when greedy suffices
• Thinking multiple transactions per day require new logic

5. Suppose the wiggle subsequence problem is modified so that elements can be reused multiple times in the subsequence (i.e., repeated picks allowed). Which of the following statements about adapting the optimal greedy algorithm is correct?

hard

A. A modified greedy approach can work by allowing zero differences and counting repeated elements

B. The original greedy algorithm works without changes because reuse does not affect difference signs

C. Reuse breaks the problem definition, so no efficient algorithm exists

D. The algorithm must be changed to a dynamic programming approach to handle reuse correctly

Solution

1. Step 1: Understand reuse impact

   Allowing reuse means subsequence elements can repeat, changing the problem fundamentally and invalidating the original greedy assumptions.

2. Step 2: Identify correct adaptation

   Greedy approach relies on strictly alternating differences without reuse; to handle reuse, a dynamic programming approach that tracks states and counts is needed.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Reuse requires more complex state tracking than greedy allows [OK]

Hint: Reuse breaks greedy assumptions; DP needed

Common Mistakes:

• Assuming greedy still works
• Thinking reuse is trivial
• Ignoring problem definition changes