Largest Number (Custom Comparator Sort)

📋

Problem

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

Given a list of non-negative integers, arrange them such that they form the largest number and return it as a string. The result may be very large, so return a string instead of an integer.

1 ≤ n ≤ 10^50 ≤ nums[i] ≤ 10^9The result may contain leading zeros only if the entire number is zero

Edge cases: All zeros → output should be '0'Single element array → output is that element as stringNumbers with same prefix → ensure correct order by concatenation

</>

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: 102Sorting numbers in ascending or descending numeric order instead of using concatenation comparator.✅ Implement comparator that compares 'xy' and 'yx' as strings and sorts accordingly.

Wrong: 000Not handling all zero inputs by returning multiple zeros instead of single '0'.✅ After sorting, check if the first character is '0' and return '0' instead.

Wrong: 12112Incorrect ordering of numbers with same prefix by numeric or lex order instead of concatenation comparison.✅ Compare concatenations 'xy' and 'yx' as strings to decide order.

Wrong: 8308308Sorting shorter prefix before longer prefix incorrectly in prefix edge cases.✅ Use concatenation comparator comparing 'xy' and 'yx' strings.

Wrong: 91990Greedy approach sorting by first digit only, ignoring full concatenation comparison.✅ Use comparator comparing full concatenations 'xy' and 'yx'.

✓

Test Cases

Try testing your solution on empty and single-element inputs to ensure base cases are handled.

Focus on tricky cases where numbers share prefixes or greedy sorting fails.

Optimize your solution to use sorting with a custom comparator instead of brute force permutations.

t1_01basic

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

Expected"210"

⏱ Performance - must finish in 2000ms

Concatenating '2' + '10' = '210' is larger than '10' + '2' = '102', so '2' should come before '10'.

💡 Think about how to compare two numbers by concatenating them in different orders.

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

💡 Sort the numbers as strings using the comparator: if xy > yx, x should come before y.

Why it failed: Failed to use correct custom comparator: output is lex order or numeric order instead of concatenation order. Fix by comparing concatenations 'xy' and 'yx' as strings.

✓ Correctly implements custom comparator and concatenation logic.

t1_02basic

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

Expected"9534330"

⏱ Performance - must finish in 2000ms

Ordering as '9', '5', '34', '3', '30' forms the largest number '9534330'.

💡 Check how to order numbers with different digit lengths using concatenation comparison.

💡 Remember to convert numbers to strings before comparing concatenations.

💡 Sort with comparator: for x,y compare xy and yx strings to decide order.

Why it failed: Incorrect order due to numeric or lexicographic sort instead of concatenation comparison. Fix by implementing comparator that compares 'xy' and 'yx'.

✓ Correctly sorts all numbers to form the largest concatenated number.

t2_01edge

Input{"nums":[]}

Expected""

⏱ Performance - must finish in 2000ms

Empty input array should return empty string as no numbers to concatenate.

💡 Consider what to return when input list is empty.

💡 Check if your code handles empty input without errors.

💡 Return empty string if nums is empty.

Why it failed: Code crashes or returns non-empty output on empty input. Fix by adding check for empty input and return empty string.

✓ 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 array has only one element.

💡 Ensure single number is converted to string and returned.

💡 Return str(nums[0]) if length is 1.

Why it failed: Fails to convert single element to string or returns wrong output. Fix by returning str(nums[0]) for single element input.

✓ 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 multiple zeros concatenated.

💡 Check if all numbers are zero after sorting.

💡 Avoid returning multiple leading zeros.

💡 Return '0' if the first character of concatenated result is '0'.

Why it failed: Returns '000' or multiple zeros instead of '0'. Fix by checking if result starts with '0' and return '0' instead.

✓ Correctly returns '0' for all zero inputs.

t3_01corner

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

Expected"12121"

⏱ Performance - must finish in 2000ms

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

💡 Beware of numbers with same prefix causing wrong order.

💡 Compare concatenations 'xy' and 'yx' carefully for prefix cases.

💡 Ensure comparator returns correct order for '121' and '12' by comparing '12112' vs '12121'.

Why it failed: Incorrect order due to naive prefix comparison or numeric comparison. Fix by comparing full concatenations 'xy' and 'yx' as strings.

