Make delicious recipes!

Three increasing numbers such that
i < j < k
and
arr[i] < arr[j] < arr[k]



Puzzle: Given an array of integers, find three indexes i,j,k such that i<j<k and arr[i]<arr[j]<arr[k]


Solution:
As always, solving a smaller problem always sheds more light on solving the bigger problem.
If only two such variables were to be found, then its pretty simple.
Just keep track of the minimum element till now and whenever a higher element is found, print the pair.
Note that the problem is to find just any one such pair, not all the pairs.

Similarly, to find any one such triplet, we have to keep track of two minimums - arr[i] and arr[j] till arr[k] is found.
However, after two minimums have been selected and a new all-time minimum is found, how to handle that?
It is important to handle this all-time minimum because all the remaining numbers may be smaller than the current two minimums but may be larger than this all-time minimum.
For example:
    [ 20, 30, 5, 6, 1, 7 ]
               ¶cursor
    current-series = 20,30
    new minimum    = 5

This is solved by storing this new minimum as a potential start of a new series.
If another number is found which is less than the series started by current two minimums but is larger than potential minimum, then we can discard the current series in favor of current number and the previous all-time minimum.

    [ 20, 30, 5, 6, 1, 7 ]
                  ¶cursor
    current-series = 20,30
    potential min  = 5
    current num    = 6
    => discard current-series and replace it with potential min and current num
    => current-series = 5, 6


With the above considerations in mind, an O(n) solution is as follows:


public class ThreeIncreasingNumbers 
{

    public static void main(String[] args) 
    {
        int numCount = 7;
        int arr[] = getRandomNums (numCount);

        
        // threeNums holds the solution
        int [] threeNums = new int [] {-1, -1, -1};
        threeNums[0] = 0;
        
        // potentialMin holds the start of a new sequence whose first number
        // is smaller than threeNums[0]
        int potentialMin = -1;
        
        
        for (int i=1; i<numCount; i++)
        {
            if (arr[i] >= arr[threeNums[0]]) // number larger than the one at threeNums[0]
            {
                if (threeNums[1] == -1 || arr[i] <= arr[threeNums[1]]) // found second number
                {
                    threeNums[1] = i;
                }
                else
                {
                    // found third number, print the solution
                    System.out.println ();
                    System.out.println(threeNums[0] + ", " + threeNums[1] + ", " + i);
                    System.out.println(arr[threeNums[0]] + ", " + arr[threeNums[1]] + ", " + arr[i]);   
                }
            }
            else // number smaller than the one at threeNums[0] has been found
            {
                if (potentialMin == -1 || arr[potentialMin] > arr[i]) // This is the smallest number seen till now
                {
                    potentialMin = i; // It  may start a new series
                }
                else
                {
                    // Number smaller than threeNums[0] but larger than potentialMin
                    // This means no point in keeping the previous numbers in threeNums because 
                    // arr[potentialMin] and arr[i] will be the new series
                    threeNums[0] = potentialMin; 
                    threeNums[1] = i;
                    potentialMin = -1;
                }
            }
        }
    }
    
    
    
    
    // Helper method to get some random numbers
    static int[] getRandomNums(int numCount) 
    {
        int arr[] = new int[numCount];

        for (int i=0; i<numCount; i++)
        {
            arr[i] = 1+(int)(Math.random()*numCount*30);
            System.out.print (arr[i]+", ");
        }

        System.out.println();
        return arr;
    }
}



Sample Executions:
Input Array
129, 28, 173, 62, 77, 71, 200, 

1, 3, 4
28, 62, 77

1, 3, 5
28, 62, 71

1, 3, 6
28, 62, 200



Input Array
176, 196, 87, 175, 192, 81, 95, 

2, 3, 4
87, 175, 192



Input Array
29, 85, 53, 128, 33, 4, 77, 

0, 2, 3
29, 53, 128

0, 4, 6
29, 33, 77






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal