Largest Number (Arrange to Form Biggest)

▶

Steps

setup

Convert numbers to strings

The input list of integers [3, 30, 34, 5, 9] is converted to strings ['3', '30', '34', '5', '9'] to enable concatenation comparisons.

💡 Converting to strings allows the algorithm to compare concatenated pairs like '9' + '5' vs '5' + '9' to decide order.

Line:

nums_str = list(map(str, nums))

💡 This step sets up the data type needed for the custom sorting logic.

compare

Start sorting: compare '30' and '3'

The sorting algorithm compares '30' (index 1) and '3' (index 0) by concatenating '303' and '330' to decide order.

💡 Comparing concatenations determines which string should come first to maximize the final number.

Line:

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

💡 The comparator orders '3' before '30' because '330' is larger than '303'.

swap

Swap '30' and '3' to order correctly

Because '3' should come before '30', the two elements are swapped to ['3', '30', '34', '5', '9'].

💡 Swapping enforces the order decided by the comparator to build the largest number.

Line:

nums_str.sort(key=cmp_to_key(compare))

💡 Swapping ensures the array moves closer to the correct sorted order.

compare

Compare '34' and '30'

Next, compare '34' (index 2) and '30' (index 1) by concatenating '3430' and '3034'.

💡 This comparison checks if '34' should come before '30' to maximize the number.

Line:

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

💡 The comparator places '34' before '30' because '3430' is larger.

swap

Swap '34' and '30' to correct order

Swap '34' and '30' to place '34' before '30', resulting in ['3', '34', '30', '5', '9'].

💡 Swapping enforces the comparator's order to maximize the final number.

Line:

nums_str.sort(key=cmp_to_key(compare))

💡 The array is progressively sorted by swapping elements based on concatenation comparison.

compare

Compare '5' and '30'

Compare '5' (index 3) and '30' (index 2) by concatenating '530' and '305'.

💡 This comparison decides if '5' should come before '30' to maximize the number.

Line:

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

💡 The comparator places '5' before '30' because '530' is larger.

swap

Swap '5' and '30' to correct order

Swap '5' and '30' to place '5' before '30', resulting in ['3', '34', '5', '30', '9'].

💡 Swapping enforces the comparator's order to maximize the final number.

Line:

nums_str.sort(key=cmp_to_key(compare))

💡 The array is progressively sorted by swapping elements based on concatenation comparison.

compare

Compare '9' and '30'

Compare '9' (index 4) and '30' (index 3) by concatenating '930' and '309'.

💡 This comparison decides if '9' should come before '30' to maximize the number.

Line:

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

💡 The comparator places '9' before '30' because '930' is larger.

swap

Swap '9' and '30' to correct order

Swap '9' and '30' to place '9' before '30', resulting in ['3', '34', '5', '9', '30'].

💡 Swapping enforces the comparator's order to maximize the final number.

Line:

nums_str.sort(key=cmp_to_key(compare))

💡 The array is progressively sorted by swapping elements based on concatenation comparison.

compare

Compare '9' and '5'

Compare '9' (index 3) and '5' (index 2) by concatenating '95' and '59' to decide order.

💡 This comparison checks if '9' should come before '5' to maximize the number.

Line:

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

💡 The comparator places '9' before '5' because '95' is larger.

swap

Swap '9' and '5' to correct order

Swap '9' and '5' to place '9' before '5', resulting in ['3', '34', '9', '5', '30'].

💡 Swapping enforces the comparator's order to maximize the final number.

Line:

nums_str.sort(key=cmp_to_key(compare))

💡 The array is progressively sorted by swapping elements based on concatenation comparison.

compare

Compare '9' and '34'

Compare '9' (index 2) and '34' (index 1) by concatenating '934' and '349' to decide order.

💡 This comparison checks if '9' should come before '34' to maximize the number.

Line:

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

💡 The comparator places '9' before '34' because '934' is larger.

swap

Swap '9' and '34' to correct order

Swap '9' and '34' to place '9' before '34', resulting in ['3', '9', '34', '5', '30'].

💡 Swapping enforces the comparator's order to maximize the final number.

Line:

nums_str.sort(key=cmp_to_key(compare))

