738. Monotone Increasing Digits

MediumGreedyMath
Leetcode Link

Problem Description

The problem statement presents a challenge where you need to find the largest number that is less than or equal to a given integer n and also has monotone increasing digits. A number is said to have monotone increasing digits if every digit is less than or equal to the digit immediately to its right. The objective is to transform n in such a way that it satisfies this condition but still remains the largest possible number under the given constraints.

Intuition

To solve this problem, the intuition is to process the number from the left to right because the leftmost digits have a higher value. Therefore, adjusting them will have a greater impact on the overall value of the number. As we iterate through the digits, we're looking for the point where the monotone condition is violated (a digit that is greater than the next digit). When this violation is found, we must adjust the number to restore the monotone condition.

The key insight is that once we find a pair of digits where the left digit is greater than the right digit, we can reduce the left digit by one and change all subsequent digits to 9 to get the largest possible monotone increasing number. However, this reduction can cause a violation of the monotone condition to the left, so we must check and fix those cases too.

The solution approach involves turning the integer into a string to work with individual digits more conveniently, then walking through the string to find the first descending point. We decrement the digit at that point and then check to the left to ensure we still have a monotone sequence, adjusting as needed. Lastly, we set all digits to the right of the adjusted digit to 9, since that will give us the largest possible number that maintains our condition.

Learn more about Greedy and Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The implementation starts by converting the integer n to a string. This allows us to access each digit character easily to compare and modify them.

The algorithm proceeds in the following steps:

  1. Initiate Search for Non-Monotone Point: We initialize i to 1 and start iterating over the digits from left to right, comparing each digit with its immediate predecessor to ensure that each digit is greater than or equal to the previous one. The goal is to identify the index where the monotone increasing property fails.

  2. Detect Decreasing Sequence: As we proceed, if we find a digit that is smaller than the digit before it (s[i] < s[i - 1]), this is where the property of monotone increasing digits is violated. This is the point where we need to take action to correct the sequence.

  3. Reduce and Correct the Sequence: To fix the violation, we move one position to the left (start decrementing i) and reduce that digit by 1 (s[i - 1] = str(int(s[i - 1]) - 1)). We continue correcting the sequence by moving leftward until we reach a point where the sequence is increasing again.

  4. Maximize Remaining Digits: After correcting the sequence, we replace all digits to the right of our correction point with '9'. This is because '9's will maximize the resulting number while preserving the monotone property from that point forward.

  5. Return the Result: Finally, we convert the list of characters back into a string, and then into an integer, which is the largest number less than or equal to n with monotone increasing digits.

Algorithmic Concepts:

  • Greedy Approach: The idea of changing only the first violating digit and replacing subsequent digits with '9's is greedy because it makes the most significant digits as large as possible without violating the monotone condition.

  • String Manipulation: By treating the number as a string, we are able to manipulate individual digits more directly compared to doing so with arithmetic operations.

  • Simple Iteration: The solution performs linear scans from left to right, and in some cases from right to left, showcasing a good use of simple iterative logic to solve the problem.

Data Structures Used:

  • List of Characters: A list is used to represent the digits of n, because string in Python is immutable, and a list allows us to make changes to individual digits conveniently.

The solution exploits the property that a number is always greater when its leftmost digits are greater, hence the left-to-right and then right-to-left scans to achieve a correct and efficient approach to finding the answer.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the integer n = 3214.

Following the steps of the solution:

  1. Initiate Search for Non-Monotone Point: We will convert the number into a string for easy manipulation, s = "3214", and start looking for the point where the digits stop being monotone increasing. We initialize i to 1 and start comparing adjacent digits.

  2. Detect Decreasing Sequence: While comparing, we notice that s[1] > s[2] (which is 2 > 1), violating the monotone increasing condition at index i = 2.

  3. Reduce and Correct the Sequence: Now, we need to decrement s[i - 1] from 2 to 1. But this alone makes the string "3114", which still violates the condition at i = 1 (since 3 > 1). So, we need to also decrement s[i - 2] from 3 to 2, giving us "2114".

  4. Maximize Remaining Digits: After the correction, we know that s[i] to s[len(s) - 1] can all be set to '9' to maximize the number without violating the monotone condition. So, '2114' becomes '2999'.

  5. Return the Result: We convert the string "2999" back into an integer, which gives us 2999. This is the largest number less than or equal to 3214 that has monotone increasing digits.

With the original number 3214, the solution finds that at the index 2, the monotone condition is violated. It then modifies the digits in such a way to maintain the maximum values while correcting the sequence, resulting in 2999. This effectively demonstrates the greedy approach of the solution, which optimizes the leftmost digits first to get the largest possible number with the constraint of monotone increasing digits.

Solution Implementation

