Jobs

Interviews

Discussions

Next Greater Element III

Medium

DoorDash

0 views

Topics:

ArraysStringsGreedy Algorithms

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 <= 2³¹ - 1

Try coding it in LeetCode

Next Greater Element III

Medium

DoorDash

0 views

Topics:

ArraysStringsGreedy Algorithms

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 <= 2³¹ - 1

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the digits that can appear in the input number?
If there is no next greater element that can be formed, what should I return?
Does the input number contain leading zeros, and should the output number also avoid leading zeros if possible?
Should I handle the case where the integer overflow occurs when forming the next greater element? What value should be returned?
Is the input guaranteed to be a positive integer?

Brute Force Solution

Approach

The brute force method for finding the next greater element involves checking every possible arrangement of the digits in the original number. We generate all possible numbers that can be formed using the same digits and see if any are both larger than the original number and the smallest amongst the numbers larger than the original number.

Here's how the algorithm would work step-by-step:

First, think of all the possible numbers you can make by rearranging the digits of the original number.
Then, take each of these new numbers and compare it to the original number.
If a rearranged number is bigger than the original, put it aside as a potential 'next greater element'.
After checking all possible rearrangements, look at the numbers you put aside.
Find the smallest one among those bigger numbers. That's your next greater element.
If you didn't find any number bigger than the original, then there is no next greater element.

Code Implementation

def next_greater_element_brute_force(number):
    string_representation = str(number)
    import itertools
    permutations = list(itertools.permutations(string_representation))
    
greater_elements = []

    for permutation in permutations:
        arranged_number = int("".join(permutation))

        # Need to make sure the arranged number is greater than the original
        if arranged_number > number:

            greater_elements.append(arranged_number)

    if not greater_elements:
        return -1

    # Need to find the smallest of the greater elements
    smallest_greater_element = min(greater_elements)

    #Check for 32 bit integer overflow
    if smallest_greater_element > (2**31 - 1):
        return -1

    return smallest_greater_element

Big(O) Analysis

Time Complexity

O(n! * n) – The brute force approach involves generating all permutations of the digits of the input number. If the input number has n digits, there are n! possible permutations. For each of these n! permutations, we need to compare it with the original number, which takes O(n) time (to compare n digits). Therefore, the overall time complexity is O(n! * n).

Space Complexity

O(N!) – The brute force approach generates all possible permutations of the digits of the input number. The number of permutations can grow up to N! where N is the number of digits in the input number. Storing these permutations in a list to compare against the original number requires auxiliary space proportional to the number of permutations. Therefore, the auxiliary space complexity is O(N!).

Optimal Solution

Approach

The key idea is to find the smallest number that's bigger than the given number by rearranging its digits. We want to avoid checking every possible rearrangement by working backwards from the end of the number and making a single, smart swap.

Here's how the algorithm would work step-by-step:

Start from the rightmost digit and move left until you find a digit that is smaller than the digit to its right.
If you can't find such a digit, it means the digits are in descending order, and no larger number can be formed with the same digits; so, stop.
Now, find the smallest digit to the right of the digit you found in the first step that is still bigger than that digit.
Swap these two digits.
Finally, sort all the digits to the right of the original digit in ascending order to get the smallest possible arrangement in that portion of the number.
Combine the digits back together to form the next greater element. Be careful for overflow if the resulting number is too big.

Code Implementation

def next_greater_element_iii(number):
    number_string = str(number)
    length = len(number_string)

    # Find the first digit from right that is smaller than the digit to its right.
    for index in range(length - 2, -1, -1):
        if number_string[index] < number_string[index + 1]:
            break
    else:
        return -1

    # If no such digit is found, it's the largest possible number.
    pivot_index = index

    # Find the smallest digit to the right of pivot_index that is greater than digit at pivot_index.
    for index in range(length - 1, pivot_index, -1):
        if number_string[index] > number_string[pivot_index]:
            swap_index = index
            break

    # Swap the pivot digit with the found digit.
    number_string_list = list(number_string)
    number_string_list[pivot_index], number_string_list[swap_index] = number_string_list[swap_index], number_string_list[pivot_index]

    # Sort the digits to the right of the pivot_index in ascending order.
    number_string_list[pivot_index + 1:] = sorted(number_string_list[pivot_index + 1:])
    result_string = "".join(number_string_list)

    # Handle potential overflow by checking against max 32-bit integer.
    try:
        result = int(result_string)
        if result > 2**31 - 1:
            return -1
        else:
            return result
    except ValueError:
        return -1

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the digits of the input number (represented as a string or array of characters) from right to left, at most once, to find the first digit that is smaller than the digit to its right. This takes O(n) time. It then searches for the smallest digit to the right of that digit, again taking at most O(n) time in the worst case. Finally, it sorts the digits to the right of the swapped digit, which takes O(n log n) time in the worst case because there can be at most n digits there. However, because n log n grows slower than O(n^2), the overall complexity is usually dominated by sorting and so is considered O(n log n) but in the example case the number of elements for sort will be much less than total digits. Therefore, the dominant factor becomes O(n).

