Typical ways to solve circular array problems. Java solution.


  • 24

    The first typical way to solve circular array problems is to extend the original array to twice length, 2nd half has the same element as first half. Then everything become simple.
    Naive by simple solution, just look for the next greater element directly. Time complexity: O(n^2).

    public class Solution {
        public int[] nextGreaterElements(int[] nums) {
            int max = Integer.MIN_VALUE;
            for (int num : nums) {
                max = Math.max(max, num);
            }
            
            int n = nums.length;
            int[] result = new int[n];
            int[] temp = new int[n * 2];
            
            for (int i = 0; i < n * 2; i++) {
                temp[i] = nums[i % n];
            }
            
            for (int i = 0; i < n; i++) {
                result[i] = -1;
                if (nums[i] == max) continue;
                
                for (int j = i + 1; j < n * 2; j++) {
                    if (temp[j] > nums[i]) {
                        result[i] = temp[j];
                        break;
                    }
                }
            }
            
            return result;
        }
    }
    

    The second way is to use a stack to facilitate the look up. First we put all indexes into the stack, smaller index on the top. Then we start from end of the array look for the first element (index) in the stack which is greater than the current one. That one is guaranteed to be the Next Greater Element. Then put the current element (index) into the stack.
    Time complexity: O(n).

    public class Solution {
        public int[] nextGreaterElements(int[] nums) {
            int n = nums.length;
            int[] result = new int[n];
            
            Stack<Integer> stack = new Stack<>();
            for (int i = n - 1; i >= 0; i--) {
                stack.push(i);
            }
            
            for (int i = n - 1; i >= 0; i--) {
                result[i] = -1;
                while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
                    stack.pop();
                }
                if (!stack.isEmpty()){
                    result[i] = nums[stack.peek()];
                }
                stack.add(i);
            }
            
            return result;
        }
    }
    

  • 0
    V
    This post is deleted!

  • 0
    V
    This post is deleted!

  • 2
    V

    Your solution time complexity is O(n^2). It can be reduced to O(n). Following is my solution:

    public class Solution {
        class node{
            int val, index;
            node(int val, int index){
                this.val = val;
                this.index = index;
            }
        }
        public int[] nextGreaterElements(int[] nums) {
            Stack<node> st = new Stack<node>();
            
            if(nums.length == 0){
                
                return new int[0];
            }
            st.push(new node(nums[0], 0));
            
            int i;
            int res[] =new int[nums.length];
            
            for(i = 1; i < nums.length; i++){
                if(nums[i] <= st.peek().val){
                    st.push(new node(nums[i], i));
                    continue;
                }
                while(!st.isEmpty() && nums[i] > st.peek().val){
                    node temp = (node)st.pop();
                    int index=  temp.index;
                    res[index] = nums[i];
                }
                
                st.push(new node(nums[i], i));
            }
           
            if(st.isEmpty()){
                return res;
            }
            node temp = null;
            int index = st.peek().index;
            
            for(i = 0; i < index; i++){
          
                while(!st.isEmpty() && st.peek().val < nums[i]){
                    temp = (node)st.pop();
                    res[temp.index] = nums[i];
                }
                if(st.isEmpty()){
                    return res;
                }
            }
            
            while(!st.isEmpty()){
                temp = st.pop();
                res[temp.index] = -1;
            }
            return res;
        }
    }
    

  • 0

    @vivek75 Yup, you are right. Updated my post with slightly different way of using stack.


  • 0
    S

    Good solution! Actually, we can just keep the value instead of the index in the stack.


  • 0
    N

    In your first solution, if you init res[i] = -1, you dont need to find the max num.


  • 1

    @novaatru2 Consider test cases [1,1,1.....,1,1] Isn't it more efficient to find max first?


  • 0

    Same idea, perhaps a more concise version:

    public class Solution {
        public int[] nextGreaterElements(int[] nums) {
            if(nums == null || nums.length == 0) return new int[0];
            int len = nums.length, max = Arrays.stream(nums).max().getAsInt();
            int[] res = new int[len];
        
            for(int i = 0; i < nums.length; i++) {
                res[i] = -1;
                if(nums[i] == max) continue;
                
                for(int j = i + 1; i != j; j++) {
                    if(j == len) j = 0;
                    if(nums[i] < nums[j]) {
                        res[i] = nums[j];
                        break;
                    }
                }
            }
            
            return res;
        }
    }
    

  • 1
    K

    @shawngao Great explanation. Here's my stack-based solution with an explanation of what I consider the core principles of the solution:

    • iterate backwards through the array (i.e. from the last element to the first element)
    • at each iteration, search forward for the current number's next greater number
    • when searching forward, consider the number that was the current number in the previous iteration, but don't bother considering any of the numbers that were passed up on in the previous iteration, because those number are less than or equal to the number that was the current number in the previous iteration. If the number that was the current number in the previous iteration is not greater than current number, you already know none of those numbers will be either, so they don't need to be considered in the search.
    public class Solution {
        public int[] nextGreaterElements(int[] nums) {
            int[] results = new int[nums.length];
            
            int n = nums.length;
            Stack<Integer> stack = new Stack<>();
            for (int i = n - 1; i >= 0; i --) {
                stack.push(i);
                results[i] = -1;
            }
            
            for (int i = n - 1; i >= 0; i --) {
                while (!stack.isEmpty()) {
                    int index = stack.peek();
                    if (nums[index] > nums[i]) {
                        results[i] = nums[index];
                        break;
                    } else {
                        stack.pop();
                    }
                }
                stack.push(i);
            }
            
            
            return results;
        }
    }
    

  • 0

    said in Typical ways to solve circular array problems. Java solution.:

            stack.add(i);
    

    Thank you for posting two ways. Very helpful.

    Is it a typo or it's a method of built-in Stack in Java. Seems like a "push".

    And for the 1st approach. Could you please explain why you need the max variable.


  • 0
    T

    Thanks for solutions:
    I simulated your method, but using deque:

    public class Solution {
        public int[] nextGreaterElements(int[] nums) {
            int[] res=new int[nums.length];   
            Deque<Integer> deque=new ArrayDeque<>();
            
            for(int i=0;i<nums.length;i++){
                deque.offer(i);
            }
            
            for(int i=nums.length-1;i>=0;i--){
                res[i]=-1;
                while(!deque.isEmpty()&&nums[deque.peekFirst()]<=nums[i]){
                    deque.pollFirst();
                }
                if(!deque.isEmpty()){
                    res[i]=nums[deque.peekFirst()];
                }
                deque.offerFirst(i);
            }
            
            return res;
        }
    }
    

  • 0
    M

    Really like the Stack-based solution, which helps eliminate a lot of unnecessary checks.


  • 0
    Z

    Similar to the double-array idea:

    class Solution {
        public int[] nextGreaterElements(int[] nums) {
            int[] res=new int[nums.length];
            
            Stack<Integer> stack=new Stack<>();
            // from right to left, push all the numbers onto the stack
            // this is to handle the circular array
            for (int i=nums.length-1;i>=0;i--)
                stack.push(nums[i]);
            
            // from right to left, find the next greater element for every element.
            for (int i=nums.length-1;i>=0;i--){
                while (!stack.isEmpty() && stack.peek()<=nums[i])
                    stack.pop();
                
                res[i]=(stack.isEmpty())?-1:stack.peek();
                stack.push(nums[i]);
            }
            return res;
        }
    }
    

  • 0
    L

    May I ask that why at last we need put the current element (index) into the stack?
    Many tanks @shawngao


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.