Katkat
Back

Find the Largest Monotone Increasing Number

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests greedy algorithms, digit manipulation, and boundary handling to find the largest number less than or equal to n with non-decreasing decimal digits.

Problem Statement

An integer is said to have monotone increasing digits if each pair of adjacent digits satisfies digits[i] <= digits[i + 1] for all valid i (reading from left to right).

Given an integer n, return the largest integer x such that `x int: pass


## Input and Output Format

- **Input:** A single non-negative integer `n`.
- **Output:** An integer representing the largest number less than or equal to `n` whose decimal digits are in non-decreasing order.

## Constraints

- `0  0). The largest valid number <= 10 is 9.

Example 2

Input: n = 1234
Output: 1234
Explanation: The digits of 1234 are already non-decreasing (1  2. If we just decrement the second 3 to 2 and fill with 9, we get 329, which still violates the monotone condition (3 > 2).
We must backtrack to the first occurrence of 3, decrement it to 2, and turn all subsequent digits into 9, giving 299.

Edge Cases to Consider

  • Single-digit inputs (0 13999`).
  • Leading digit transitions (e.g., 100 -> 99).

Hints

Hint 1

If the digits of n are already in non-decreasing order, then n itself is the answer.

Hint 2

When a decrease digits[i] > digits[i + 1] is encountered, decrementing digits[i] by 1 and setting all subsequent digits to 9 gives the maximal valid suffix.

Hint 3

If digits[i] is part of a run of identical digits, decrementing only digits[i] creates a new decrease; you must backtrack to the first digit of that run.

Follow-up questions

  • How would you modify your solution if the condition required strictly increasing digits (digits[i] < digits[i+1])?
  • Can you solve this in O(log10(n)) time and O(1) extra space without converting the number to a string or array?
  • How would your algorithm scale if n were provided as an arbitrarily large string of up to 100,000 digits?