Introduction

In this blog post, we will explore how to solve the LeetCode problem "556" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1. Note that the returned integer should fit in 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1. Example 1: Input: n = 12 Output: 21 Example 2: Input: n = 21 Output: -1 Constraints: 1 <= n <= 231 - 1

Explanation

Here's the breakdown of the solution:

• Find the Pivot: Starting from the rightmost digit, find the first digit (pivot) which is smaller than the digit to its right. This indicates a potential point where we can rearrange digits to find a larger number.
• Find the Replacement: To the right of the pivot, find the smallest digit that is greater than the pivot. Swap these two digits.

• Sort the Right Subarray: Sort the digits to the right of the original pivot in ascending order. This ensures we get the smallest possible integer greater than n.

• Runtime Complexity: O(N), where N is the number of digits in n.

• Storage Complexity: O(N), due to the conversion of the integer to a list of digits.

Code

    def next_greater_element(n: int) -> int:
    """
    Given a positive integer n, find the smallest integer which has exactly the
    same digits existing in the integer n and is greater in value than n.
    If no such positive integer exists, return -1.

    Note that the returned integer should fit in 32-bit integer, if there is
    a valid answer but it does not fit in 32-bit integer, return -1.

    For example:
    next_greater_element(12) == 21
    next_greater_element(21) == -1
    """

    s = list(str(n))
    i = len(s) - 2

    # Find the pivot
    while i >= 0 and s[i] >= s[i + 1]:
        i -= 1

    if i < 0:
        return -1

    # Find the replacement
    j = len(s) - 1
    while j > i and s[j] <= s[i]:
        j -= 1

    # Swap
    s[i], s[j] = s[j], s[i]

    # Sort the right subarray
    s[i + 1:] = sorted(s[i + 1:])

    try:
        result = int("".join(s))
    except ValueError:
        return -1  # Handle potential integer overflow

    if result > (2**31 - 1):
        return -1

    return result