✓ Correctly orders numbers with same prefix using concatenation comparator.

t3_02corner

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

Expected"8308830"

⏱ Performance - must finish in 2000ms

Comparing '8308830' and '8308308', '8308830' is larger, so '8308' should come before '830'.

💡 Test cases where one number is prefix of another but longer number should come first.

💡 Use concatenation comparison to decide order.

💡 Compare '8308'+'830' and '830'+'8308' to determine correct order.

Why it failed: Fails prefix edge case by sorting shorter prefix first. Fix by comparing concatenations 'xy' and 'yx' as strings.

✓ Handles prefix edge cases correctly with custom comparator.

t3_03corner

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

Expected"99190"

⏱ Performance - must finish in 2000ms

Ordering '9', '91', '90' forms '99190' which is largest possible.

💡 Beware of greedy approach that sorts by first digit only.

💡 Use full concatenation comparison to order numbers correctly.

💡 Compare pairs like '9'+'91' vs '91'+'9' to decide order.

Why it failed: Greedy approach sorting by first digit fails here. Fix by using comparator comparing 'xy' and 'yx' concatenations.

✓ Correctly orders numbers avoiding greedy trap.

t4_01performance

Input{"nums":[999999937,999999929,999999893,999999883,999999877,999999863,999999857,999999853,999999841,999999839,999999833,999999823,999999811,999999809,999999797,999999787,999999773,999999763,999999757,999999749,999999743,999999733,999999727,999999719,999999713,999999701,999999697,999999689,999999683,999999677,999999671,999999667,999999659,999999653,999999647,999999643,999999631,999999629,999999613,999999607,999999599,999999593,999999587,999999577,999999571,999999563,999999557,999999551,999999547,999999541,999999533,999999523,999999517,999999511,999999509,999999503,999999499,999999491,999999487,999999479,999999473,999999467,999999461,999999457,999999449,999999443,999999439,999999433,999999427,999999421,999999419,999999413,999999409,999999401,999999397,999999389,999999383,999999379,999999373,999999367,999999359,999999353,999999349,999999341,999999337,999999331,999999323,999999317,999999311,999999307,999999301,999999293,999999289,999999283,999999277,999999271,999999269,999999263,999999259,999999253]}

Expectednull

⏱ Performance - must finish in 2000ms

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

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

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

💡 Use efficient string concatenation and comparator to pass performance.

Why it failed: Brute force or naive approach causes TLE due to factorial complexity. Fix by implementing custom comparator sort with O(n log n * k) complexity.

✓ Efficient sorting with custom comparator passes performance constraints.

Practice

1. Consider the following Python function that finds the minimum time difference between time points. What is the returned value when the input is ["01:01", "02:01", "01:02"]?

def findMinDifference(timePoints):
    seen = [False] * 1440
    for t in timePoints:
        h, m = map(int, t.split(':'))
        total = h * 60 + m
        if seen[total]:
            return 0
        seen[total] = True
    prev = -1
    first = -1
    min_diff = 1440
    for i in range(1440):
        if seen[i]:
            if prev != -1:
                min_diff = min(min_diff, i - prev)
            else:
                first = i
            prev = i
    min_diff = min(min_diff, 1440 - prev + first)
    return min_diff

easy

A. 59

B. 0

C. 60

D. 1

Solution

1. Step 1: Convert times to minutes and mark seen

   "01:01" -> 61, "02:01" -> 121, "01:02" -> 62; all unique, so no early return 0.

2. Step 2: Iterate over seen array to find minimum adjacent difference

   Adjacent times are 61 and 62 (diff 1), 62 and 121 (diff 59). Minimum difference is 1.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Minimum adjacent difference found is 1 minute [OK]

Hint: Check adjacent differences after sorting times [OK]

Common Mistakes:

• Confusing difference between 61 and 121 as minimum
• Forgetting to check circular difference
• Returning 0 incorrectly when no duplicates

2. What is the time complexity of the optimal h-index algorithm that sorts the citations and uses binary search on possible h values, assuming n is the number of papers?

medium

A. O(n log n) dominated by sorting; counting inside binary search is O(n) per iteration but binary search runs O(log n) times

B. O(n log n) due to sorting plus O(log n) binary search with O(n) counting each iteration

