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.
Your second solution is incorrect. e.g. try using the array 10 50 49 48 11 12. The answer is 10, 11, 12, of course.
ReplyDeleteFelipe, his question is a little unclear. The three indices must in an unbroken sequence. You can infer this from his article, though it is never made explicitly clear. So the second solution does work.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteI think the problem meant to say that the numbers can be in any way, whether sequential or not. Note the piece of code "else if(nums[index] < nums[*j])" - he is clearly skipping a few numbers in between which don't match his criteria. Anyways, for those interested I wrote a solution which does not care if the elements are sequential or not. Code is in python.
ReplyDeletehttps://github.com/vikhyath/python-runs/blob/master/increasing-elements/inc.py
This comment has been removed by the author.
Deleteyour code fails for this input : [40, 1, 2, 5]
DeleteThis comment has been removed by the author.
ReplyDeletepublic boolean threeIntegers(int prevJ, int arrG[], int retArr[]){
ReplyDelete// retArr contains i,j,k at index 0,1,2 and prevJ is 0 initially
//arrG contains the given array
int i = prevJ, k = 0;
while(arrG[i] >= arrG[i+1])
i++;
if(prevJ!=0 && arrG[i+1]> arrG[prevJ]){
retArr[2] = i+1;
return true;
}
retArr[k++] = i++;
while(arrG[i]> arrG[i+1] && arrG[i+1] > retArr[k-1] ){
i++;
}
retArr[k] = i;
return threeIntegers(retArr[k], arrG, retArr);
}
complexity is O(n) amortised( as it requires a few recursive calls)
check this alco for c# interview questions @ http://skillgun.com
ReplyDeleteThe second algorithm fails for simple input like the following
ReplyDelete{6, 1, 5, 2, 4} or
{4, 1, 5, 3, 2}
@Vikhyath Reddy, Checked out your solution also. It fails for the following test case.
ReplyDeleteCheckout the output of your program here.
http://ideone.com/ukm5gb
ReplyDeleteThank you sharing wondefull Information
I also found Various useful links related to Devops, Docker & Kubernetes
Kubernetes Kubectl Commands CheatSheet
Introduction to Kubernetes Networking
Basic Concept of Kubernetes
Kubernetes Interview Question and Answers
Kubernetes Sheetsheat
Docker Interview Question and Answers
Docker Basic Tutorial