My python solution - 35 ms

  • 0

    Concretely, if all the bits are in decreasing order, for example, 4321, then there would be no next greater element. If we have a number like 12431, then we need to exchange 3 with 2, 13421. Now 3 is definitely at its rightful position. We only need to see what is the smallest number formed by 4, 2, 1, which is 124.

    Program above idea: suppose our number in its string format is ns, where ns[0] is the highest bit. We scan from the lowest bit until we encounter the bit i where ns[i] < ns[i+1], then we exchange ns[i] with ns[j], where j is the lowest bit that satisfies ns[i] < ns[j]. After this, we can be sure that bit i is right, then we need to sort ns[i+1:len(ns)].

    class Solution(object):
        def nextGreaterElement(self, n):
            :type n: int
            :rtype: int
            ns = [s for s in str(n)]
            for i in range(len(ns)-2, -1, -1):
                if ns[i] < ns[i+1]:
                    j = len(ns) - 1
                    while ns[j] <= ns[i]: # need to find ns[i] < ns[j] where j is the lowest possible bit
                        j -= 1
                    ns[i], ns[j] = ns[j], ns[i]
                    ns[i+1:] = sorted(ns[i+1: ])
                    return int(''.join(ns)) if int(''.join(ns)) < 2**31 - 1 else -1
            return -1

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.