💡 The array is progressively sorted by swapping elements based on concatenation comparison.

compare

Compare '9' and '3'

Compare '9' (index 1) and '3' (index 0) by concatenating '93' and '39' to decide order.

💡 This comparison checks if '9' should come before '3' to maximize the number.

Line:

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

💡 The comparator places '9' before '3' because '93' is larger.

swap

Swap '9' and '3' to correct order

Swap '9' and '3' to place '9' before '3', resulting in ['9', '3', '34', '5', '30'].

💡 Swapping enforces the comparator's order to maximize the final number.

Line:

nums_str.sort(key=cmp_to_key(compare))

💡 The array is progressively sorted by swapping elements based on concatenation comparison.

compare

Compare '5' and '34'

Compare '5' (index 3) and '34' (index 2) by concatenating '534' and '345' to decide order.

💡 This comparison checks if '5' should come before '34' to maximize the number.

Line:

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

💡 The comparator places '5' before '34' because '534' is larger.

swap

Swap '5' and '34' to correct order

Swap '5' and '34' to place '5' before '34', resulting in ['9', '3', '5', '34', '30'].

💡 Swapping enforces the comparator's order to maximize the final number.

Line:

nums_str.sort(key=cmp_to_key(compare))

💡 The array is progressively sorted by swapping elements based on concatenation comparison.

prune

Check if first string is '0'

After sorting, check if the first element is '0'. If yes, return '0' immediately to handle edge case of all zeros.

💡 This step handles the edge case where all numbers are zero, avoiding leading zeros in output.

Line:

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

💡 No early return needed since the largest number is not zero.

reconstruct

Concatenate all strings to form largest number

Join all strings in the sorted array ['9', '3', '5', '34', '30'] to form the final largest number '9534330'.

💡 Concatenation of the sorted strings produces the maximum possible number.

Line:

return ''.join(nums_str)

💡 The final answer is constructed by joining the sorted strings.

def largestNumber(nums):  # STEP 1
    from functools import cmp_to_key
    nums_str = list(map(str, nums))  # STEP 1
    def compare(a, b):  # STEP 2 onwards
        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))  # STEPS 2-17
    if nums_str[0] == '0':  # STEP 18
        return '0'
    return ''.join(nums_str)  # STEP 19

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

📊

Largest Number (Arrange to Form Biggest) - Watch the Algorithm Execute, Step by Step

Watching each comparison and swap in the sorting process reveals why the custom comparator works and how the final largest number is constructed.

setup

3

0

30

1

34

2

5

3

9

4

compare

right

3

0

left

30

1

34

2

5

3

9

4

swap

left

3

0

right

30

1

34

2

5

3

9

4

compare

3

0

right

30

1

left

34

2

5

3

9

4

swap

3

0

left

34

1

right

30

2

5

3

9

4

compare

3

0

34

1

right

30

2

left

5

3

9

4

swap

3

0

34

1

left

5

2

right

30

3

9

4

compare

3

0

34

1

5

2

right

30

3

left

9

4

swap

3

0

34

1

5

2

left

9

3

right

30

4

compare

3

0

34

1

right

5

2

left

9

3

30

4

swap

3

0

34

1

left

9

2

right

5

3

30

4

compare

3

0

right

34

1

left

9

2

5

3

30

4

swap

3

0

left

9

1

right

34

2

5

3

30

4

compare

right

3

0

left

9

1

34

2

5

3

30

4

swap

left

9

0

right

3

1

34

2

5

3

30

4

compare

9

0

3

1

right

34

2

left

5

3

30

4

swap

9

0

3

1

left

5

2

right

34

3

30

4

prune

i

9

0

3

1

5

2

34

3

30

4

record

9

0

3

1

5

2

34

3

30

4

Result: "9534330"

Key Takeaways

✓ The custom comparator compares concatenated pairs to decide order, not numeric value alone.

This insight is hard to see from code alone because it requires understanding why '9' + '5' > '5' + '9' means '9' should come first.

✓ Sorting with this comparator rearranges the array step-by-step by swapping elements based on concatenation comparisons.

Visualizing each comparison and swap clarifies how the greedy approach builds the largest number incrementally.

✓ The early check for the first element being '0' handles the edge case of all zeros efficiently.

