Next Greater Numerically Balanced Number - Video Solutions

Problem Overview: Given an integer n, return the smallest integer strictly greater than n where every digit appears exactly as many times as its value. For example, 22 is numerically balanced because digit 2 appears twice, while 1333 is balanced because digit 1 appears once and digit 3 appears three times.

Approach 1: Brute Force Search (Time: O(k * d), Space: O(1))

Start from n + 1 and increment one number at a time. For each candidate, count digit frequencies using a small array of size 10. A number is numerically balanced if every digit d appears exactly d times and digits with frequency > 0 satisfy the rule. Each validation scans the digits of the number, which takes O(d) where d is the number of digits. Since the search space is small (balanced numbers are rare and typically below 10⁷), this brute force approach performs surprisingly well in practice. This method mainly relies on simple counting logic from math and is easy to implement during interviews.

Approach 2: Permutations with Digit Limits (Time: O(P), Space: O(P))

Instead of scanning every number, generate only valid numerically balanced numbers. The key observation: a balanced number can only contain digits 1–9 where the count of each digit equals the digit itself. That means valid digit sets look like {1}, {2,2}, {1,2,2}, {3,3,3}, etc. Build candidate digit multisets where the frequency rule already holds, then generate all permutations of those digits. Convert each permutation to an integer and keep only those greater than n. Finally return the minimum valid candidate. Generation can be implemented using backtracking or direct enumeration. Because the total number of balanced numbers is tiny, this approach efficiently precomputes all possibilities and performs a simple comparison search.

Recommended for interviews: Start with brute force to show you understand the definition and validation logic. Then explain the enumeration insight: balanced numbers have strict digit-frequency constraints, so generating valid permutations dramatically reduces the search space. Interviewers usually expect you to recognize this constraint-based enumeration since it avoids unnecessary checks and demonstrates stronger algorithmic reasoning.