CareerCup

a[i]<a[j]<a[k] s.t i<j<k
From the original array build two arrays.
i) LMin[i] contains index of the min element seen so far from the left including a[i].
ii) RMax[i] contains index of the max element seen so far from the right including a[i].
consider the following array: 
a      =4,7,5,1,3,8,9,6,2
LMin=0,0,0,3,3,3,3,3,3
RMax=6,6,6,6,6,6,6,7,8

Now for i=1 to n if a[LMin[i]] < a[i] < a[RMax[i] print LMin[i],a[i],RMax[i]
Time complexity: O(n)
Space Complexity: O(n)

a[i]<a[j]<a[k] s.t i<j<k
From the original array build two arrays.
i) LMin[i] contains index of the min element seen so far from the left including a[i].
ii) RMax[i] contains index of the max element seen so far from the right including a[i].
consider the following array: 
a=4,7,5,1,3,8,9,6,2
LMin=0,0,0,3,3,3,3,3,3
RMax=6,6,6,6,6,6,6,7,8
Now for i=1 to n if a[LMin[i]] < a[i] < a[RMax[i] print LMin[i],a[i],RMax[i]
Time complexity: O(n)
Space Complexity: O(n)

void order_numb(vector<int> array){   
         int N=array.size();
         int result[3];
         result[0]=-1;
         result[1]=-1;
         result[2]=-1;
         result[0]=array[0];
         for(int i=1;i<N;i++){
            if(array[i]<result[0] && result[1]==-1){
               result[0]=array[i];
               continue;
            }else if(array[i]>result[0] && (result[1] == -1 || result[1]>array[i])){
               result[1]=array[i];
               continue;
            }
            if(array[i]>result[0] && array[i]>result[1]){
               result[2]=array[i];
               cout<<result[0]<<" "<<result[1]<<" "<<result[2]<<endl;
               return;
               }
         }
         cout<<"NO SUCH SUBSEQUENCE"<<endl;
      }

// Here is a c++ solution that guarantees correctness and is able to handle duplicate.
// However, it is not a O(n) solution. I do not think this problem can be solved in linear time tho. Correct me if I am wrong.

static vector<int> findAscElements(int a[], int l) {
vector<int> r;
for (int i = 0; i < l; i++) {
if (r.size() == 0) { r.push_back(a[i]); }
else if (r.size() == 1) {
if (a[i] < r.front()) { r.pop_back(); r.push_back(a[i]); }
else if (a[i] > r.front()) { r.push_back(a[i]); }
}
else if (r.size() == 2) {
if (a[i] <= r[0]) {
vector<int> d = findAscElements(a + i, l - i);
if (d.size() == 3) { return d; }
}
else if (a[i] < r[1]) { r.pop_back(); r.push_back(a[i]); }
else if (a[i] > r[1]) { r.push_back(a[i]); break; }
}
}
return r;
}

garimaa.blogspot.in/2012/04/program-4th-in-c.html

A solution in C# based on the idea of keeping the minimum array of length 1, and the minimum array of length 2 in memory and then expanding or updating either until we find an element that would extend the array of length 2 to an array of length 3:

static IList<int> FindTriplet(int[] input)
    {
        int minL1 = int.MaxValue;
        int[] minL2 = new int[2] { int.MaxValue, int.MaxValue};

        for (int i = 0; i < input.Length; i++)
        {
            //3 cases:
            // 1.) input[i] < minL2[1] and input[i] > minL2[0] -> replace array length 2 second number
            // 2.)  input[i] > minL1 && input[i] < minL2[1]  -> replace array length 2 with (minL1, input[i])
            // 3.) input[i] < minL1 -> replace minL1 with input[i] 

            if (input[i] > minL2[1])
            {
                //success:
                return new List<int>() { minL2[0], minL2[1], input[i] };
            }
            else if (input[i] < minL2[1] && input[i] > minL2[0])
            {
                //case 1:
                minL2[1] = input[i];
            }
            else if (input[i] > minL1 && input[i] < minL2[1])
            {
                //case 2:
                minL2[0] = minL1;
                minL2[1] = input[i];
            }
            else if (input[i] < minL1)
            {
                minL1 = input[i];
            }
        }
        return null;
    }

Hi Kiruba!

It doesn't work as expected for {15,18,13,17,9,6,20,1,25};
It doesn't print the triplet:
{17,20,25}

Let me know whats wrong!

This finds the first 3 elements that meet the requirement with a single loop:

def find3(a):
  if len(a) == 0:
    return []

  # first : a[i], second: a[j]
  # minel: minimum element encountered so far
  first = minel = a[0]
  second = None

  for n in a[1:]:
    if second == None:
      if first < n:
        second = n
      elif first > n:
        first = n
    elif n > second:
      return [first, second, n]
    elif n > first:
      first, second = minel, n

    minel = min(minel, n)

  return []

Here is a solution which has time complexity O(n) and space complexity O(1):

#include <iostream>
#include <vector>
#include <iterator>

void push_back(std::vector<int>& v1, std::vector<int>& v2, int value){
    if(v1.size() == 0){
        v1.push_back(value);
    } else if(v1.size() == 1){
        if(v1[0] < value){
            v1.push_back(value);
        } else {
            v1[0] = value;
        }
    } else if(v1.size() == 2) {
        if(value < v1[0]){
            if(v2.size() == 0){
                v2.push_back(value);
            } else { // v2.size() == 2
                if(value > v2[0]){
                    v2.push_back(value);
                    v1.swap(v2);
                    v2.clear();
                } else {
                    v2[0] = value;
                }
            }
        } else if(value > v1[1]){
            v1.push_back(value);
        } else if(value > v1[0]){
            v1[1] = value;
        }
    }
}

void find3(std::vector<int>& v){
    if(v.size() < 3){
        return;
    }
    std::vector<int> r1;
    std::vector<int> r2;
    r1.reserve(3);
    r2.reserve(2);
    for(size_t i = 0; i < v.size(); ++i){
        push_back(r1, r2, v[i]);
        if(r1.size() == 3)
            break;
    }
    std::ostream_iterator<int> os(std::cout, " ");
    std::copy(r1.begin(), r1.end(), os);
    std::cout << std::endl;
}

int main(){
    int ar[] = {1,2,1,4,6};
    //int ar[] = {6,10,4,2,7,3,1,8};
    //int ar[] = {4,3,2,1};
    //int ar[] = {8,9,6,7,2,3,10};
    //int ar[] = {4,5,3,6};
    //int ar[] = {5,4,7,1,2,8};
    //int ar[] = {5,4,7,1,2,3,8};
    //int ar[] = {5,4,7,1,2,3};
    size_t N = sizeof(ar) / sizeof(ar[0]);
    std::vector<int> v(ar, ar + N);
    find3(v);
    return 0;
}

how about this method?

1 #!/usr/bin/python
  2 #-*- encoding: utf-8 -*-
  3 
  4 a = [4, 7, 5, 1, 3, 8, 9, 6, 2]
  5 
  6 def find_max_until(a, max_value, max_index):
  7     tmp_max = 0
  8     tmp_index = 0
  9     for index in range(max_index):
 10         if tmp_max < a[index] and a[index] < max_value:
 11             tmp_max = a[index]
 12             tmp_index = index
 13     return tmp_max, tmp_index
 14 max_value = 100
 15 max_index = len(a)
 16 for i in range(3):
 17     max_value, max_index = find_max_until(a, max_value, max_index)
 18     print max_value, max_index

Can we say that the problem can be reduced to finding the min and max element in the array o given numbers
Once we have that in O(n) time, any number other than them can be taken to form a set of
min < a[i] < max

bool find3Elements(int ary[], int len, int &i, int &j, int &k)
{
	if (len < 3) return false;

	int minIdx = 0;
	int maxIdx = len - 1;
	int start = 1;
	int end = len - 2;

	while (start <= end)
	{
		if (ary[start] > ary[minIdx] && ary[start] < ary[maxIdx])
		{
			i = minIdx;
			j = start;
			k = maxIdx;
			return true;
		}
		else if (ary[end] > ary[minIdx] && ary[end] < ary[maxIdx])
		{
			i = minIdx;
			j = end;
			k = maxIdx;
			return true;
		}
		else 
		{
			if (ary[start] < ary[minIdx]) minIdx = start;
			if (ary[end] > ary[maxIdx]) maxIdx = end;
			start++;
			end --;
		}
	}

	return false;
}

This would work

def min3(a)
	s1dash = a[0]
	s1 = nil
	s2 = nil
		for i in (1..a.length-1)
			if a[i]<s1dash
			s1dash = a[i]
			elsif(a[i]>s1dash and (s2.nil? or s2>a[i])) 
			s1 = s1dash
			s2 = a[i]
			else
			puts" #{s1} #{s2} #{a[i]}"
			return
		end
	end
end

tested against
a = [15,16,13,14,10,9,6,7,8] ;[5,1,2,3,4];[5, 4, 3, 2, 1]