Solution For Next Greater Element Iii

Problem statement:

Given a circular array containing n elements, find the next greater element for every element in the array in a circular fashion. The next greater element of an element x is the first greater element to its right in the circular array. If it does not exist, output -1 for this element.

Example:

Input: [1,2,1]

Output: [2,-1,2]

Explanation:

The first 1’s next greater element is 2;

The second 2 cannot be greater than itself (element on the right is the same), so output -1;

The last 1 has next greater element as 2 (the first occurrence of number 2 is at a circular index of 1, which is greater than the index of the current element).

Solution:

As the array is circular, we need to traverse it twice to find the next greater element for every element in the array.

We can achieve this by using a stack and iterating the array twice. In the first iteration, we will find the next greater element for every element to its right. In the second iteration, we will find the next greater element for every element left to that element.

To find the next greater element to the right, we push the elements onto the stack until we find a larger element. The larger element will be the next greater element for all the previous elements in the stack – we pop those elements from the stack and update their next greater element to be the current element.

To find the next greater element to the left, we follow the same approach but in reverse direction. We push the elements onto the stack until we find a larger element. The larger element will be the next greater element for all the previous elements in the stack – we pop those elements from the stack and update their next greater element to be the current element.

At the end of both iterations, the array will contain the next greater element for every element in the circular array.

Here’s the Python code to implement this approach:

def nextGreaterElements(nums: List[int]) -> List[int]:

n = len(nums)
result = [-1] * n
stack = []

# Iteration 1: Find next greater element to the right
for i in range(n * 2):
    while stack and nums[stack[-1]] < nums[i % n]:
        result[stack.pop()] = nums[i % n]
    stack.append(i % n)

# Iteration 2: Find next greater element to the left
for i in range(n * 2):
    while stack and nums[stack[-1]] < nums[i % n]:
        result[stack.pop()] = nums[i % n]
    if i < n:
        stack.append(i)

return result

Time complexity: O(n)

Space complexity: O(n) (stack size)

Step by Step Implementation For Next Greater Element Iii

class Solution {
    public int nextGreaterElement(int n) {
        char[] num = ("" + n).toCharArray();
        int i = num.length - 2;
        while (i >= 0 && num[i + 1] <= num[i]) {
            i--;
        }
        if (i < 0)
            return -1;
        int j = num.length - 1;
        while (j >= 0 && num[j] <= num[i]) {
            j--;
        }
        swap(num, i, j);
        reverse(num, i + 1);
        try {
            return Integer.parseInt(new String(num));
        } catch (Exception e) {
            return -1;
        }
    }

    private void reverse(char[] num, int start) {
        int i = start, j = num.length - 1;
        while (i < j) {
            swap(num, i, j);
            i++;
            j--;
        }
    }

    private void swap(char[] num, int i, int j) {
        char temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
}

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        
        #convert n to a list of digits
        n_list = [int(i) for i in str(n)]
        
        #find the first digit from the right that is smaller than the digit to its right
        for i in range(len(n_list)-2, -1, -1):
            if n_list[i] < n_list[i+1]:
                break
        else:
            return -1
        
        #swap the smallest digit to the right of i that is greater than n_list[i]
        for j in range(len(n_list)-1, i, -1):
            if n_list[j] > n_list[i]:
                n_list[i], n_list[j] = n_list[j], n_list[i]
                break
        
        #reverse the digits to the right of i
        n_list[i+1:] = n_list[i+1:][::-1]
        
        #check for overflow
        if int(''.join(map(str, n_list))) > 2**31-1:
            return -1
        
        return int(''.join(map(str, n_list)))

var nextGreaterElement = function(n) {
    // convert n to string
    let nStr = n.toString();
    
    // create a map to store the previous element and next element
    let map = new Map();
    
    // iterate through nStr
    for (let i = 0; i < nStr.length; i++) {
        // store the previous element
        let prev = nStr[i-1];
        // store the current element
        let curr = nStr[i];
        // store the next element
        let next = nStr[i+1];
        
        // if the current element is less than the next element
        // store the current element as the key and the next element as the value
        if (curr < next) {
            map.set(curr, next);
        }
    }
    
    // iterate through nStr in reverse
    for (let i = nStr.length - 1; i >= 0; i--) {
        // store the current element
        let curr = nStr[i];
        // store the next element
        let next = map.get(curr);
        
        // if the current element is less than the next element
        if (curr < next) {
            // swap the current element with the next element
            let temp = curr;
            curr = next;
            next = temp;
            
            // join the elements back into a string
            let newStr = nStr.slice(0, i) + curr + next + nStr.slice(i + 2);
            
            // return the new string
            return newStr;
        }
    }
    
    // if no next element is found, return -1
    return -1;
};

int nextGreaterElement(int n) {
    
    // convert int to string
    string num = to_string(n);
    
    // create a stack to store int
    stack stk;
    
    // push first element to stack
    stk.push(num[0]);
    
    // start from the second element
    for (int i = 1; i < num.size(); i++) {
        
        // if current element is greater than the top element in the stack
        // that means we found the next greater element for the top element
        // in the stack
        if (num[i] > stk.top()) {
            
            // pop the element from the stack
            int element = stk.top();
            stk.pop();
            
            // push the current element to the stack
            stk.push(num[i]);
            
            // push the next greater element to the stack
            stk.push(element);
        }
        
        // else push the current element to the stack
        else {
            stk.push(num[i]);
        }
    }
    
    // after the loop the stack will contain the next greater element
    // for each element from right to left
    // so pop each element one by one from the stack and
    // construct the number
    
    // reverse the string
    reverse(num.begin(), num.end());
    
    // replace each element in the string with the
    // next greater element from the stack
    for (int i = 0; i < num.size(); i++) {
        num[i] = stk.top();
        stk.pop();
    }
    
    // reverse the string again to get the number
    // in the correct order
    reverse(num.begin(), num.end());
    
    // convert the string to long long
    long long int res = stoll(num);
    
    // if the result is greater than integer max value
    // return -1
    if (res > INT_MAX) {
        return -1;
    }
    
    // else return the result
    return res;
}

public class Solution {
    public int NextGreaterElement(int n) {
        //convert n to char array
        char[] number = n.ToString().ToCharArray();
        
        //find the first index from the right that is smaller than the number to its right
        int i;
        for(i = number.Length - 1; i > 0; i--){
            if(number[i] > number[i-1]){
                break;
            }
        }
        //if no such index exists, then n is the greatest element
        if(i == 0){
            return -1;
        }
        
        //find the smallest element to the right of (i-1)th index that is greater than number[i-1]
        int x = number[i-1], smallest = i;
        for(int j = i+1; j < number.Length; j++){
            if(number[j] > x && number[j] < number[smallest]){
                smallest = j;
            }
        }
        
        //swap the numbers
        char temp = number[i-1];
        number[i-1] = number[smallest];
        number[smallest] = temp;
        
        //sort the numbers after (i-1) in ascending order
        Array.Sort(number, i, number.Length - i);
        
        //check for overflow and return
        long val = Convert.ToInt64(new string(number));
        return (val <= int.MaxValue) ? (int) val : -1;
    }
}