Largest Number (Custom Comparator Sort)

▶

Steps

setup

Convert numbers to strings

The input array [10, 2] is converted to strings ['10', '2'] to prepare for custom string comparison.

💡 Sorting requires string concatenation comparisons, so converting numbers to strings is essential.

Line:

nums_str = list(map(str, nums))

💡 The problem is transformed into sorting strings, not numbers.

compare

Start first comparison in sort

The sort algorithm begins comparing the first two elements '10' and '2' using the custom comparator.

💡 The comparator decides order by comparing concatenations '10'+'2' and '2'+'10'.

Line:

def compare(a, b):
    return -1 if a + b > b + a else 1 if a + b < b + a else 0

💡 The comparator function is the core of the custom sort order.

compare

Compare concatenations '10'+'2' vs '2'+'10'

Compare '102' (a+b) with '210' (b+a) to decide which string should come first.

💡 The larger concatenation determines the order to maximize the final number.

Line:

return -1 if a + b > b + a else 1 if a + b < b + a else 0

💡 Ordering by concatenation ensures the largest combined number.

swap

Swap elements based on comparator result

Since '2' should come before '10', the elements at indices 0 and 1 are swapped.

💡 Swapping reorders the array to reflect the custom comparator's decision.

Line:

nums_str.sort(key=cmp_to_key(compare))

💡 Sorting rearranges elements to maximize the concatenated number.

compare

Sorting complete - check for leading zero

Check if the first element is '0' to handle the edge case where all numbers are zero.

💡 If the largest number is '0', the entire number is zero.

Line:

if nums_str[0] == '0':
    return '0'

💡 This check prevents returning numbers like '000'.

reconstruct

Concatenate all strings to form result

Join the sorted strings ['2', '10'] to form the final largest number '210'.

💡 Concatenation of sorted strings produces the answer.

Line:

return ''.join(nums_str)

💡 The final string is the largest number possible from the input.

reconstruct

Final answer ready

The final answer '210' is returned as the largest number formed by the input array.

💡 This confirms the correctness of the custom sorting approach.

Line:

return ''.join(nums_str)

💡 The problem is solved by sorting with the custom comparator and concatenating.

setup

Edge case example: all zeros input

For input [0, 0, 0], convert to strings ['0', '0', '0'] to prepare for sorting.

💡 This edge case tests the early exit condition after sorting.

Line:

nums_str = list(map(str, nums))

💡 Even with multiple zeros, the algorithm handles correctly.

compare

Check first element after sorting zeros

After sorting, check if the first element is '0' to return '0' immediately.

💡 This prevents returning '000' instead of '0'.

Line:

if nums_str[0] == '0':
    return '0'

💡 Early exit optimizes for all-zero inputs.

reconstruct

Return '0' for all zeros input

Return the string '0' as the largest number for input [0, 0, 0].

💡 This is the correct output for all zero inputs.

Line:

return '0'

💡 The algorithm handles edge cases gracefully.

from functools import cmp_to_key

def largestNumber(nums):
    # STEP 1: Convert numbers to strings
    nums_str = list(map(str, nums))

    # STEP 2-3: Define comparator for sorting
    def compare(a, b):
        # STEP 3: Compare concatenations
        if a + b > b + a:
            return -1  # a should come before b
        elif a + b < b + a:
            return 1   # b should come before a
        else:
            return 0

    # STEP 4: Sort using custom comparator
    nums_str.sort(key=cmp_to_key(compare))

    # STEP 5: Check if first element is '0'
    if nums_str[0] == '0':
        return '0'

    # STEP 6-7: Concatenate and return result
    return ''.join(nums_str)

if __name__ == '__main__':
    print(largestNumber([10, 2]))  # Expected: '210'
    print(largestNumber([0, 0, 0]))  # Expected: '0'

📊

Largest Number (Custom Comparator Sort) - Watch the Algorithm Execute, Step by Step

