132 Pattern LeetCode

Picture a bookshop that receives, loans out, and restocks books in an ongoing cycle. This pattern is similar to the 132 sequences observed in certain array sequences:

  1. First comes the arrival of new books (i), followed by their lending (j) and their return (k).

  2. Much like with arrays, this routine functions best when everything lines up properly. The order has to be followed, such as acquiring stock ahead of demand while maintaining inventory levels through replenishment after borrowing.

By recognizing these patterns within a bookstore’s operations, it becomes possible to streamline processes for restocking to ensure the process goes smoothly.

Problem statement

A 132 pattern is a sequence of three integers in an array. Within array sequences, this pattern [i, j, k] occurs, which dictates that i should precede j; meanwhile, k should be greater than i and smaller than j, making a very specific array composition. The pattern holds if the indexes i, j, and k follow these rules:

  • i < j < k

  • nums[i] < nums[k] < nums[j]

If both these conditions are followed, we return True. The illustration below depicts an example of this:

Example of a 132 problem
Example of a 132 problem

In this example, i (index 1) is less than j (index 2) and both are less than k (index 3). The value of nums[i] (1) is less than nums[k] (2), and both are less than nums[j] (4). Another example of this would be nums = [-1,3,2,0]. In this case, i is index 0, j is index 1, and k is index 2. So, the rules below will be followed:

  • 0 < 1 < 2 (i < j < k)

  • -1 < 2 < 3 (nums[i] < nums[k] < nums[j]

Therefore, this list also contains a 132 pattern.

Knowledge test

Q

Which of the following conditions must be met to identify a 132 pattern in an array nums of length n?

A)

i < k < j and nums[i] < nums[k] < nums[j]

B)

i < j < k and nums[i] < nums[j] < nums[k]

C)

j < i < k and nums[k] < nums[i] < nums[j]

D)

k < j < i and nums[j] < nums[k] < nums[i]

Algorithm

This algorithm begins by defining variables:

  • length that determine the array’s size

  • An empty stack to serve as a data structure

  • k set initially to negative infinity, representing an invalid value

  • The nums array that stores the numbers

We begin by reverse-iterating through the nums array. We then check if the element at index i is less than k. If so, This marks the existence of the pattern, and we return True. If not:

  • Check if stack isn’t empty, and the current element is greater than the top element in the stack. If so, update k by removing elements from the stack to ensure k is greater than the first element i and smaller than the second element j.

  • This element is then appended to the stack for the next iteration.

If the loop ends without a pattern, we return False.

The initial values of the variables
The initial values of the variables
1 of 4

Educative 99 helps you solve complex coding problems like the 132 pattern by recognizing patterns and applying the right algorithms.

Code example

The code for this problem is provided below:

def find132pattern(nums):
    length = len(nums)
    stack = []
    k = float('-inf')
    
    for i in range(length - 1, -1, -1):
        if nums[i] < k:
            return True
        while stack and nums[i] > stack[-1]:
            k = stack.pop()
        stack.append(nums[i])
    
    return False
print(find132pattern([1, 2, 3, 4]))
print(find132pattern([3, 1, 4, 2]))
print(find132pattern([-1, 3, 2, 0]))

Coding explanation

This code can be explained below:

  • Line 1: Here, we have the definition of the find132pattern function, which takes nums (a list of numbers) as a parameter.

  • Line 2: The code stores the size of the list in length.

  • Line 3: The code defines an empty list called stack.

  • Line 4: The code initializes k to negative infinity. This will store potential k values when we iterate through nums.

  • Line 6: We iterate through the elements inside nums. It starts from the last element in the list and decrements until it reaches the first element.

  • Lines 7–8: We check whether the current element nums[i] is less than the k value. If it is, this is the 132 pattern, and we return True.

  • Lines 9–10: We utilize a while loop to compare nums[i] with the elements in the stack. We check if the stack isn’t empty, and we then check if the current element is greater than the top element in the stack. If these conditions are met, this may be a 132 pattern. The k value is then updated by popping the value from the stack to keep track of the largest value that may be used as k in the 132 pattern.

  • Line 11: After this loop, the value of nums[i] is appended to stack. This keeps track of potential j values as we repeatedly loop through the list.

  • Line 13: If we iterate through the whole list without finding a 132 pattern, return False.

  • Lines 15–17: This is the code to call the function.

Time complexity

The time complexity for this code is O(n)O(n), in whichnnrepresents the length of nums. This is because it only loops through the array once in reverse and performs stack operations that don’t exceed the array’s length.

Space complexity

The space complexity for this code is O(n)O(n), primarily due to stack, which scales with the size of the nums, and stores all potential elements in some cases.


Free Resources

Copyright ©2025 Educative, Inc. All rights reserved