Problem: Given an array of integers A, please find three indexes i, j, k, such that i<j<k and A[i]<A[j]<A[k].
Solution 1: O(n) time efficiency with O(n) space consumption
The strategy of this solution is to store as less value to A[i] and A[j] as possible, in order to enlarge the value range for steps in the future.
Solution 1: O(n) time efficiency with O(n) space consumption
we could construct an auxiliary array B. The element B[j] stores the index of the smallest element of elements from the leftmost element to A[j]. The array B can be constructed based on elements in A from left to right.
Similarly, we could also construct another auxiliary array C. The element C[j] stores the index of the greatest element of elements from the rightmost element to A[j]. The array C can be constructed based on elements in A from right to left.
When an element A[j] is scanned, the index j is compared with B[j] and C[j]. if B[j]<j (there is a smaller element on the left side) and j<C[j] (there is a greater element on the right side), three increasing elements have been found.
void increasingIndex_1(int* nums, int length, int* i, int* j, int* k)
{
if(nums == NULL || length <= 0 || i == NULL || j == NULL || k == NULL)
return;
int* minIndex = new int[length];
int index = 0;
minIndex[0] = 0;
int t;
for(t = 1; t < length; ++t)
{
if(nums[t] < nums[index])
index = t;
minIndex[t] = index;
}
int* maxIndex = new int[length];
index = length - 1;
for(t = length - 1; t >= 0; --t)
{
if(nums[t] > nums[index])
index = t;
maxIndex[t] = index;
}
for(t = 1; t < length - 1; ++t)
{
if(minIndex[t] < t && maxIndex[t] > t)
break;
}
if(t < length - 1)
{
*i = minIndex[t];
*j = t;
*k = maxIndex[t];
}
else
{
*i = *j = *k = -1;
}
delete[] minIndex;
delete[] maxIndex;
}
Solution 2: O(n) time efficiency with O(1) space consumptionThe strategy of this solution is to store as less value to A[i] and A[j] as possible, in order to enlarge the value range for steps in the future.
void increasingIndex_2(int* nums, int length, int* i, int* j, int* k)
{
if(nums == NULL || length <= 0 || i == NULL || j == NULL || k == NULL)
return;
*i = *j = *k = -1;
int backup = -1;
int index;
for(index = 0; index < length; ++index)
{
if(*i == -1)
{
*i = index;
}
else if(*j == -1)
{
if(nums[index] > nums[*i])
*j = index;
else
*i = index;
}
else if(nums[index] > nums[*j])
{
*k = index;
break;
}
else if(nums[index] < nums[*j])
{
if(backup != -1)
{
if(nums[index] > nums[backup])
{
*i = backup;
*j = index;
backup = -1;
}
else if (nums[index] < nums[backup])
{
backup = index;
}
}
else if(nums[index] < nums[*j])
backup = index;
}
}
if(index == length)
*i = *j = *k = -1;
}
Read full article from Coding Interview Questions: No. 42 - Three Increasing Elements in an Array