Katkat
Back

Check Whether Digits Are Monotone Increasing

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Determine if a non-negative integer has digits that are monotonically non-decreasing from left to right, handling edge cases without unnecessary memory allocation.

Problem Statement

Given a non-negative integer n, determine whether its decimal digits are sorted in non-decreasing order from left to right. That is, for every digit, the digit immediately following it must be greater than or equal to it.

Implement the function:

def is_monotone_increasing(n: int) -> bool:
    pass

Input

  • n: A non-negative integer (0 <= n <= 10^18).

Output

  • Return True if the digits of n are non-decreasing from left to right, and False otherwise.

Examples

Example 1:

Input: n = 1234
Output: True
Explanation: 1 <= 2 <= 3 <= 4, which is non-decreasing.

Example 2:

Input: n = 1225
Output: True
Explanation: Adjacent duplicate digits are allowed (1  0, so the digits are not non-decreasing.

Example 4:

Input: n = 0
Output: True
Explanation: Any single-digit number is trivially monotone increasing.

Constraints

  • 0 <= n <= 10^18
  • Your solution should run in O(d) time and O(1) auxiliary space, where d is the number of digits in n.

Hints

Hint 1

Any single-digit integer (0 through 9) is trivially monotone increasing.

Hint 2

You can extract digits from right to left using the modulo operator (`n % 10`) and integer division (`n // 10`).

Hint 3

When traversing right to left, each newly extracted digit must be less than or equal to the previous digit extracted.

Follow-up questions

  • How would you find the largest integer less than or equal to n that has monotone increasing digits?
  • How would your approach change if the input is provided as a string of up to 10^6 digits?
  • How would you modify the solution to check for strictly increasing digits instead of non-decreasing digits?