medium 132 Pattern

Problem Statement

Given an array nums, containing N integers.

A 132 pattern consists of three numbers, say x, y, and z, where x < z and z < y. This is often referred to as a '132' pattern because if we represent x, y, and z as 1, 3, and 2, respectively, it mimics the positional pattern in '132'.

Return true if such a pattern exists within any sequence of given numbers nums. Otherwise, return false.

Examples

1. Example 1:

   • Input: nums = [3, 5, 0, 3, 4]
   • Expected Output: True
   • Justification: Here, 3 < 4 and 4 < 5, forming a '132' pattern with the numbers 3, 5, and 4.

2. Example 2:

   • Input: nums = [1, 2, 3, 4]
   • Expected Output: False
   • Justification: The sequence is in ascending order, and no '132' pattern is present.

3. Example 3:

   • Input: nums = [9, 11, 8, 9, 10, 7, 9]
   • Expected Output: True
   • Justification: The pattern is formed with 8 < 9 and 9 < 10 in sequence 8, 10, 9.

Constraints:

• n == nums.length
• 1 <= n <= 2 * 10⁵
• -10⁹ <= nums[i] <= 10⁹

Solution

The 132 Pattern problem requires finding a sequence of three numbers in an array such that the first number is smaller than the third number, which is in turn smaller than the second number. In other words, for indices i, j, and k, we need to find a pattern where nums[i] < nums[k] < nums[j] with i < j < k.

To solve this problem efficiently, we use a combination of a stack and a set to track potential candidates for the 132 pattern as we iterate through the array from the end to the beginning. This approach ensures that we can quickly identify and verify the necessary conditions for the pattern.

Step-by-Step Algorithm

1. Initialize Data Structures:

   • Create a SortedSet named second to store potential candidates for the second number in the 132 pattern.
   • Create a stack named st to manage the numbers during the traversal.

2. Iterate Through the Array from End to Beginning:

   • Loop through the array from the last element to the first element (i.e., from right to left).

3. Manage the Stack:

   • For each element nums[i] in the array:
     • While the stack is not empty and the top element of the stack is smaller than nums[i], pop the element from the stack and add it to the second set.

4. Check for the 132 Pattern:

   • If the stack is not empty and the second set is not empty:
     • Iterate through the second set to find the smallest number that is greater than nums[i]. This is done using the higher method of SortedSet which finds the smallest number in the set that is greater than nums[i].
     • If such a number is found, it confirms the presence of the 132 pattern, and we return True.

5. Push the Current Number onto the Stack:

   • Push the current number nums[i] onto the stack to potentially serve as the second number in future iterations.

6. End of Iteration:

   • If the loop completes without finding a 132 pattern, return False.

Algorithm Walkthrough

Using the input nums = [9, 11, 8, 9, 10, 7, 9]:

1. Initialize Data Structures:

   • second = {} (empty set)
   • st = [] (empty stack)

2. Iteration from End to Beginning:

   • i = 6 (nums[i] = 9):

     • Stack is empty.
     • Push 9 onto the stack: st = [9].

   • i = 5 (nums[i] = 7):

     • Stack contains 9, which is greater than 7.
     • Push 7 onto the stack: st = [9, 7].

   • i = 4 (nums[i] = 10):

     • Pop elements from the stack while they are smaller than 10:
       • Pop 7, insert into second: second = {7}, st = [9].
       • Pop 9, insert into second: second = {7, 9}, st = [].
     • Stack is empty.
     • Push 10 onto the stack: st = [10].

   • i = 3 (nums[i] = 9):

     • Stack contains 10, which is greater than 9.
     • Check second for an element greater than 9:
       • second.upper_bound(9) finds 9, which is not greater than 9, so continue.
     • Push 9 onto the stack: st = [10, 9].

   • i = 2 (nums[i] = 8):

     • Stack contains 9, which is greater than 8.
     • Check second for an element greater than 8:
       • second.upper_bound(8) finds 9, which is greater than 8.
       • A 132 pattern is found with 8 < 9 and 9 < 10.
     • Return True.

Code

import java.util.*;

class Solution {