1class Solution:
2    def monotoneIncreasingDigits(self, n: int) -> int:
3        # Convert the number to a list of characters for easy manipulation
4        digits = list(str(n))
5
6        # Find the first digit that breaks the monotony
7        index = 1
8        while index < len(digits) and digits[index - 1] <= digits[index]:
9            index += 1
10
11        # If a non-monotone digit was found, modify the number
12        if index < len(digits):
13            # Decrease the previous digit by 1 until the number becomes monotone
14            while index > 0 and digits[index - 1] > digits[index]:
15                digits[index - 1] = str(int(digits[index - 1]) - 1)
16                index -= 1
17
18            # Setting the rest of the digits to '9' to guarantee the largest monotone number
19            index += 1
20            while index < len(digits):
21                digits[index] = '9'
22                index += 1
23
24        # Convert the list of characters back to an integer and return
25        return int(''.join(digits))
26
1class Solution {
2    public int monotoneIncreasingDigits(int n) {
3        // Convert the input integer n to a character array to process each digit individually.
4        char[] digits = String.valueOf(n).toCharArray();
5      
6        // Initialize index i for iterating through the digits.
7        int i = 1;
8      
9        // Find the point where digits are no longer increasing (i.e., digits[i-1] > digits[i]).
10        for (; i < digits.length && digits[i - 1] <= digits[i]; i++) {
11            // This loop will keep iterating until it finds a decreasing point or reaches the end.
12        }
13      
14        // If the monotone increasing property is violated,
15        // work backwards to find the digit which can be decremented.
16        if (i < digits.length) {
17            // Decrement the violating digit and find the position from which to replace with 9s.
18            for (; i > 0 && digits[i - 1] > digits[i]; i--) {
19                // Reduce the previous digit by 1 to maintain the monotone increasing property.
20                digits[i - 1]--;
21            }
22
23            // Reset remaining digits to '9' beginning from the current index to the end of the array.
24            for (; i < digits.length; i++) {
25                digits[i] = '9';
26            }
27        }
28      
29        // Convert the updated character array back to an integer and return the result.
30        return Integer.parseInt(new String(digits));
31    }
32}
33
1class Solution {
2public:
3    // This function finds the largest monotone increasing number that is less than or equal to n.
4    int monotoneIncreasingDigits(int n) {
5        // Convert the integer n to a string representation for digit manipulation
6        string numStr = to_string(n);
7        int marker = 1;
8      
9        // Traverse the digits of the number until we find a digit that is less than the previous digit,
10        // indicating that the sequence is no longer monotone increasing
11        while (marker < numStr.size() && numStr[marker - 1] <= numStr[marker]) {
12            ++marker;
13        }
14      
15        // If we found a position where the monotone property is violated
16        if (marker < numStr.size()) {
17            // Go back and find the position where we need to decrement to restore the monotone property
18            while (marker > 0 && numStr[marker - 1] > numStr[marker]) {
19                numStr[marker - 1]--;
20                --marker;
21            }
22            // Fill the rest of the digits after marker with '9' to maximize the resultant number
23            for (int i = marker + 1; i < numStr.size(); ++i) {
24                numStr[i] = '9';
25            }
26        }
27      
28        // Convert the modified string back to an integer and return it
29        return stoi(numStr);
30    }
31};
32
1// This function finds the largest monotone increasing number that is less than or equal to n.
2function monotoneIncreasingDigits(n: number): number {
3    // Convert the integer n to a string representation for digit manipulation
4    let numStr: string = n.toString();
5  
6    // Initialize marker as a pointer to traverse the digits
7    let marker: number = 1;
8
9    // Traverse the digits of the number to find where the monotone increasing sequence is broken
10    while (marker < numStr.length && numStr[marker - 1] <= numStr[marker]) {
11        marker++;
12    }
13
14    // Check if we found a position where the sequence is no longer monotone increasing
15    if (marker < numStr.length) {
16        // Step back to find the correct digit to decrement in order to keep the number monotone increasing
17        while (marker > 0 && numStr[marker - 1] > numStr[marker]) {
18            // Decrement the digit at marker - 1
19            let prevDigit = parseInt(numStr[marker - 1], 10) - 1;
20            numStr = numStr.substring(0, marker - 1) + prevDigit.toString() + numStr.substring(marker);
21
22            // Move the marker back to the left as needed
23            marker--;
24        }
25
26        // Fill the rest of the string with '9' after the marker to maximize the resulting number
27        for (let i = marker + 1; i < numStr.length; i++) {
28            numStr = numStr.substring(0, i) + '9' + numStr.substring(i + 1);
29        }
30    }
31
32    // Convert the modified string back to an integer and return it
33    return parseInt(numStr, 10);
34}
35
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

The provided code aims to find the largest monotone increasing number that is less than or equal to a given number n. The time complexity and space complexity are analyzed as follows:

Time Complexity

  • Best-case scenario: When the digits are already in a monotone increasing order, the algorithm would traverse the number's digits once. Thus, in the best case, the time complexity is O(d), where d is the number of digits in n.

  • Worst-case scenario: The algorithm will need to traverse the digits twice if a decrease is found:

    • Once to identify the first position where s[i - 1] is greater than s[i].
    • And a second pass to correct the number by decrementing the digit at position i - 1 and setting all subsequent digits to '9'.

    Since each of these operations is linear with respect to the number of digits in n, the worst-case time complexity will also be O(d).

In conclusion, the overall time complexity is O(d), with d being the number of digits in n.

Space Complexity

  • The input number n is converted to a list s of its digits in string format. This is the only significant additional memory used, which depends on the number of digits d in n.

  • No other additional data structures are used that grow with the input size. The variables used for iteration and comparison are constant in size.

Therefore, the space complexity is O(d), where d is the number of digits in n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