grid47 Exploring patterns and algorithms
Sep 12, 2024
4 min read
Solution to LeetCode 556: Next Greater Element III Problem
Given a positive integer n, find the smallest integer which can be formed by rearranging the digits of n and is greater than n. If no such integer exists, return -1.
Problem
Approach
Steps
Complexity
Input: The input is a positive integer n, which can be up to 2^31-1.
Example: Input: n = 123
Constraints:
• 1 <= n <= 2^31 - 1
Output: The output should be the smallest integer greater than n formed by rearranging its digits, or -1 if no such integer exists.
Example: Output: 132
Constraints:
• The returned value should be within the 32-bit signed integer range.
Goal: The goal is to find the smallest integer greater than n that can be formed using the digits of n.
Steps:
• Convert n to a string of digits.
• Find the next permutation of the digits that is greater than n.
• If such a permutation exists and it fits within the 32-bit integer range, return it.
• If no permutation is possible or the resulting number exceeds the 32-bit limit, return -1.
Goal: The input integer n will be within the range of 1 to 2^31-1.
Steps:
• 1 <= n <= 2^31 - 1
Assumptions:
• The input will always be a valid positive integer within the specified range.
• Input: Input: n = 123
• Explanation: The next permutation of the digits of 123 is 132, which is the smallest number greater than 123 that can be formed.
• Input: Input: n = 321
• Explanation: Since no larger number can be formed with the digits of 321, the answer is -1.
Approach: The approach involves finding the next permutation of the digits of n that is greater than n. If no such permutation exists, return -1.
Observations:
• Finding the next permutation is a well-known algorithmic problem. It requires rearranging digits to find the smallest number greater than the current number.
• The algorithm can be implemented using a series of steps that involve finding a digit that can be swapped to form the next greater number.
Steps:
• Convert the integer n to a string of digits.
• Find the first digit from the right that is smaller than the digit next to it.
• Find the smallest digit greater than this digit and swap them.
• Reverse the digits to the right of the swapped digit to get the smallest possible number.
• If no such rearrangement is possible, return -1.
Empty Inputs:
• There are no empty inputs as n is always a valid positive integer.
Large Inputs:
• The solution should handle the maximum value of n (2^31-1) without exceeding the 32-bit integer limit.
Special Values:
• For values like 999, no next permutation is possible, and the result should be -1.
Constraints:
• The algorithm must be efficient to handle large inputs within the problem constraints.
intnextGreaterElement(int n) {
auto digits = to_string(n);
next_permutation(begin(digits), end(digits));
auto res = stoll(digits);
return (res > INT_MAX || res <= n)?-1: res;
}
1 : Function Definition
intnextGreaterElement(int n) {
Defines the function `nextGreaterElement`, which takes an integer `n` and returns the next greater integer that can be formed by rearranging its digits.
2 : String Conversion
auto digits = to_string(n);
Converts the integer `n` into a string representation to easily manipulate its digits.
3 : Next Permutation
next_permutation(begin(digits), end(digits));
Uses the `next_permutation` function to rearrange the digits of the string into the next lexicographically greater permutation.
4 : String to Integer Conversion
auto res = stoll(digits);
Converts the string `digits` back into an integer using `stoll` (string to long long). This represents the next greater permutation of digits.
5 : Edge Case Handling, Return Statement
return (res > INT_MAX || res <= n)?-1: res;
Checks if the resulting number exceeds the maximum allowable integer value (`INT_MAX`) or if it's not greater than the original number. If either condition is true, it returns -1, otherwise it returns the next greater number.
Best Case: O(d)
Average Case: O(d)
Worst Case: O(d)
Description: The time complexity is linear in terms of the number of digits, which is at most 10 for a 32-bit integer.
Best Case: O(d)
Worst Case: O(d)
Description: The space complexity is O(d) due to the storage of the digits of the integer.
