Problem: 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:
Input: nums = [1,0,1,4,3] Output: true Explanation: There is a 132 pattern in the sequence: [1, 4, 3].
Approach: To understand the optimal approach, we need to start with the very basic brute force approach which is as follows:
- FOR i = 0 to n - 2
- FOR j = i + 1 to n - 1
- FOR k = j + 1 to n
- IF nums[j] > nums[k] AND nums[k] > nums[i]
- RETURN true
- RETURN false
Hopefully the above approach is clear. There is nothing to explain about the above simple approach where we are examine every triplet (i, j, k) where i <j < k to check for the given condition. This approach is expensive as you can see it will take O(n^3) time. Let's make it better!
Instead of having three loop, we will have only two loops. We are not going to have loop for 'i' which we had in the above approach but then how we will compare nums[i] and nums[k] (nums[i] < nums[k] right!). Basically when we have a case of nums[j] > nums[k], we want to see if there is some 'i' in the range [0...j - 1] which satisfy condition nums[i] < nums[k]. If we look closely this is same as Min(nums[0]...nums[j - 1]) < nums[k] as if the minimum number in that range [0...j-1] is not smaller than nums[k] then no number in [0...j - 1] will satisfy this condition. Hence it is safe to say that the condition is not met for current j and k.
Now this problem is reduced to how to get minimum number in the range [0...j - 1]. To achieve this we can preprocess the array nums and save the minimum numbers in an additional array say minVals. minVals[i] will have the Min(nums[0],...[nums[i]). Here is how we can fill minVals in linear time:
- minVals[0] = nums[0]
- FOR i = 1 to n
- minVals[i] = Min(minVals[i - 1], nums[i])
Once we are done with the above preprocessing, things will become simple and our loops now looks like:
- FOR j = 1 to n - 1
- FOR k = j + 1 to n
- IF nums[j] > nums[k] AND nums[k] > minVals[j - 1]
- RETURN true
- RETURN false
This is a definite improvement in the first approach and it will solve the problem in O(n^2) time only but can we do better still? Let's now move to our most optimal approach now.
What we were doing in the second approach is we were have two loops one is for j and one is for k. To get rid of the loop 'i', we did the preprocessing to have the minimum value stored for every prefix. Now if we want to get rid of another loop which is say the loop for k, we need to see what we are doing there. Basically we are trying to find a k in range [j + 1...n] which will satisfy conditions nums[k] > nums[i] (minVals[j - 1]) and nums[k] < nums[j]. What this is telling us is we need to find maximum number of [nums[j + 1]...nums[n] which is less than nums[j] and then we can compare this max number with minVals[j - 1]. Here we can't do any preprocess which we did to replace nums[0]...nums[j - 1] as it is just not about finding max or min.
What we can do here is we can maintain a stack in which we fill the element from [n to 0] in a decreasing order. Basically the top of the stack will have the minimum number of the numbers in the stack. Something like this:
We will have a loop from j = n to 1 (we need to get maximum from j + 1 to n) and maintain the stack in the above way. Say num[j] = 8 then the above stack will change to:
If you see we are making sure that we are getting the maximum number in the stack which is less than nums[j] as we are popping out all the elements in the stack which are less than nums[j] before pushing nums[j] to stack and these are happening in an increasing order. While popping the element out, we can also check if top of the stack is greater than minVals[j - 1]. If we find such element in the stack, we can just return true. In this way we can solve this problem in linear time.
That's all!
Implementation in C#:
public static bool Find132pattern(int[] nums)
{
if (nums?.Length <= 2)
{
return false;
}
int[] minVal = new int[nums.Length];
minVal[0] = nums[0];
for (int i = 1; i < nums.Length; ++i)
{
minVal[i] = Math.Min(minVal[i - 1], nums[i]);
}
Stack<int> stack = new Stack<int>();
for (int i = nums.Length - 1; i > 0; --i)
{
while (stack.Count > 0 && nums[i] > stack.Peek())
{
if (stack.Peek() > minVal[i - 1])
{
return true;
}
stack.Pop();
}
stack.Push(nums[i]);
}
return false;
}
Complexity: O(n)
No comments:
Post a Comment