algoadvance

Leetcode 556. Next Greater Element III

Problem Statement

Given a positive integer n, find the smallest positive 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.

Example:

Input: n = 12
Output: 21

Input: n = 21
Output: -1

Clarifying Questions

  1. Q: Can the integer n be very large?
    • A: The problem does not specify an upper limit, but typically n will be within the bounds of a standard integer type.
  2. Q: Can we assume that the input n is always positive?
    • A: Yes, the problem statement specifies that n is a positive integer.
  3. Q: Should leading zeros be considered?
    • A: The problem deals with positive integers, so leading zeros in the output do not need explicit handling due to integer properties.

Strategy

  1. Convert the integer to a string to analyze and manipulate the digits easily.
  2. Traverse the string from right to left to find the first digit that is smaller than the digit next to it (right to left ensures the smallest possible change yielding the next greater number).
  3. Once such a digit is found, locate the smallest digit to the right of the found digit that is larger than it.
  4. Swap those two digits.
  5. Sort the digits after the initially found digit in ascending order to get the smallest possible number.

Code

#include <iostream>
#include <string>
#include <algorithm>

int nextGreaterElement(int n) {
    std::string num = std::to_string(n);
    int len = num.size();
    
    // Step 2: Find first decreasing digit from the right
    int i = len - 2;
    while (i >= 0 && num[i] >= num[i + 1]) {
        i--;
    }
    
    // If no such digit is found, return -1
    if (i < 0) return -1;
    
    // Step 3: Find the smallest digit on the right of `i` that is larger than num[i]
    int j = len - 1;
    while (num[j] <= num[i]) {
        j--;
    }
    
    // Step 4: Swap
    std::swap(num[i], num[j]);
    
    // Step 5: Reverse the digits after `i`
    std::reverse(num.begin() + i + 1, num.end());
    
    // Convert string back to integer
    long result = std::stol(num);
    
    // Check if the result is within the 32-bit integer range
    return (result > INT_MAX) ? -1 : static_cast<int>(result);
}

// Test the function
int main() {
    int n = 12;
    std::cout << "Next greater element of " << n << " is: " << nextGreaterElement(n) << std::endl;
    
    n = 21;
    std::cout << "Next greater element of " << n << " is: " << nextGreaterElement(n) << std::endl;
    
    return 0;
}

Time Complexity

The time complexity of the above approach is (O(k)), where (k) is the number of digits in the number n. The key operations such as finding indices and swapping digits happen in constant time, and the sorting operation performed on the suffix is (O(k \log k)), which is manageable for typical input sizes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI