Monotone Increasing Digits

▶

Steps

setup

Convert number to digit list

Convert the input number 332 into a list of digits [3, 3, 2] to allow easy manipulation.

💡 Working with digits as a list simplifies checking and modifying individual digits.

Line:

digits = list(map(int, str(n)))

💡 Digits are now accessible individually for comparisons and updates.

setup

Initialize marker to length of digits

Set marker to 3 (length of digits), indicating no adjustments needed yet.

💡 Marker will track where digits start to be set to 9 if a break is found.

Line:

marker = len(digits)

💡 Initially, assume the number is monotone increasing.

traverse

Start backward traversal from right

Set pointer i to index 2 (last digit) to begin checking digits from right to left.

💡 Checking from right to left helps find where monotone property breaks earliest.

Line:

for i in range(len(digits) - 1, 0, -1):

💡 We will compare digits[i] with digits[i-1] to detect breaks.

compare

Compare digits[2] and digits[1]

Compare digit 2 (value 2) with digit 1 (value 3). Since 2 < 3, monotone breaks here.

💡 Detecting where the digits decrease is key to fixing the number.

Line:

if digits[i] < digits[i - 1]:

💡 We must decrease digits[1] to restore monotonicity and mark position 2 for trailing 9s.

shrink

Decrement digit at i-1

Decrement digit at index 1 from 3 to 2 to fix monotone break.

💡 Decreasing this digit ensures the number becomes monotone increasing after adjustments.

Line:

digits[i - 1] -= 1

💡 Digit 1 is now 2, which may require further checks to maintain monotonicity.

traverse

Move i to 1 for next comparison

Move pointer i to index 1 to check if monotone property holds between digits[1] and digits[0].

💡 We must verify if the decrement caused a new monotone break earlier in the number.

Line:

for i in range(len(digits) - 1, 0, -1):

💡 Checking digits[1] and digits[0] to ensure monotonicity.

compare

Compare digits[1] and digits[0]

Compare digit 1 (2) with digit 0 (3). Since 2 < 3, monotone breaks again.

💡 We must fix this new break by decrementing digit 0 and updating marker.

Line:

if digits[i] < digits[i - 1]:

💡 Digit 0 must be decreased and marker updated to 1 to fix monotonicity.

shrink

Decrement digit at i-1

Decrement digit at index 0 from 3 to 2 to fix monotone break.

💡 Adjusting the leftmost digit ensures the entire number can be monotone increasing.

Line:

digits[i - 1] -= 1

💡 Digit 0 is now 2, which should be monotone with digit 1 (2).

traverse

End backward traversal

Traversal ends as i reaches 1; all monotone breaks detected and fixed.

💡 Now we will set all digits after marker to 9 to maximize the number.

Line:

for i in range(marker, len(digits)):
    digits[i] = 9

💡 Marker at 1 means digits from index 1 onward will be set to 9.

fill_cells

Set digits after marker to 9 (index 1)

Set digit at index 1 to 9 to maximize the number while maintaining monotonicity.

💡 Filling with 9s after the marker ensures the largest possible number less than original.

Line:

digits[i] = 9

💡 Digit 1 changed from 2 to 9.

fill_cells

Set digits after marker to 9 (index 2)

Set digit at index 2 to 9 to complete filling trailing digits with 9s.

💡 All digits after marker are now 9, finalizing the monotone number.

Line:

digits[i] = 9

💡 Digit 2 changed from 2 to 9.

reconstruct

Convert digit list back to integer

Join digits [2, 9, 9] into string '299' and convert to integer 299 as the final answer.

💡 Reconstruction returns the final monotone increasing number.

Line:

return int(''.join(map(str, digits)))

💡 The final monotone increasing number less than or equal to 332 is 299.

def monotoneIncreasingDigits(n: int) -> int:
    digits = list(map(int, str(n)))  # STEP 1
    marker = len(digits)             # STEP 2
    for i in range(len(digits) - 1, 0, -1):  # STEP 3,6,9
        if digits[i] < digits[i - 1]:        # STEP 4,7
            digits[i - 1] -= 1               # STEP 5,8
            marker = i                       # STEP 4,7
    for i in range(marker, len(digits)):     # STEP 10,11
        digits[i] = 9
    return int(''.join(map(str, digits)))    # STEP 12

if __name__ == '__main__':
    print(monotoneIncreasingDigits(332))  # Expected: 299

📊

Monotone Increasing Digits - Watch the Algorithm Execute, Step by Step

Watching each digit comparison and adjustment helps you understand how the greedy approach finds the optimal solution efficiently without brute force.

setup

3

0

3

1

2

2

setup

3

0

3

1

2

2

compare

3

0

3

1

i

2

2

compare

3

0

3

1

marker

2

2

shrink

3

0

2

1

marker

2

2

compare

3

0

i

2

1

marker

2

2

compare

3

0

marker

2

1

2

2

shrink

2

0

marker

2

1

2

2

traverse

2

0

marker

2

1

2

2

fill_cells

2

0

i

9

1

2

2

fill_cells

2

0

marker

9

1

i

9

2

reconstruct

2

0

9

1

9

2

Result: 299