Without this, the output could incorrectly have leading zeros; the trace shows this check explicitly.

Practice

1. You are given a sequence of integers and need to find the length of the longest subsequence where the differences between successive elements strictly alternate between positive and negative. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Dynamic Programming with a 2D table tracking subsequence lengths for each index and difference sign

B. Brute force recursion exploring all subsequences and checking alternating differences

C. Greedy approach tracking the direction of the last difference and counting peaks and valleys

D. Sliding window approach maintaining a contiguous alternating difference substring

Solution

1. Step 1: Understand problem constraints

   The problem requires the longest subsequence with alternating positive and negative differences, not necessarily contiguous.

2. Step 2: Identify optimal approach

   Dynamic programming is possible but less efficient; brute force is exponential; sliding window fails because subsequence need not be contiguous. The greedy approach tracking last difference direction and counting peaks and valleys achieves O(n) time and O(1) space optimally.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Greedy with direction tracking matches problem requirements [OK]

Hint: Longest alternating difference subsequence -> greedy direction tracking

Common Mistakes:

• Confusing subsequence with substring
• Assuming DP is always needed
• Trying brute force without pruning

2. Consider the following buggy code for the Gas Station problem. Which line contains the subtle bug that can cause incorrect results?

def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    # Bug: missing total gas check
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i+1] = prefix[i] + net[i % n]
    for i in range(n):
        if prefix[i+n] - prefix[i] >= 0:
            return i
    return -1

medium

A. Line 3: net array computation

B. Line 4: missing total gas vs total cost check

C. Line 6: prefix sums computation loop

D. Line 8: checking prefix sums for valid start

Solution

1. Step 1: Identify missing total gas check

   The code does not check if sum(net) < 0 before proceeding, which can cause incorrect start index or false positives.

2. Step 2: Verify other lines

   Net array, prefix sums, and prefix difference checks are correct and standard.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing total gas check leads to incorrect results [OK]

Hint: Always check total gas >= total cost before searching start [OK]

Common Mistakes:

• Forgetting total gas check
• Misusing modulo in prefix sums
• Resetting start without resetting tank

3. The following code attempts to solve the Jump Game problem. Identify the line that contains a subtle bug that causes incorrect results on some inputs.

def canJump(nums):
    maxReach = 0
    for i, jump in enumerate(nums):
        # Bug: missing check if current index is beyond maxReach
        maxReach = max(maxReach, i + jump)
        if maxReach >= len(nums) - 1:
            return True
    return False

medium

A. Line 2: Initialization of maxReach

B. Line 3: for loop header enumerating nums

C. Line 4: Missing check if i > maxReach before updating maxReach

D. Line 6: Checking if maxReach reaches or exceeds last index

Solution

1. Step 1: Understand the missing condition

   The code does not check if the current index i is beyond maxReach, which means it may continue even when stuck.

2. Step 2: Identify the bug line

   Line 4 updates maxReach without verifying if i is reachable, causing false positives on inputs with unreachable indices.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding "if i > maxReach: return False" fixes the bug [OK]

Hint: Check if current index is reachable before updating maxReach [OK]

Common Mistakes:

• Forgetting to check i > maxReach
• Assuming maxReach update alone suffices

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

5. What is the time complexity of the optimal greedy algorithm that finds the largest monotone increasing digits number less than or equal to n, where d is the number of digits in n?

medium

A. O(d), since it scans digits once from right to left and then sets trailing digits

B. O(log n), since the number of digits d is proportional to log n

C. O(d^2), because each decrement may cause re-checking previous digits multiple times

D. O(n * d), where n is the input number and d is the number of digits

Solution

1. Step 1: Understand the relationship between digits and input size

   The number of digits d in n is proportional to log₁₀ n.

2. Step 2: Express complexity in terms of n

   The algorithm runs in O(d) time, which is O(log n) when expressed in terms of n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Expressing complexity in terms of n, O(log n) is correct and more standard [OK]

Hint: Algorithm runs in linear time relative to digit count, which is logarithmic in n [OK]

Common Mistakes:

• Confusing input size n with digit count d
• Assuming repeated decrements cause quadratic time
• Ignoring that digit count is log n