Problem is to check if exists 3 indices with i < j < k and a[i] > a[k] and a[k] < a[j] .
I have learnt the logic and written below solutions with description :
/*there can be multiple pairs of (i,j)
where i pointing to min value and j pointing to max value.
we need to find k where it points to value which is
lesser than max value and greater than max value
but this k should point after j.
these k values can be added to stack.To find the multiple pairs of (i,j),
-- maintain an array of min values starting from the first value and till
that corresponding element.
-- In a loop traverse back from the last element of array till first element:
-- assuming the current index as j , the min array element corresponding to j index is a[i]
-- if the current element is lesser or equal (a[i] = a[j]),
no action to be performed, just proceed for previous element.
-- in a loop check if the stack is not empty and elements in stack are
lesser or equal to this current element
remove those elements from stack.
(mainly checking for element where it meets the condition
a[i] < a[k])
-- if stack is not empty and top value in stack is < cur-element (means a[k] < a[j] (problem condition) where in above loop a[i]<a[k] condition already met.)
found 132 pattern , return true
-- 132 pattern not found. Push the current element to stack.
-- end of loop
--end of loop
-- return false (132 pattern not found all over array elements)Basically there are 4 set statements in a loop:
S1: check if (min_array[j] <= a[j]) which is equivalent to a[i] <= a[j]
proceed to previous element
S2: a loop to remove elements in a stack which are lesser than a[i].
if stack is not empty and top element of stack <= min_array[j]
pop element
S3: if stack is not empty and top value < a[j] (== equivalenet to 2nd condition of problem stmt a[k] < a[j])
found 132 pattern and return true
S4: push the current element to stacknote:
regarding the stack memory: this stack can be a new memory or
some part of input array can be used to maintain stack.
e.g while traversing back. a[n] can be pushed back at the same location.
a[n-1] can point to a[n-1] or any element where the index is lesser than n-1.case 1:
input = {1,2,3,4}
array of min values = {1,1,1,1}
traversing back from a[3]:
1) a[3] = 4 here assumption is j = 3,
as this the last element , there is no k.
S1: min-array[3] (1) < a[3] --> false
S2: stack empty -> no loop entry
S3: stack empty --> false
S4: push 4
2) a[2] = 3 (j=2).
S1: min_array[2] (1) < a[2] --> false
S2: top of stck is 4 > min_array[2] --> no loop
S3: top of stk is 4 > a[2] --> false
3) a[1] = 2 (j=1).
S1: false
S2 no loop and S3 false
S4: push to stack
end while
no 132 pattern found, return falsecase 2:
input = {3,1,4,2}
array of min values = {3,1,1,1}
traversing back from a[3]:
1) a[3] = 2 (j=3)
S1 false, S2 no loop, S3 false
S4: push 2
2) a[2] = 4 (j=2)
S1: false
S2: top (2) > min_array[2] (1) :
S3: top (2) < a[j] (4):
132 pattern found and return true
*/bool find132pattern(int* nums, int numsSize){
int j, k;
int mina[numsSize];
if (numsSize < 3)
return 0;
mina[0] = nums[0];
for (j=1; j<numsSize; j++){
if (nums[j] < mina[j-1])
mina[j] = nums[j];
else
mina[j] = mina[j-1];
}
/* traversal from last to first */
j = numsSize-1;
k = numsSize; /* stack starting from numsSize-1 and grows down */
while (j>0) { /* first element check not required */
/* check if the current element is lesser or equal of mina[j] */
if (nums[j] <= mina[j]){ j--; continue;}
/* remove stack elements which are lesser than min array[j]
that is elements which are not meeting the problem condition1
a[i] < a[k] */
while ((k < numsSize) && (nums[k] <= mina[j]))
k++;
/* if top value is less than a[j], ie
problem condition 2 : a[k] < a[j] */
if ((k != numsSize) && (nums[k] < nums[j]))
return 1;
nums[--k] = nums[j];
j--;
}
return 0;
}
There is another solution where we can avoid min_array.
Below is the solution:
/* stack starting from nums[numsSize-1] and grows downward.
traverse from backward.
If stack not empty, find the element from the stack which is lesser than current element. This meets the condition (a[j] > a[k])
goto previous element,
check if the condition satisfies (a[i] < a[k])
else repeat the process,
push each element in stack
*/
bool find132pattern(int* nums, int numsSize){
int j, k;
int stk_ele=INT_MIN;
if (numsSize < 3)
return 0;
/* traversal from last to first */
j = numsSize-1;
k = numsSize; /* stack starting from numsSize-1 and grows down */
while (j>=0) {
/* check if a[k] > a[i] ,
initially this stk element is assigned with the INT_MIN
This condition will always be false when j is pointing to last element */
if (stk_ele > nums[j])
return 1;
/* remove stack elements which are lesser than a[j]
that is elements which are meeting the problem condition2
a[j] > a[k] */
while ((k < numsSize) && (nums[j] > nums[k])){
stk_ele = nums[k];
k++;
}
k--;
nums[k] = nums[j]; j--;
}
return 0;
}
