Thursday, February 21, 2013

No. 42 - Three Increasing Elements in an Array


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.

12 comments:

  1. 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.

    ReplyDelete
  2. Felipe, 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.

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. I 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.

    https://github.com/vikhyath/python-runs/blob/master/increasing-elements/inc.py

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. your code fails for this input : [40, 1, 2, 5]

      Delete
  5. This comment has been removed by the author.

    ReplyDelete
  6. public boolean threeIntegers(int prevJ, int arrG[], int retArr[]){
    // 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)

    ReplyDelete
  7. The second algorithm fails for simple input like the following

    {6, 1, 5, 2, 4} or
    {4, 1, 5, 3, 2}

    ReplyDelete
  8. @Vikhyath Reddy, Checked out your solution also. It fails for the following test case.
    Checkout the output of your program here.
    http://ideone.com/ukm5gb

    ReplyDelete