Jobs

Interviews

Discussions

132 Pattern

Medium

Asked by:

More companies

66 views

Topics:

ArraysStacks

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 * 10⁵
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

132 Pattern

Medium

Asked by:

More companies

66 views

Topics:

ArraysStacks

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 * 10⁵
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the `nums` array? Can I assume they are integers?
Can the input array `nums` be empty or null?
If multiple 132 patterns exist, is it sufficient to return `true` as soon as the first one is found?
Are duplicate numbers allowed in the array, and if so, how do they affect the definition of the 132 pattern?
What is the expected behavior if the input array is sorted in ascending or descending order?

Brute Force Solution

Approach

The brute force approach to finding a 132 pattern is like trying every possible combination. We're searching for three numbers where the first is smaller than the third, and the third is smaller than the second. We check every single group of three numbers to see if they fit this pattern.

Here's how the algorithm would work step-by-step:

First, pick a number. Let's call it the 'first' number.
Then, pick another number that comes after the 'first' number. Let's call it the 'second' number.
Finally, pick a third number that comes after the 'second' number. Let's call it the 'third' number.
Now, check if the 'first' number is smaller than the 'third' number, AND if the 'third' number is smaller than the 'second' number.
If both of those are true, then you've found the pattern! The search is done.
If not, pick a different 'third' number and check again.
If you've tried all the possible 'third' numbers, pick a different 'second' number and start picking 'third' numbers again.
If you've tried all the possible 'second' numbers after a certain 'first' number, then pick a different 'first' number and repeat the whole process.
Keep doing this until you either find the pattern or you've checked every possible combination of three numbers.

Code Implementation

def has_132_pattern_brute_force(numbers):
    list_length = len(numbers)
    for first_index in range(list_length):
        for second_index in range(first_index + 1, list_length):
            # Need to check for third numbers after the second number.
            for third_index in range(second_index + 1, list_length):
                # Check if the 132 pattern exists

                if numbers[first_index] < numbers[third_index] and numbers[third_index] < numbers[second_index]:
                    return True

    return False

Big(O) Analysis

Time Complexity

O(n^3) – The brute force approach involves iterating through the array three times using nested loops to find the '1', '3', and '2' elements. The outermost loop selects the '1', the middle loop selects the '3', and the innermost loop selects the '2'. For each possible '1', we iterate through the remaining elements to find a potential '3', and for each '3', we iterate again to find a potential '2'. This leads to approximately n * n * n operations, which simplifies to O(n^3).

Space Complexity

O(1) – The brute force approach described only uses a few integer variables to store the indices of the first, second, and third numbers being compared. The number of such variables is constant, regardless of the input array's size (N). Therefore, the algorithm's auxiliary space complexity is O(1), indicating constant space usage.

Optimal Solution

Approach

The core idea is to efficiently identify the '3' in the 132 pattern. We maintain a stack of potential '2' values, ensuring that we check for the pattern in reverse order which allows for efficient discovery.

Here's how the algorithm would work step-by-step:

Imagine you're walking backwards through the list of numbers.
Keep track of the largest number you've seen so far that could be the '2' in our pattern.
Use a temporary holding area for numbers that could potentially be the '2', but only keep the ones that are useful to us.
As you walk backward, check each number to see if it could be the '1' in the 132 pattern. To be the '1', it must be smaller than the largest potential '2' you've seen so far.
If you find a number that fits the '1' role, you've found the 132 pattern!
If you don't find a suitable '1', continue walking backwards, updating the largest potential '2' as you go.
The stack helps maintain a descending ordered list that helps narrow down potential '2' values.

Code Implementation

def find132pattern(numbers) -> bool:
    stack_of_potential_second_values = []
    maximum_second_value = float('-inf')

    for i in range(len(numbers) - 1, -1, -1):
        # Check if the current number can be the '1'
        if numbers[i] < maximum_second_value:
            return True

        # Maintain a decreasing stack for potential '2' values
        while stack_of_potential_second_values and numbers[i] > stack_of_potential_second_values[-1]:
            # Update max_second_value with viable stack values
            maximum_second_value = stack_of_potential_second_values.pop()

        stack_of_potential_second_values.append(numbers[i])

    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n once, from right to left. In each iteration, it performs a constant number of operations: comparing the current element with a variable called second, pushing elements onto the stack, and popping elements from the stack. While there is a while loop inside the for loop, the while loop only runs at most n times in total because each element is pushed and popped from the stack at most once. Therefore, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm uses a stack to store potential '2' values. In the worst-case scenario, where the input array is sorted in descending order, all N elements could be pushed onto the stack. This creates an auxiliary data structure (the stack) that requires space proportional to the input size N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty or null input array	Return false immediately since a 132 pattern requires at least three elements.
Array with less than three elements	Return false immediately as a 132 pattern cannot exist with fewer than three elements.
Array with all elements identical	Return false because nums[i] < nums[k] < nums[j] cannot be satisfied with identical elements.
Array sorted in ascending order	Return false, as it's impossible to find nums[i] < nums[k] < nums[j] where i < j < k.
Array sorted in descending order	Iterate through the array, the middle number must be largest, checking previous and succeeding values for condition.
Array with large range of integer values (positive and negative)	The algorithm should handle both positive and negative integers correctly without overflow issues.
Very large input array (performance)	The algorithm should have a time complexity better than O(n^3) to avoid exceeding time limits with large inputs, preferably O(n) or O(n log n).
Input contains integer overflow condition with mathematical operations.	Avoid potential integer overflow issues by not performing calculations that could exceed the maximum integer value, or use a larger data type like long if necessary.

Empty or null input array

How to Handle:

Return false immediately since a 132 pattern requires at least three elements.

