Count Numbers with Non-Decreasing Digits - Solution & Explanation

Problem Overview: You need to count how many numbers satisfy the constraint that digits never decrease from left to right (for example, 11239 is valid while 132 is not). The challenge is that the numeric range can be large, so enumerating every value is too slow.

Approach 1: Brute Force Enumeration (O(n * d) time, O(1) space)

The most direct idea is to iterate through every number in the range and check whether its digits are non-decreasing. Convert each number to a string (or repeatedly extract digits with modulo) and verify that digit[i] >= digit[i-1]. Each validation costs O(d) where d is the number of digits. This works for very small ranges but quickly becomes infeasible when n grows to millions or higher.

Approach 2: Combinatorics with Stars and Bars (O(d * 10) time, O(1) space)

Non‑decreasing numbers have a key property: digits behave like a multiset chosen in sorted order. Counting them is equivalent to choosing digits with repetition allowed while maintaining order. Using combinatorics, the count of length d sequences with digits 0–9 in non‑decreasing order can be computed using combinations such as C(d + 9, 9). This method works well when the task is to count all valid numbers of a fixed length. However, it becomes tricky when an upper bound is imposed, because you must ensure the constructed numbers do not exceed that limit.

Approach 3: Digit Dynamic Programming (Digit DP) (O(d * 10 * 10) time, O(d * 10 * 2) space)

The optimal solution uses digit DP, a common technique for counting numbers with digit constraints. Process the number from left to right while tracking three states: the current index, the previous digit chosen, and whether the prefix is already smaller than the limit (tight flag). At each step, try digits from the previous digit up to the current bound, ensuring the non‑decreasing property holds. Memoization stores results for repeated states, reducing the search space dramatically.

This approach avoids enumerating all numbers. Instead, it enumerates only valid digit transitions. The complexity depends on digit length rather than the numeric value, which makes it efficient even for very large bounds.

Digit DP appears frequently in range-counting problems involving digit constraints such as monotonic digits, digit sums, or forbidden patterns. If you're new to this pattern, review dynamic programming, math combinatorics, and digit manipulation techniques often implemented through string representations.

Recommended for interviews: Start by describing the brute force validator to show understanding of the property. Then transition to digit DP as the scalable solution. Interviewers expect the DP formulation with (index, previousDigit, tight) state and memoization because it handles upper bounds efficiently while enforcing the non-decreasing constraint.