Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A numerically balanced number uses each present digit d exactly d times; zero cannot appear. The bounded input permits a precomputed sorted list of all relevant candidates, including one beyond the maximum input. The problem then becomes a strict-successor lookup.

Approach

Use the literal balanced-number table stored in the solution. Binary-search for the first table entry strictly greater than n, using an upper-bound search so an equal balanced value is skipped. Return that entry. The final candidate 1224444 covers the upper end of the allowed input range. The reference implementation does not generate permutations or test successive integers at query time.

class Solution:
    def nextBeautifulNumber(self, n: int) -> int:
        all = [1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444]
        return all[bisect_right(all, n)]

Complexity analysis

Let B be the number of entries in the sorted literal table. Both implementations materialize the table in O(B) time and space, then use binary search in O(log B) time to find the first balanced number greater than n.