Space Complexity

O(N) – The algorithm uses a list to store the digits of the input number. The size of this list is directly proportional to the number of digits in the input number, N. The sorting operation in step 5 might use O(log N) space depending on the sorting algorithm, but converting to a list uses O(N) space and dominates. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Input integer is 0	Convert to string and handle like other numbers; if no next greater exists, return -1 as specified.
Input integer is negative	The problem statement specifies a positive 32-bit integer as input, so throw an IllegalArgumentException.
Input integer is already the largest possible permutation	Return -1 since no greater permutation is possible.
Input integer consists of all 9s (e.g., 999999999)	Return -1, as it's already the largest possible integer with those digits.
Input integer leads to integer overflow when calculating the next greater element	Check for potential overflow after the digit swap and reversion steps and before returning by comparing result with Integer.MAX_VALUE.
Input integer with only two digits and they are in descending order	Swap and reverse the two digits to obtain the next greater element, e.g., 21 becomes 12.
Input integer is a single-digit number	Return -1, as there is no greater number that can be formed with a single digit.
Input integer has leading zeros after permutation	After the permutation, ensure to parse the output as an integer and return, which will automatically remove leading zeros.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the digits that can appear in the input number?
If there is no next greater element that can be formed, what should I return?
Does the input number contain leading zeros, and should the output number also avoid leading zeros if possible?
Should I handle the case where the integer overflow occurs when forming the next greater element? What value should be returned?
Is the input guaranteed to be a positive integer?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, think of all the possible numbers you can make by rearranging the digits of the original number.
Then, take each of these new numbers and compare it to the original number.
If a rearranged number is bigger than the original, put it aside as a potential 'next greater element'.
After checking all possible rearrangements, look at the numbers you put aside.
Find the smallest one among those bigger numbers. That's your next greater element.
If you didn't find any number bigger than the original, then there is no next greater element.

Code Implementation

def next_greater_element_brute_force(number):
    string_representation = str(number)
    import itertools
    permutations = list(itertools.permutations(string_representation))
    
greater_elements = []

    for permutation in permutations:
        arranged_number = int("".join(permutation))

        # Need to make sure the arranged number is greater than the original
        if arranged_number > number:

            greater_elements.append(arranged_number)

    if not greater_elements:
        return -1

    # Need to find the smallest of the greater elements
    smallest_greater_element = min(greater_elements)

    #Check for 32 bit integer overflow
    if smallest_greater_element > (2**31 - 1):
        return -1

    return smallest_greater_element

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start from the rightmost digit and move left until you find a digit that is smaller than the digit to its right.
If you can't find such a digit, it means the digits are in descending order, and no larger number can be formed with the same digits; so, stop.
Now, find the smallest digit to the right of the digit you found in the first step that is still bigger than that digit.
Swap these two digits.
Finally, sort all the digits to the right of the original digit in ascending order to get the smallest possible arrangement in that portion of the number.
Combine the digits back together to form the next greater element. Be careful for overflow if the resulting number is too big.

Code Implementation

def next_greater_element_iii(number):
    number_string = str(number)
    length = len(number_string)

    # Find the first digit from right that is smaller than the digit to its right.
    for index in range(length - 2, -1, -1):
        if number_string[index] < number_string[index + 1]:
            break
    else:
        return -1

    # If no such digit is found, it's the largest possible number.
    pivot_index = index

    # Find the smallest digit to the right of pivot_index that is greater than digit at pivot_index.
    for index in range(length - 1, pivot_index, -1):
        if number_string[index] > number_string[pivot_index]:
            swap_index = index
            break

    # Swap the pivot digit with the found digit.
    number_string_list = list(number_string)
    number_string_list[pivot_index], number_string_list[swap_index] = number_string_list[swap_index], number_string_list[pivot_index]

    # Sort the digits to the right of the pivot_index in ascending order.
    number_string_list[pivot_index + 1:] = sorted(number_string_list[pivot_index + 1:])
    result_string = "".join(number_string_list)

    # Handle potential overflow by checking against max 32-bit integer.
    try:
        result = int(result_string)
        if result > 2**31 - 1:
            return -1
        else:
            return result
    except ValueError:
        return -1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input integer is 0	Convert to string and handle like other numbers; if no next greater exists, return -1 as specified.
Input integer is negative	The problem statement specifies a positive 32-bit integer as input, so throw an IllegalArgumentException.
Input integer is already the largest possible permutation	Return -1 since no greater permutation is possible.
Input integer consists of all 9s (e.g., 999999999)	Return -1, as it's already the largest possible integer with those digits.
Input integer leads to integer overflow when calculating the next greater element	Check for potential overflow after the digit swap and reversion steps and before returning by comparing result with Integer.MAX_VALUE.
Input integer with only two digits and they are in descending order	Swap and reverse the two digits to obtain the next greater element, e.g., 21 becomes 12.
Input integer is a single-digit number	Return -1, as there is no greater number that can be formed with a single digit.
Input integer has leading zeros after permutation	After the permutation, ensure to parse the output as an integer and return, which will automatically remove leading zeros.