132 pattern leetcode monotonic stack

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Constraints:

n == nums.length
1 <= n <= 2 * 105
-109 <= nums[i] <= 109

public class Pattern_132 {
    /**
     * Our condition - nums[i] < nums[k] < nums[j] , where i<j<k
     *
     * Our approach is to break down the above condition into two set
     * Find,
     *      First, nums[i] < nums[k]
     *      Second, nums[j] > nums[k]
     *
     * @param nums - Input integer array
     * @return true - if exist
     *         false - if not exist
     */
    public static boolean find132pattern(int[] nums) {
        int len = nums.length;
        if(len < 3) return false;

        int[] minPrefix = new int[len];
        // Stack stores the nums[k] values with certain approach
        Stack<Integer> stack = new Stack<>();

        // Stores minimum value till current element
        // Since, nums[i] is the least of (nums[j], nums[k]), i.e., nums[i] < nums[j] && nums[i] < nums[k]
        minPrefix[0] = nums[0];
        for(int i=1; i<len; i++){
            minPrefix[i] = Math.min(minPrefix[i-1], nums[i]);
        }

        // Traversing from the last, which is an optimal approach to reduce the time complexity
        // Now, we have nums[i] which is the least element from {minPrefix} array
        //      we have nums[j], which is the current traversal element from {nums} array
        // We need to find a strategy to get the nums[k], which is in between range (nums[i], nums[j])
        // We also need to keep the range of (nums[i], nums[j]) as max as possible to find the value, i.e., minPrefix[] array
        for(int j = len-1; j>=0; j--) {
            // Our goal is to find element nums[k], which is in between range (nums[i], nums[j])
            // If current element is greater than minPrefix[j], => nums[k] > nums[i]
            if(nums[j] > minPrefix[j]){

                // This is fto find an element(nums[k] in Stack) which is greater than the minPrefix[](nums[i])
                while(!stack.isEmpty() && stack.peek() <= minPrefix[j]){
                    stack.pop();
                }
                // Now we have found an elemnt nums[i], which is lesser than nums[k] => nums[i] < nums[k]

                // Now, we can return true if current (nums[j]) > Stack.peek() (nums[k])
                if(!stack.isEmpty() && stack.peek() < nums[j]){
                    return true;
                }

                // If not, push that element into stack
                stack.push(nums[j]);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(find132pattern(new int[] {1,2,3,4,5}));
        System.out.println(find132pattern(new int[] {1,2,3,2,5}));
        System.out.println(find132pattern(new int[] {4,3,2,1}));
    }
}

132 Pattern | Leetcode 456 | Monotonic Stack