O(n) java solutioin with monotone stack


  • 0
    J

    Let's read the code first.

    public class Solution {
        public boolean find132pattern(int[] nums) {
            Stack<Integer> st = new Stack<>();   // store the index of the array, not the actual value of the number
            List<Integer> Mn = new ArrayList<>();  // store the min value of the prefix of the array - nums
    
            // dp to calc the Mn
            for(int n : nums) {
                if(Mn.isEmpty()) {
                    Mn.add(n);
                } else {
                    Mn.add(Math.min(n, Mn.get(Mn.size()-1)));
                }
            }
            
            // use a for loop to maintain the monotone stack
            for(int i = 0; i < nums.length; i ++) {
                int n = nums[i];
                
                //[key step] make sure we pop all the number smaller than n, to keep the monotonity of the stack. 
                while(!st.isEmpty() && nums[st.peek()] <= n) {
                    st.pop();
                }
                
                // check if the number we get is smaller than the smallest number from nums[0 - larger number before it]
                if(!st.isEmpty() && Mn.get(st.peek()) < n) {
                    return true;
                }
                
                st.push(i);
            }
            
            // we found no pattern 132 during the previous for loop checks
            return false;
        }
    }
    

    To solve this problem, we need to find such pattern in the below array:
    array = ........[very small number n0]...[large number - n1]....[smaller number n2]...

    To construct the relation of n0 and n1, we can use an array Mn where Mn[i] stores the smallest number from 0 to i. With Mn, we can easily get the smallest number in a any prefix array in O(1).

    In the first few lines of the code, Mn is constructed.

    Then, how can we construct the relatioinship of n1 and n2. We would like to try all the combination of a larger number in the front and a smaller number after the larger number. The solution is to maintain a monotone decreasing stack! With the stack, we can hit all the combination of [larger number] - [smaller number]. Then, we just need to compare the [smaller number] we get with the Mn[i].

    Actually, to come up wiith the solution, you need to have a very deep understanding of the using of monotone stack algorithm. Merely reading this post is far not enough.


Log in to reply
 

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