Python 39ms O(n)


  • 1

    same idea as "next permutation." Start from back, find point where the previous digit is less than the current digit, look for the furthest right value that is greater than (which is also the smallest digit that is greater than) the previous digit, swap the two, then reverse the array from the current digit to the end.

        def nextGreaterElement(self, n):
            if not n: return -1
            s = str(n)
            arr = [c for c in s]
            i = len(arr)-1
            while i > 0:
                prev = int(arr[i-1])
                if int(arr[i]) > prev:
                    j = i
                    # looking for right position to swap
                    while j < len(arr) and int(arr[j]) > prev:
                        j += 1
                    arr[i-1], arr[j-1], j = arr[j-1], arr[i-1], len(arr)-1
                    # reverse array from pivot point til end
                    while i < j:
                        arr[i], arr[j] = arr[j], arr[i]
                        i += 1; j -= 1
                    res = int(''.join(arr))
                    # check 32 bit constraint
                    return -1 if res > 2147483647 else res
                i -= 1
            return -1
    

  • 0
    S

    Same idea, a little bit different implementation. Use sort for next permutation.

    class Solution(object):
        def nextGreaterElement(self, n):
            """
            :type n: int
            :rtype: int
            """
            max_int = 2**31 - 1
            s = str(n)
            for i in range(len(s) - 1, 0, -1):
                if s[i] > s[i - 1]:
                    # possible swap
                    for j in range(len(s) - 1, i - 1, -1):
                        if s[j] > s[i-1]:
                            break
                    # s[j] as first one > s[i-1]
                    new_s = s[:i-1] + s[j] + ''.join(sorted(s[i-1:j] + s[j+1:]))
                    result = int(new_s)
                    return result if result <= max_int else -1
            return -1
    

  • -1
    S

    This is not O(n). Considering the search and swap, the expectation should be O(n2)


  • 0

    @sylvanyang O(n2) and O(n) are the exact same thing, so it can't be one but not the other. Also, it's actually O(log2 n).


Log in to reply
 

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