Watching each comparison and pointer movement reveals how the custom sorting order is determined, which is hard to grasp from code alone.

setup

10

0

2

1

compare

i

10

0

j

2

1

compare

i

10

0

j

2

1

swap

2

0

10

1

compare

left

2

0

10

1

record

2

0

10

1

Result: "210"

record

2

0

10

1

Result: "210"

setup

0

0

0

1

0

2

compare

left

0

0

0

1

0

2

record

0

0

0

1

0

2

Result: "0"

Key Takeaways

✓ The custom comparator orders strings by comparing concatenated pairs to maximize the final number.

This insight is difficult to grasp from code alone because it involves understanding string concatenation ordering, which is non-intuitive.

✓ Sorting rearranges the array step-by-step based on pairwise comparisons, not numeric value alone.

Visualizing each comparison clarifies why '2' comes before '10' even though 10 > 2 numerically.

✓ The early exit for all-zero inputs prevents incorrect results like '000' and returns '0' immediately.

This edge case is easy to miss without seeing the check after sorting.

Practice

1. You are given an array containing only three distinct values representing colors: red, white, and blue. The goal is to sort the array so that all reds come first, followed by whites, then blues, in a single pass with constant extra space. Which algorithmic approach guarantees this optimal solution?

easy

A. Use a standard comparison-based sort like quicksort or mergesort to sort the array.

B. Use a three-pointer partitioning approach that rearranges elements in one pass, known as the Dutch National Flag algorithm.

C. Count the occurrences of each color and then overwrite the array in multiple passes.

D. Use dynamic programming to decide the position of each color based on previous states.

Solution

1. Step 1: Understand the problem constraints

   The problem requires sorting three distinct values in a single pass with O(1) extra space.

2. Step 2: Identify the algorithm that meets these constraints

   The Dutch National Flag algorithm uses three pointers to partition the array in one pass without extra space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   One-pass, constant space sorting of three distinct values matches Dutch National Flag algorithm [OK]

Hint: One-pass, three-pointer partitioning solves this optimally [OK]

Common Mistakes:

• Thinking counting sort is optimal despite multiple passes
• Assuming comparison-based sorts are needed
• Confusing DP with sorting problems

2. What is the time complexity of the optimal approach that sorts the array and scans adjacent pairs to find the minimum absolute difference?

medium

A. O(n) because scanning adjacent pairs is linear

B. O(n²) because every pair is compared

C. O(n log n) due to sorting, scanning is O(n)

D. O(log n) because sorting uses divide and conquer

Solution

1. Step 1: Identify sorting cost

   Sorting an array of size n takes O(n log n) time.

2. Step 2: Identify scanning cost

   Scanning adjacent pairs is a single pass O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting dominates total time -> O(n log n) [OK]

Hint: Sorting dominates; scanning is linear [OK]

Common Mistakes:

• Confusing scanning cost as sorting cost
• Assuming O(n) overall without sorting

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. 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

5. Suppose the input list nums can contain duplicate numbers and is not guaranteed to be sorted. Which modification to the optimal binary search approach is necessary to correctly find missing ranges?

hard

A. Modify binary search to skip duplicates by checking neighbors

B. Use a hash set to track presence and scan the entire range linearly

C. Apply binary search directly without changes since duplicates don't affect bisect

D. Sort the list and remove duplicates before applying binary search

Solution

1. Step 1: Understand binary search prerequisites

   Binary search requires a sorted list with unique elements to correctly locate insertion points and detect gaps.

2. Step 2: Preprocess input by sorting and removing duplicates

   Sorting ensures order; removing duplicates prevents incorrect gap detection caused by repeated numbers.

3. Step 3: Apply binary search on cleaned list

   After preprocessing, the existing binary search approach works correctly.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Sorting and deduplication are essential preprocessing steps [OK]

Hint: Binary search needs sorted unique data [OK]

Common Mistakes:

• Ignoring duplicates
• Assuming bisect handles duplicates correctly
• Switching to linear scan unnecessarily