C. O(n²) because binary search calls a linear count each time

D. O(n) because binary search reduces search space quickly

Solution

1. Step 1: Analyze sorting step

   Sorting citations takes O(n log n).

2. Step 2: Analyze binary search and counting

   Binary search runs O(log n) times; each iteration counts papers ≥ mid in O(n). Total counting cost is O(n log n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting plus binary search counting yields O(n log n) [OK]

Hint: Sorting dominates; counting inside binary search multiplies log n [OK]

Common Mistakes:

• Thinking counting is O(1)
• Confusing total binary search cost
• Assuming linear time overall

3. The following code attempts to sort a matrix diagonally using min-heaps keyed by (row - col). Identify the line containing the subtle bug that causes incorrect sorting or corrupted output.

from typing import List
import collections
import heapq

def diagonalSort(mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    diagonals = collections.defaultdict(list)
    for i in range(m):
        for j in range(n):
            heapq.heappush(diagonals[i + j], mat[i][j])  # Line X
    for i in range(m):
        for j in range(n):
            mat[i][j] = heapq.heappop(diagonals[i - j])  # Line Y
    return mat

medium

A. Line X: Using i + j as diagonal key instead of i - j.

B. Line Y: Popping from diagonals keyed by i - j instead of i + j.

C. Line X: Using heapq.heappush instead of sorting the diagonal list first.

D. Line Y: Assigning popped element directly without checking if heap is empty.

Solution

1. Step 1: Check diagonal key consistency

   The diagonal key must be consistent for both pushing and popping. Here, push uses i + j, pop uses i - j, causing mismatch.

2. Step 2: Identify impact of key mismatch

   Elements pushed into one diagonal heap are popped from a different key, leading to empty heaps or incorrect elements assigned.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Diagonal keys must match exactly for correct sorting [OK]

Hint: Diagonal key must be consistent for push and pop [OK]

Common Mistakes:

• Mixing i + j and i - j keys
• Forgetting to check heap emptiness
• Using reverse sorting but popping incorrectly

4. What is the time complexity of the optimal wiggle sort algorithm that uses sorting, median finding, and in-place three-way partitioning with virtual indexing on an input array of length n?

medium

A. O(n log n) because median finding requires sorting and partitioning is linear

B. O(n) because partitioning and virtual indexing are linear time operations

C. O(n^2) because of repeated swaps during three-way partitioning

D. O(n log n) due to the initial sorting step dominating the runtime

Solution

1. Step 1: Identify the dominant operation

   The algorithm first sorts the array, which takes O(n log n) time.

2. Step 2: Analyze partitioning and median finding

   Median is found by indexing the sorted array (O(1)), and three-way partitioning with virtual indexing runs in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates, so overall complexity is O(n log n) [OK]

Hint: Sorting dominates time complexity despite linear partitioning [OK]

Common Mistakes:

• Assuming median finding is O(n) without sorting
• Confusing partitioning swaps as quadratic
• Ignoring sorting step's cost

5. Suppose the problem is modified so that elements can be reused unlimited times to form an infinitely long array with no two adjacent elements equal. Which modification to the heap-based algorithm correctly handles this variant?

hard

A. Remove the max frequency check and keep pushing elements back with updated counts indefinitely.

B. Use a queue instead of a heap to cycle through elements ensuring no two adjacent are equal.

C. Use a max heap but reset counts to original frequencies after each full pass through the heap.

D. Modify the algorithm to never decrement counts and always push elements back to allow infinite reuse.

Solution

1. Step 1: Understand infinite reuse implication

   Since elements can be reused unlimited times, counts do not decrease; the algorithm must allow repeated placement without decrementing counts.

2. Step 2: Modify heap usage accordingly

   Never decrement counts and always push elements back to heap to maintain availability, ensuring no two adjacent elements are equal.

3. Step 3: Evaluate other options

   Removing max frequency check or resetting counts breaks correctness or efficiency; queue does not prioritize frequency.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Maintaining counts without decrement allows infinite reuse without adjacency violation [OK]

Hint: Infinite reuse means counts stay constant [OK]

Common Mistakes:

• Removing checks without adjusting counts
• Resetting counts causing incorrect order