Key Takeaways

✓ The algorithm detects monotone breaks by scanning digits from right to left and fixes them greedily by decrementing the previous digit.

This insight is hard to see from code alone because the backward traversal and marker logic are subtle without visualization.

✓ Setting all digits after the marker to 9 maximizes the number while maintaining monotonicity.

Visualizing the fill with 9s clarifies why this step produces the largest valid number.

✓ Multiple decrements may cascade leftwards if earlier digits become smaller than their predecessors after adjustment.

The trace shows how the algorithm handles cascading fixes, which is not obvious from reading code.

Practice

1. Consider the following code snippet implementing the peak-valley approach to maximize stock profit. What is the final returned profit when the input prices are [1, 2, 3]?

def maxProfit(prices):
    i = 0
    profit = 0
    n = len(prices)
    while i < n - 1:
        while i < n - 1 and prices[i] >= prices[i + 1]:
            i += 1
        valley = prices[i]
        while i < n - 1 and prices[i] <= prices[i + 1]:
            i += 1
        peak = prices[i]
        profit += peak - valley
    return profit

easy

A. 2

B. 0

C. 3

D. 1

Solution

1. Step 1: Trace first while loop to find valley

   i=0, prices[0]=1, prices[1]=2, 1 < 2 so inner loop skips, valley=1

2. Step 2: Trace second while loop to find peak

   i increments while prices[i] <= prices[i+1]: i=0 to 1 (2 <= 3), i=1 to 2 (3 no next), peak=3

3. Step 3: Calculate profit and return

   profit += 3 - 1 = 2, loop ends, return 2

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Profit matches sum of positive differences (2) [OK]

Hint: Sum of (3-1) = 2 profit [OK]

Common Mistakes:

• Off-by-one error missing last peak
• Confusing valley and peak assignments
• Returning zero if no decreasing sequence found

2. Given the following code, what is the return value when gas = [2, 3, 4] and cost = [3, 4, 3]?

def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    if sum(net) < 0:
        return -1
    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

print(canCompleteCircuit(gas, cost))

easy

A. -1

B. 0

C. 1

D. 2

Solution

1. Step 1: Compute net array

   net = [2-3, 3-4, 4-3] = [-1, -1, 1], sum(net) = -1 which is less than 0, so return -1 immediately.

2. Step 2: Check sum(net)

   Since sum(net) < 0, no start station can complete the circuit.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum of net gas is negative, no solution exists [OK]

Hint: Sum net gas < 0 means no solution [OK]

Common Mistakes:

• Forgetting to check total gas vs cost
• Misindexing prefix sums
• Returning wrong start index

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

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 -1
            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])

A = [3,5,1,2]
B = [3,6,3,3]
print(minDominoRotations(A, B))

easy

A. -1

B. 2

C. 1

D. 3

Solution

1. Step 1: Check candidate x = A[0] = 3

   i=0: A[0]=3 matches x=3, no rotation.
   i=1: A[1]=5 != 3, B[1]=6 != 3 -> return -1 immediately.

2. Step 2: Check candidate x = B[0] = 3

   i=0: A[0]=3 matches x=3, no rotation.
   i=1: A[1]=5 != 3, B[1]=6 != 3 -> return -1 immediately.
   Both candidates fail, so output is -1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Both candidates fail at i=1, so no solution [OK]

Hint: Check both candidates carefully for early failure [OK]

Common Mistakes:

• Assuming first candidate always works
• Miscounting rotations when both sides match

4. Given the following code for the Task Scheduler, what is the returned value for leastInterval(['A','A','B'], 2)?

easy

A. 3

B. 5

C. 6

D. 4

Solution

1. Step 1: Initialize frequencies and max-heap

   Tasks: A(2), B(1). Max-heap: [-2, -1].

2. Step 2: Simulate scheduling cycles

   Cycle 1: pop -2 (A), decrement to -1 and store; pop -1 (B), decrement to 0 ignore; cycle=2, heap not empty -> time += n+1=3.
   Cycle 2: pop -1 (A), decrement to 0 ignore; cycle=1, heap empty -> time += cycle=1.
   Total time = 3 + 1 = 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual simulation matches 4 units [OK]

Hint: Count cycles and add idle if heap not empty [OK]

Common Mistakes:

• Off-by-one in cycle count
• Adding n+1 even when heap empty
• Ignoring decrement of counts

5. Consider the following buggy code for assigning cookies to children. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line 5: Missing increment of j when cookie is assigned

B. Line 3: Incorrect loop condition including count < len(g)

C. Line 1: Missing sorting of g and s arrays

D. Line 7: Incrementing j only in else block

Solution

1. Step 1: Identify missing pointer increment

   When a cookie satisfies a child (s[j] ≥ g[i]), j should increment to avoid reusing the same cookie.

2. Step 2: Check code lines

   Line 5 increments count and i but does not increment j, causing the same cookie to be assigned multiple times.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without j increment on assignment, cookie reuse occurs [OK]

Hint: Check pointer increments on both branches [OK]

Common Mistakes:

• Forgetting to sort arrays
• Incorrect loop conditions
• Not incrementing both pointers on assignment