algoadvance

Leetcode 738. Monotone Increasing Digits

Problem Statement

Given a non-negative integer N, you need to find the largest number that is less than or equal to N and that its digits are in non-decreasing order (monotone increasing).

Clarifying Questions

  1. What is the input range for N?
    • N will be a non-negative integer and the standard range for an integer would be assumed.
  2. Can N be 0?
    • Yes, since the problem states N is non-negative.
  3. Are there built-in functions we can use to convert between characters and digits?
    • Yes, we can leverage character manipulation functions in C++ to easily switch between digits and characters.
  4. What is the expected type for input and output?
    • Input: int N
    • Output: int

Strategy

  1. Convert N to a String: This allows easy manipulation of its digits.
  2. Identify Violation Point: Traverse from left to right to find where the order violation occurs (if any).
  3. Make Adjustment: If a violation is found (i.e., a digit is smaller than the previous one),:
    • Reduce the digit just before the violation.
    • Change all subsequent digits to ‘9’ to maximize the resultant number.
  4. Manage Propagation: It might be needed to propagate the decrement to the left if converting a digit to ‘9’ creates another violation.
  5. Convert Back to Integer: After adjustments, convert the string back to an integer and return the result.

Code

Here is the C++ implementation of the described solution:

#include <iostream>
#include <string>

int monotoneIncreasingDigits(int N) {
    std::string strN = std::to_string(N);
    int n = strN.size();
    int marker = n;
    
    // Find the first place where the order is violated.
    for (int i = n - 1; i > 0; --i) {
        if (strN[i] < strN[i - 1]) {
            marker = i;
            strN[i - 1]--;
        }
    }
    
    // Change all digits after the marker to '9'.
    for (int i = marker; i < n; ++i) {
        strN[i] = '9';
    }
    
    return std::stoi(strN);
}

int main() {
    int N = 332;
    std::cout << "The largest number less than or equal to " << N << " with monotone increasing digits is " << monotoneIncreasingDigits(N) << std::endl;
    return 0;
}

Time Complexity

Space Complexity

This covers the strategy and solution to the problem, ensuring clarity and efficiency in implementation.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI