Check Whether Digits Are Monotone Increasing
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Check Whether Digits Are Monotone Increasing
## Problem
A non-negative integer has monotone increasing digits when every adjacent pair of digits is non-decreasing from left to right. In other words, for digits `d[0], d[1], ..., d[m-1]`, `d[i] <= d[i+1]` for every valid `i`.
Implement:
```python
def has_monotone_increasing_digits(n: int) -> bool:
...
```
## Constraints
- `0 <= n <= 10^18`
- The single-digit numbers, including `0`, are monotone increasing.
- Do not reorder, remove, or replace digits.
## Examples
```text
123449 -> True
112233 -> True
332 -> False
10 -> False
7 -> True
```
## Performance Goal
Use `O(d)` time for `d` digits and `O(1)` auxiliary space if processing arithmetically, or `O(d)` space if converting to a string. Explain the edge cases in either representation.
Quick Answer: Check whether a non-negative integer's decimal digits are non-decreasing from left to right. Cover zero, single-digit values, repeated digits, and an O(d) implementation using either arithmetic digit extraction or string traversal.
Return whether the decimal digits of a nonnegative integer are nondecreasing from left to right.
Constraints
- 0 <= n <= 10^18
- Single-digit values are monotone
- Digits may not be reordered
Examples
Input: 0
Expected Output: True
Explanation: Zero is a single digit.
Input: 7
Expected Output: True
Explanation: Every single-digit number qualifies.
Hints
- Compare each digit only with its successor.
- Equality is allowed; only a decrease fails.