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. You are given a list of non-negative integers and need to arrange them to form the largest possible number when concatenated. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming to find the maximum concatenation by exploring all subsequences

B. Sorting the numbers as strings using a custom comparator that compares concatenations

C. Greedy approach by always picking the largest integer first

D. Brute force generating all permutations and selecting the maximum concatenation

Solution

1. Step 1: Understand the problem requires ordering numbers to maximize concatenation

   The key is to compare pairs by concatenating in both possible orders and deciding which order yields a larger combined string.

2. Step 2: Recognize that sorting with a custom comparator based on concatenation comparisons guarantees optimal order

   This approach ensures the final concatenation is lexicographically largest, unlike greedy or DP which do not handle pairwise ordering correctly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Custom comparator sorting is the standard solution for this problem [OK]

Hint: Compare concatenations as strings to decide order [OK]

Common Mistakes:

• Assuming greedy pick of largest integer works
• Using DP which is unnecessary
• Brute force is correct but inefficient

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

def maximumUnits(boxTypes, truckSize):
    boxTypes.sort(key=lambda x: x[1], reverse=True)
    totalUnits = 0
    for boxes, units in boxTypes:
        if truckSize == 0:
            break
        take = min(boxes, truckSize)
        totalUnits += take * units
        truckSize -= take
    return totalUnits

boxTypes = [[1,3],[2,2],[3,1]]
truckSize = 4
print(maximumUnits(boxTypes, truckSize))

easy

A. 7

B. 8

C. 9

D. 6

Solution

1. Step 1: Sort boxTypes by units descending

   Sorted list: [[1,3],[2,2],[3,1]] (already sorted)

2. Step 2: Iterate and pick boxes until truckSize=0

   Take 1 box with 3 units -> totalUnits=3, truckSize=3 left; take 2 boxes with 2 units -> totalUnits=3+4=7, truckSize=1 left; take 1 box with 1 unit -> totalUnits=7+1=8, truckSize=0 stop.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum matches manual calculation [OK]

Hint: Sort by units descending and pick greedily [OK]

Common Mistakes:

• Off-by-one in take calculation
• Not stopping when truckSize=0
• Incorrect sorting order

3. You are given arrival and departure times of trains at a station. You need to find the minimum number of platforms required so that no train waits. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Sort trains by arrival time and use a min-heap to track earliest departure times

B. Dynamic Programming to find the maximum number of overlapping intervals

C. Greedy approach by always assigning the next available platform without sorting

D. Brute force nested loops checking all pairs of trains for overlaps

Solution

1. Step 1: Understand the problem requires tracking overlapping intervals

   We need to find the maximum number of trains simultaneously at the station, which corresponds to the maximum overlap of intervals.

2. Step 2: Identify the optimal approach

   Sorting trains by arrival time and using a min-heap to track the earliest departure allows efficient detection of overlaps and platform reuse, guaranteeing an optimal solution.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min-heap approach efficiently tracks platform usage [OK]

Hint: Min-heap tracks earliest departure for platform reuse [OK]

Common Mistakes:

• Assuming greedy without sorting works optimally
• Thinking DP is needed for interval overlaps
• Using brute force for large inputs

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 reorganizing a string. Which line contains the subtle bug that can cause the function to return an invalid string with adjacent identical characters?

import heapq
from collections import Counter

def reorganizeString(s: str) -> str:
    freq = Counter(s)
    max_heap = [(-count, ch) for ch, count in freq.items()]
    heapq.heapify(max_heap)
    prev_count, prev_char = 0, ''
    result = []

    while max_heap:
        count, ch = heapq.heappop(max_heap)
        result.append(ch)
        # Bug: missing check for impossible case
        if prev_count < 0:
            heapq.heappush(max_heap, (prev_count, prev_char))
        prev_count, prev_char = count + 1, ch

    res_str = ''.join(result)
    if len(res_str) != len(s):
        return ""
    return res_str

medium

A. Missing check before the while loop to verify if max frequency exceeds (n+1)/2

B. Line where prev_count and prev_char are updated after appending

C. Line where the previous character is pushed back into the heap

D. Line where max_heap is initialized with negative counts

Solution

1. Step 1: Identify missing validation

   The code lacks a check before the loop to verify if the most frequent character count exceeds (n+1)/2, which makes rearrangement impossible.

2. Step 2: Understand consequences

   Without this check, the algorithm may produce invalid strings with adjacent duplicates or fail silently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding this check prevents impossible cases early [OK]

Hint: Check max frequency before processing [OK]

Common Mistakes:

• Forgetting impossible case check
• Misplacing heap pushback logic
• Incorrect prev_count update