Array with less than three elements

How to Handle:

Return false immediately as a 132 pattern cannot exist with fewer than three elements.

Array with all elements identical

How to Handle:

Return false because nums[i] < nums[k] < nums[j] cannot be satisfied with identical elements.

Array sorted in ascending order

How to Handle:

Return false, as it's impossible to find nums[i] < nums[k] < nums[j] where i < j < k.

Array sorted in descending order

How to Handle:

Iterate through the array, the middle number must be largest, checking previous and succeeding values for condition.

Array with large range of integer values (positive and negative)

How to Handle:

The algorithm should handle both positive and negative integers correctly without overflow issues.

Very large input array (performance)

How to Handle:

The algorithm should have a time complexity better than O(n^3) to avoid exceeding time limits with large inputs, preferably O(n) or O(n log n).

Input contains integer overflow condition with mathematical operations.

How to Handle:

Avoid potential integer overflow issues by not performing calculations that could exceed the maximum integer value, or use a larger data type like long if necessary.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the `nums` array? Can I assume they are integers?
Can the input array `nums` be empty or null?
If multiple 132 patterns exist, is it sufficient to return `true` as soon as the first one is found?
Are duplicate numbers allowed in the array, and if so, how do they affect the definition of the 132 pattern?
What is the expected behavior if the input array is sorted in ascending or descending order?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, pick a number. Let's call it the 'first' number.
Then, pick another number that comes after the 'first' number. Let's call it the 'second' number.
Finally, pick a third number that comes after the 'second' number. Let's call it the 'third' number.
Now, check if the 'first' number is smaller than the 'third' number, AND if the 'third' number is smaller than the 'second' number.
If both of those are true, then you've found the pattern! The search is done.
If not, pick a different 'third' number and check again.
If you've tried all the possible 'third' numbers, pick a different 'second' number and start picking 'third' numbers again.
If you've tried all the possible 'second' numbers after a certain 'first' number, then pick a different 'first' number and repeat the whole process.
Keep doing this until you either find the pattern or you've checked every possible combination of three numbers.

Code Implementation

def has_132_pattern_brute_force(numbers):
    list_length = len(numbers)
    for first_index in range(list_length):
        for second_index in range(first_index + 1, list_length):
            # Need to check for third numbers after the second number.
            for third_index in range(second_index + 1, list_length):
                # Check if the 132 pattern exists

                if numbers[first_index] < numbers[third_index] and numbers[third_index] < numbers[second_index]:
                    return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you're walking backwards through the list of numbers.
Keep track of the largest number you've seen so far that could be the '2' in our pattern.
Use a temporary holding area for numbers that could potentially be the '2', but only keep the ones that are useful to us.
As you walk backward, check each number to see if it could be the '1' in the 132 pattern. To be the '1', it must be smaller than the largest potential '2' you've seen so far.
If you find a number that fits the '1' role, you've found the 132 pattern!
If you don't find a suitable '1', continue walking backwards, updating the largest potential '2' as you go.
The stack helps maintain a descending ordered list that helps narrow down potential '2' values.

Code Implementation

def find132pattern(numbers) -> bool:
    stack_of_potential_second_values = []
    maximum_second_value = float('-inf')

    for i in range(len(numbers) - 1, -1, -1):
        # Check if the current number can be the '1'
        if numbers[i] < maximum_second_value:
            return True

        # Maintain a decreasing stack for potential '2' values
        while stack_of_potential_second_values and numbers[i] > stack_of_potential_second_values[-1]:
            # Update max_second_value with viable stack values
            maximum_second_value = stack_of_potential_second_values.pop()

        stack_of_potential_second_values.append(numbers[i])

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return false immediately since a 132 pattern requires at least three elements.
Array with less than three elements	Return false immediately as a 132 pattern cannot exist with fewer than three elements.
Array with all elements identical	Return false because nums[i] < nums[k] < nums[j] cannot be satisfied with identical elements.
Array sorted in ascending order	Return false, as it's impossible to find nums[i] < nums[k] < nums[j] where i < j < k.
Array sorted in descending order	Iterate through the array, the middle number must be largest, checking previous and succeeding values for condition.
Array with large range of integer values (positive and negative)	The algorithm should handle both positive and negative integers correctly without overflow issues.
Very large input array (performance)	The algorithm should have a time complexity better than O(n^3) to avoid exceeding time limits with large inputs, preferably O(n) or O(n log n).
Input contains integer overflow condition with mathematical operations.	Avoid potential integer overflow issues by not performing calculations that could exceed the maximum integer value, or use a larger data type like long if necessary.

Empty or null input array

How to Handle:

Return false immediately since a 132 pattern requires at least three elements.

Array with less than three elements

How to Handle:

Return false immediately as a 132 pattern cannot exist with fewer than three elements.

Array with all elements identical

How to Handle:

Return false because nums[i] < nums[k] < nums[j] cannot be satisfied with identical elements.

Array sorted in ascending order

How to Handle:

Return false, as it's impossible to find nums[i] < nums[k] < nums[j] where i < j < k.

Array sorted in descending order

How to Handle:

Iterate through the array, the middle number must be largest, checking previous and succeeding values for condition.

Array with large range of integer values (positive and negative)

How to Handle:

The algorithm should handle both positive and negative integers correctly without overflow issues.

Very large input array (performance)

How to Handle:

The algorithm should have a time complexity better than O(n^3) to avoid exceeding time limits with large inputs, preferably O(n) or O(n log n).

Input contains integer overflow condition with mathematical operations.

How to Handle:

Avoid potential integer overflow issues by not performing calculations that could exceed the maximum integer value, or use a larger data type like long if necessary.