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].
Analysis: Firstly
let’s analyze this problem with the brute-force solution: All elements in the
array are scanned one by one. When an element is scanned, we take is as A[j], and check whether there is a smaller
element on its left side (A[i]), and
a greater element on its right side (A[k]).
Since it takes O(n)
time to scan numbers on two sides of each A[j],
the overall time of this solution is O(n2)
on an array with n elements.
Solution 1: O(n) time efficiency with O(n) space consumption
As our analysis above, for each element A[j], we need to know whether there is a
smaller element on its left side. If there is not a smaller element on the left
side, A[j] itself is the smallest of
all elements from the leftmost element to A[j].
If there is a smaller element on the left side, the smallest of all elements
from the leftmost element to A[j] is
on the left side of A[j].
Therefore, 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.
This solution can be implemented with the following C/C++
code:
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 consumption
In order to find an even more efficient solution, let’s scan
all elements in an array and try to find three increasing elements. The array {3,
2, 5, 1, 4, 7, 9, 6, 8} is taken as an example to simulate the process.
At first, all elements A[i],
A[j], and A[k] have not been found, so three indexes i, j, and k are initialized as -1.
The number 3 is the first number to be scanned, and A[i] is updated as 3.
The next number to be scanned is the number 2. Notice that 2
is less than 3, and it is a better candidate of A[i]. The less A[i] is, the
larger range A[j] and A[k] will have. Therefore, A[i] is updated as 2.
Let’s continue to scan the next number 5. Since 5 is greater
the current A[i], it is a candidate
of A[j]. A[j] is updated as 5.
The number 1 is scanned in the next round. Because 1 is less
than the current A[
j], it cannot be
A[
k]. Additionally, the number 1 is a
candidate to be A[
i] or A[
j] in the future since it is less than
the current A[
i] and A[
j]. However, neither A[
i] nor A[
j] can be updated as 1 at this time. If A[
i] is updated as 1, A[
i]<A[
j] but
i>
j. If A[
j] is updated as 1, A[
i]>A[
j]. Therefore, we store the number 1 into another variable named
t.
We move on to scan the next number 4. Notice that the number
4 is less than A[j] again. At this
time we have two numbers 1 (the stored variable t) and 4, so we have a new pair of numbers to be A[i] and A[j]. A[i] and A[j] are updated as 1 and 4 respectively.
The next number, 7, is greater than the current A[j], so A[k] is updated as 7. The process terminates.
The following table summarizes the step-by-step analysis
above:
Step
|
Scanned Number
|
A[i]
|
A[j]
|
A[k]
|
t
|
Operation
|
1
|
3
|
3
|
-1
|
-1
|
-1
|
Update A[i]
|
2
|
2
|
2
|
-1
|
-1
|
-1
|
Update A[i]
|
3
|
5
|
2
|
5
|
-1
|
-1
|
Update A[j]
|
4
|
1
|
2
|
5
|
-1
|
1
|
Update t
|
5
|
4
|
1
|
4
|
-1
|
-1
|
Update A[i], A[j] and t
|
6
|
7
|
1
|
4
|
7
|
-1
|
Update A[k]. Terminate.
|
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.
With our step-by-step analysis, we could implement this
solution with the following C++ code:
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;
}
More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.
The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.