  public boolean find132pattern(int[] nums) {
    TreeSet<Integer> second = new TreeSet<>(); // Set to store potential candidates for the second number
    Stack<Integer> st = new Stack<>(); // Stack to manage the numbers

    int size = nums.length;

    // Iterate through the array from the end to the beginning
    for (int i = size - 1; i >= 0; i--) {
      // Pop elements from the stack that are smaller than the current number
      while (!st.isEmpty() && st.peek() < nums[i]) {
        second.add(st.pop());
      }

      // Check if the current number can be part of a 132 pattern
      if (!st.isEmpty() && !second.isEmpty()) {
        Integer next = second.higher(nums[i]); // Find the smallest number in the set greater than nums[i]
        if (next != null) return true; // If such a number exists, we found a 132 pattern
      }

      // Push the current number onto the stack
      st.push(nums[i]);
    }

    // No 132 pattern found
    return false;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.find132pattern(new int[] { 3, 5, 0, 3, 4 })); // Output: True
    System.out.println(sol.find132pattern(new int[] { 1, 2, 3, 4 })); // Output: False
    System.out.println(sol.find132pattern(new int[] { 9, 11, 8, 9, 10, 7, 9 })); // Output: True
  }
}

Complexity Analysis

• Time Complexity: The time complexity is due to the use of the SortedSet to find the higher bound, which takes time for each insertion and query. The overall complexity is since we iterate through the list once and perform log-time operations on the set.
• Space Complexity: The space complexity is for the stack and set, which can store up to (n) elements in the worst case.

Solution Using Stack

To solve this problem, we need to find a sequence of numbers in the array that follows the pattern 132. Specifically, we need to find indices i, j, and k such that i < j < k and nums[i] < nums[k] < nums[j].

We can achieve this by iterating backward through the array, using a stack to keep track of potential values for nums[k]. By maintaining a variable z to represent the largest value we have found that is smaller than the current number, we can efficiently check for the 132 pattern.

Step-by-Step Algorithm

1. Initialization:

   • Initialize z to Integer.MIN_VALUE to represent the largest value smaller than the current number.
   • Create an empty stack to keep track of potential values for nums[k].

2. Iterate Backward:

   • Loop through the array nums from the end to the beginning.

3. Check for Pattern:

   • For each nums[i], check if it is less than z. If true, return True since we have found a 132 pattern.

4. Update z and Stack:

   • While the stack is not empty and the top of the stack is less than nums[i], update z to the top value of the stack and pop the stack.
   • Push the current nums[i] onto the stack.

5. Return Result:

   • If the loop completes without finding the pattern, return False.

Algorithm Walkthrough

Using the input: [9, 11, 8, 9, 10, 7, 9]

1. Initialization:

   • z = Integer.MIN_VALUE
   • stack = []

2. Iterate Backward:

   • Start from the last element and move to the first.

3. Iteration Details:

   • Step 1: nums[6] = 9
     • Stack is empty, push 9 onto the stack.
     • stack = [9]
   • Step 2: nums[5] = 7
     • 7 is not less than z (which is Integer.MIN_VALUE).
     • Push 7 onto the stack.
     • stack = [9, 7]
   • Step 3: nums[4] = 10
     • 10 is not less than z.
     • While stack top is less than 10, update z and pop from the stack.
       • z = 7, stack = [9]
       • z = 9, stack = []
     • Push 10 onto the stack.
     • stack = [10]
   • Step 4: nums[3] = 9
     • 9 is not less than z (which is 9).
     • While stack top is less than 9, update z and pop from the stack.
       • z = 9, stack = [10]
     • Push 9 onto the stack.
     • stack = [10, 9]
   • Step 5: nums[2] = 8
     • 8 is less than z(9). So, return true. .

Code

import java.util.*;

public class Solution {

  public boolean find132pattern(int[] nums) {
    int z = Integer.MIN_VALUE; // Initialize z to the smallest possible value
    Stack<Integer> stack = new Stack<>(); // Use a stack to simulate an ordered set

    // Iterate backwards through the list
    for (int i = nums.length - 1; i >= 0; i--) {
      if (nums[i] < z) {
        return true; // A '132' pattern is found
      }
      while (!stack.isEmpty() && stack.peek() < nums[i]) {
        z = stack.pop(); // Update z to the largest smaller element
      }
      stack.push(nums[i]); // Add the current number to the stack
    }

    return false;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.find132pattern(new int[] { 3, 5, 0, 3, 4 })); // Expected output: True
    System.out.println(solution.find132pattern(new int[] { 1, 2, 3, 4 })); // Expected output: False
    System.out.println(
      solution.find132pattern(new int[] { 9, 11, 8, 9, 10, 7, 9 })
    ); // Expected output: True
  }
}

Complexity Analysis

Time Complexity

• Building the stack: Each element is pushed onto the stack exactly once and can be popped from the stack at most once. Therefore, the operations of pushing and popping elements are each.
• Overall: Since we iterate through the array exactly once and perform operations for each element (push and pop from the stack), the total time complexity is , where n is the number of elements in the array.

Space Complexity

• Stack Space: In the worst case, all elements are pushed onto the stack, leading to a stack space usage of .
• Variable Space: The additional space used by the variable z is .
• Overall: The overall space complexity is , due to the space used by the stack.