Increasing Triplet Subsequence

Question is:

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

Thinking it how to do, then tried to pen down some logic:

Then tried the below function:

bool increasingTriplet(int* a, int n){
int ii;
int i=0, j=1, k=2,validijpair=0;
if (n < 3)
return 0;
while (k != n) {
/* checking for 1st condition */
if (a[i] < a[j]) {
/* checking for 2nd condition */
if (a[j]<a[k])
return 1;
/* check if we can update j*/
if (a[i] < a[k])
j = k;
/* in else condition do we need to update i to k then search for j and k both ?? , skipping as of now */
printf(“1. %s(%d) i %d, j %d, k %d, num[%d] %d, num[%d] %d, num[%d] %d\n”,
__func__,__LINE__,i,j,k,i, a[i],j,a[j],k,a[k]);
} else {
i= j; j++;
printf(“2. %s(%d) i %d, j %d, k %d, num[%d] %d, num[%d] %d, num[%d] %d\n”,
__func__,__LINE__,i,j,k,i, a[i],j,a[j],k,a[k]);
}
k++;
}
return 0;
}

In above solution, I found a[i], a[j], but not a[k] and the current element is lesser than existing a[i]. If we directly update that lesser element to a[i], there may not be a[j] which should meet the condition of a[i]<a[j],
then thought through it and below is my next solution:

bool increasingTriplet(int a, int n){
int ii;
int i=0, j=1, k=2,minindex;
if (n < 3)
return 0;
minindex = i;
while (k != n) {
/ checking for 1st condition /
if (a[i] < a[j]) {
/ checking for 2nd condition /
if (a[j]<a[k])
return 1;
/ check if we can update j/
if (a[minindex] < a[k]) {
i = minindex; j = k;
}
else if (a[i] < a[k])
j = k;
else
minindex = k;
/ in else condition do we need to update i to k then search for j and k both , to update this i and j, maintain minindex. In next iteration if we find another number greater than a[minindex] update i and j./
// printf(“1. %s(%d) i %d, j %d, k %d, num[%d] %d, num[%d] %d, num[%d] %d\n”,
// func,LINE,i,j,k,i, a[i],j,a[j],k,a[k]);
} else {
i= j; j++; minindex = i;
// printf(“2. %s(%d) i %d, j %d, k %d, num[%d] %d, num[%d] %d, num[%d] %d\n”,
// func,LINE,i,j,k,i, a[i],j,a[j],k,a[k]);
}
k++;
}
return 0;
}

Learned other solutions from the internet. One very simple solution: first find the smallest number, then find the second smallest number, then if 2 numbers are found and for any next biggest number goal achieved.

/* we find the smallest and 2nd smallest numbers and if there is any bigger number than those, return true */
bool increasingTriplet(int* a, int n){
int k=0;
int i=0, j=0, min2_found = 0;

if (n < 3)
return 0;
while (k != n) {
/* checking for smallest num */
if (a[k] <= a[i]) {
i = k; }
/* second smallest num */
else if (!min2_found || (a[k] <= a[j])) {
j = k; min2_found = 1; }
else
return 1;
k++;
}
return 0;
}

Another solution based on Longest Increasing Sequence:

/* based on longest increasing sequence (LIS),
get the array of 3 longest numbers (result array).
If successful in getting array, return 1, else return 0
How to get the result array:
— Initially directly assign the first element.
— check the next elements with result array of first element , if lesser, update it, else append to result array and increase the size of the array
— repeat till the end of array.
*/
bool increasingTriplet(int* a, int n){
int res[3], l, r, res_size= 0, ii, mid;

for (ii=0; ii<n; ii++){
l = 0; r = res_size;
while (l<r){ /* for first element , res_size is 0. so while is not executed */
mid = l+(r-1)/2;
if (res[mid] < a[ii])
l = mid + 1;
else
r = mid;
}
res[l] = a[ii];
if (l == res_size) res_size++;
if (res_size == 3) return 1;
}
return 0;
}

Your comments please.

--

--

www.linkedin.com/in/jyothivs

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store