456. 132 Pattern

Description

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.

Follow up: The O(n^2) is trivial, could you come up with the O(n logn) or the O(n) solution?

Constraints

• n == nums.length

• 1 <= n <= 104

• -109 <= nums[i] <= 109

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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].

Solutions

Solution 1

/**
 * Time complexity : O(N^2). Two loops are used to find the nums[j], nums[k] 
 *    pairs. Here, n refers to the size of nums array.
 * Space complexity : O(1)
 */

class Solution {
    public boolean find132pattern(int[] nums) {
        if(nums == null || nums.length < 3) {
            return false;
        }
        int n = nums.length;
        int min = Integer.MAX_VALUE;
        
        for(int j = 0; j < n-1; j++) {
            min = Math.min(min, nums[j]);
            for(int k = j+1; k < n; k++) {
                if(min < nums[k] && nums[k] < nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

Follow up