CareerCup

This question is answered in the Amazon questions

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)

I got a solution of O(n) time and O(1) space. It doesn't need to finish going through the array.

The idea:

Go through the list from left to right. If k hasn't been found, I want to find i and j to be some numbers as small as possible. I use variable temp to store a potential smaller i. i and j will be updated at the same time when a smaller j has been found.

Use 4, 7, 5, 1, 3, 8, 9, 6, 2 as an example:

i, j, k, temp
----------
0,-1,-1,-1 // a[0] = 4
0, 1,-1,-1 // a[0] = 4, a[1] = 7
0, 2,-1,-1 // a[0] = 4, a[2] = 5
0, 2,-1, 3 // temp = 3
3, 4,-1,-1 // a[3] = 1, a[4] = 3
3, 4, 5,-1 // a[3] = 1, a[4] = 3, a[5] = 8


i<j<k: 3<4<5
a[i]<a[j]<a[k]: 1<3<8

class Ijk {

	public static void main(String[] args) {
		Integer[] a = { 4, 7, 5, 1, 3, 8, 9, 6, 2 };
		Integer temp = -1, i = -1, j = -1, k = -1;

		for (int n = 0; n < a.length; n++) {
			if (i != -1) {
				if (j != -1) {
					if (a[n] > a[i] && a[n] < a[j]) {
						j = n;
					} else if (a[n] > a[j]) {
						k = n;
						break;
					}

					if (temp != -1) {

						if (a[temp] < a[i] && a[n] < a[j] && a[n] > a[temp]) {
							i = temp;
							j = n;
							temp = -1;
						}

						else if (a[temp] < a[i] && a[n] < a[j]
								&& a[n] < a[temp]) {
							i = n;
							j = temp;
							temp = -1;

						}

					} else {

						if (a[n] < a[i]) {
							temp = n;
						}
					}

				} else {
					if (a[n] > a[i]) {
						j = n;
					}else if (a[n] < a[i]) {
						i = n;
					}
				}
			} else {
				i = n;
			}
		}
		System.out.println(i + "<" + j + "<" + k);
		System.out.println(a[i] + "<" + a[j] + "<" + a[k]);
	}
}

Im sorry. I found the solution on SO but i wasnt very clear on how to do. Here is izomorphius' solution to the problem:

int greater_on_right[SIZE];
int smaller_on_left[SIZE];
memset(greater_on_rigth, -1, sizeof(greater_on_right));
memset(smaller_on_left, -1, sizeof(greater_on_right));

int n; // number of elements;
int a[n]; // actual elements;
int greatest_value_so_far = a[n- 1];
int greatest_index = n- 1;
for (int i = n -2; i >= 0; --i) {
   if (greatest_value_so_far > a[i]) {
     greater_on_rigth[i] = greatest_index;
   } else {
     greatest_value_so_far = a[i];
     greatest_index = i;
   }
}

// Do the same on the left with smaller values


for (int i =0;i<n;++i) {
  if (greater_on_rigth[i] != -1 && smaller_on_left[i] != -1) {
    cout << "Indices:" << smaller_on_left[i] << ", " << i << ", " << greater_on_rigth[i] << endl;
  }
}

How about we just use a stack?

Let the the max number of elements we are after is N, in this case N = 3.
Traverse the array, A, and do:
if (not stack.empty) and (A[i] < stack.top):
stack.pop()
stack.push(A[i])
If (stack.empty) or (A[i] > stack top):
stack.push(A[i])
if stack.size == N then we are done!

Time : THETA(n)
Space : 3

O(n) time and O(1) space is the best solution. Just keep track of the current smallest number A and currently smallest length-2 increasing piece B[0:1]. Updating it takes O(1) time.
Example: 5, 6, 1, 2, 0, 1, 0, 9.
Step 1:
A = 5, B = NULL
Step 2:
A = 5, B = [5, 6]
Step 3:
A = 1, B = [5, 6]
Step 4:
A = 1, B = [1, 2]
Step 5:
A = 0, B = [1, 2]
Step 6:
A = 0, B = [0, 1]
Step 7:
A = 0, B = [0, 1]
Step 8:
Bingo, B + 9 is length-3 increasing piece

You can do this in two iterations.
1. Iterate through the array once and make a note of the numbers which is lesser than the number on the right.
2. Iterate through the array again and make a note of the numbers which is greater than the number to its left.
Now the number (or numbers) are the numbers which are common to both these things.

My solution is following:

In first iteration let's try to compare each two neighbors with each other.

for (i=0;i<n-1;i++)
{if A[i+1]>A[i]
tmp=i+1;
}

for (j=tmp;j<n;j++)
{
if A[j]>A[tmp]
return true
}

I mean it is not possible to find any combination of suitable numbers without two neighbors that meet the condition of i<j and A[i]<A[j].
so with my solution the answer of [5, 1, 6, 1, 7] is (1,2,4) indices. This algorithm is not supposed to give you all possible combinations. It is only supposed to extract possible one.

Sounds like dynamic programming.

Let P[i][j] be true if j th value is bigger than i th value in the input array.

Traverse the input array and complete the P[][] array.

Also, try to store the number of 'trues' per each row as you build the P[][] array.

Once you have 2 trues in a row, you have found a possible candidate, so stop building the P array and return the two numbers with "true" and the starting index of that row.

So here is how you can solve the problem. You need to iterate over the array twice. On the first iteration mark all the values that have an element greater then them on the right and on the second iteration mark all the element smaller then them on their left. Now your answer would be with an element that has both:

int greater_on_right[SIZE];
int smaller_on_left[SIZE];
memset(greater_on_rigth, -1, sizeof(greater_on_right));
memset(smaller_on_left, -1, sizeof(greater_on_right));

int n; // number of elements;
int a[n]; // actual elements;
int greatest_value_so_far = a[n- 1];
int greatest_index = n- 1;
for (int i = n -2; i >= 0; --i) {
if (greatest_value_so_far > a[i]) {
greater_on_rigth[i] = greatest_index;
} else {
greatest_value_so_far = a[i];
greatest_index = i;
}
}

// Do the same on the left with smaller values


for (int i =0;i<n;++i) {
if (greater_on_rigth[i] != -1 && smaller_on_left[i] != -1) {
cout << "Indices:" << smaller_on_left[i] << ", " << i << ", " << greater_on_rigth[i] << endl;
}
}
This solution iterates 3 times over the whole array and is therefor linear. I have not provided the whole solution so that you can train yourself on the left to see if you get my idea. I am sorry not to give just some tips but couldn't figure out how to give a tip without showing the actual solution.

Hope this solves your problem.

#include<iostream>
#include<conio.h>
using namespace std;
int main()
{ int a[100],n,i,mx,md,mn,d;
  bool fl=0;
  cin>>n;
  for(i=0;i<n;i++)
  cin>>a[i];
  mx=n-1;
  md=-1;
  mn=-1;
  for(i=n-2;i>=0;i--)
  { if(a[mx]-a[i]>0)
    { if(md==-1)
      md=i;
      else
      { if(a[md]-a[i]>0)
        { mn=i;
          cout<<a[mn]<<" "<<mn+1<<"\n"<<a[md]<<" "<<md+1<<'\n'<<a[mx]<<" "<<mx+1<<'\n';
          fl=1;
          break;
        }  
        else
        { if(d>a[mx]-a[i])
          { md=i;
            d=a[mx]-a[md];
          }
        }
      }    
    }
    else
    mx=i;
  }
  if(fl==0)
  cout<<"NO Solution\n";
  getch();
}

O(N) time and memory

// Assuming arr.length >= 3
Triplet findAnyIncTriplet(int arr[]) {

    // O(n) memory
    int mins[] = new int[arr.length];
    int maxs[] = new int[arr.length];

    // O(n) time
    mins[0] = 0;
    for (int i = 1; i < arr.length; ++i) {
        if (arr[i] < arr[ mins[i - 1] ]) {
            mins[i] = i;
        } else {
            mins[i] = mins[i - 1];
        }
    }

    maxs[a.length - 1] = a.length - 1;
    for (int i = a.length - 2; i >= 0; --i) {
        if (arr[i] > arr[ maxs[i + 1] ]) {
            maxs[i] = i;
        } else {
            maxs[i] = maxs[i + 1];
        }
    }

    for (int i = 1; i < a.length - 1; ++i) {
        if (arr[ mins[i - 1] ] < arr[i] && arr[i] < arr [maxs[i + 1] ]) {
            return new Triplet(mins[i - 1], i, maxs[i + 1]);
        }
    }

    return null;
}

python

l=[1,2,8,4,0,-1,4,78,23,25,9]
firstbest=secondbest=thirdbest=0
for i in range(0,len(l)):
     if l[firstbest] < l[i]:
             thirdbest = secondbest
             secondbest = firstbest
             firstbest = i
print( thirdbest, secondbest, firstbest)

package One;

public class ThreeIncreasing {
	
	public static void main(String[] args) {
		int arr[]={5,8,2,10};
		
		int a=arr[0];
		int b=-1,c=-1,d=-1;
		
		printArray(arr);
		printVars(a,b,c,d);
		
		int i=0;
		boolean ra=false,rb=false;
		
		while(c==-1 && i<arr.length-1)
		{
			++i;
			
			if(arr[i]<a && b==-1)
			{
				a=arr[i];
				continue;
			}
			
			if(arr[i]>a && b==-1)
			{
				b=arr[i];
				continue;
			}
			
			if(b!=-1 && arr[i]<b && a<arr[i])
			{
				b=arr[i];
				if(ra==true)
				{
					rb=true;
					ra=false;
				}
				continue;
			}
			
			if(b!=-1 && arr[i]>b)
			{
				c=arr[i];
				if(ra==true && rb==false)
				{
					a=d;
				}
				continue;
			}
			
			if(b!=-1 && arr[i]<a)
			{
				ra=true;
				rb=false;
				d=a;
				a=arr[i];
				continue;
			}
			
		}
		
		if(c!=-1)
		{
			printVars(a,b,c,d);
		}
		else
		{
			System.out.println("NO Sol");
			printVars(a,b,c,d);
		}
	}
	
	public static void printArray(int arr[])
	{
		for(int i=0;i<arr.length;i++)
		{
			System.out.print(arr[i]+" , ");
		}
		
		System.out.println();
	}
	
	public static void printVars(int a,int b,int c,int d)
	{
		System.out.println(a+" , "+b+" , "+c+" , "+d+" , ");
	}

}

It's so simple

int i=0,j=-1,k=-1;
for(int s=1;s<n;s++){
   if(a[s]>a[i]){
      j=s;break;
   }
}
if(j!=-1){
   for(int s=j+1,s<n;s++){
      if(a[s]>a[j]){
         k=s;break;
      }
   }
   if(k!=-1) System.out.println(i+" "+j+" "+k);
   else System.out.println("no such indices are available in given array");
}else System.out.println("no such indices are available in given array");

//program to find i,j,k in array such that i<j<k and a[i]<a[j]<a[k]

#include<iostream>
#include<cstring>

#define SIZE 100

using namespace std;

int main()
{
	int a[SIZE];
	int len=0;

	cin>>len;

	for(int i=0;i<len;i++)
		cin>>a[i];

	int j=1;
	while(j<len-1)
	{
		if(a[j]<a[j+1])
		{
			if(a[j]>a[j-1])
			{
				cout<<j-1<<","<<j<<","<<j+1<<"\n";
			}
			j++;
		}
		else
			j=j+2;
	}
	
	return 0;
}

static void FindIncreasingTriple(int[] arr)
        {
            int a = -1, b = -1;
            for (int i = 1; i < arr.Length; i++)
            {
                if (arr[i] > arr[i-1])
                {
                    if (a < 0)
                    {
                        a = i - 1;
                        b = i;
                    }
                    else
                    {
                        if (arr[i] > arr[b])
                        {
                            Console.WriteLine("Indices: {0}, {1}, {2}, Values: {3}, {4}, {5}", a, b, i, arr[a], arr[b], arr[i]);
                        }
                        else
                        {
                            a = i - 1;
                            b = i;
                        }
                    }
                }
                else
                {
                    if (arr[i] < arr[b] && arr[i] > arr[a])
                    {
                        b = i;
                    }
                }
            }

            Console.WriteLine("Not found!");
        }

Posting implementation for feedback.

void foo(int[] a){
 int length  = a.length;
 if(length < 3){
  System.out.printf("Error: Array needs to have at least 3 entries");
  reutrn;
 }
 int k = length-1;
 int j = k-1;
 int i = j-1;
 int temp = i-1;
 while(temp>0){
  if(a[i]>=a[temp])
   i = temp;
  temp--;
 }
 temp = j-1;
 while(temp>i){
  if(a[temp]>=a[i])
   j = temp;
  temp--;
 }
 temp = k-1;
 while(temp>j){
  if(a[temp]>=a[j])
   k = temp;
  temp--;
 }
 if(a[i]<a[j] && a[j]<a[k])
  System.out.printf("%d, %d, %d", i, j, k);
 else
  System.out.printf("No entries in array where i<j<k and a[i]<a[j]<a[k]");
}

int a[] = {4,3,2,1,0,4,7,5};
	  int j = 0, least = Integer.MAX_VALUE;
	  int indices[] = {-1,-1,-1};
	  for(int i=0; i < a.length -1; i++)
	  {
		  j = i+1;
		  if(a[i] > least) {
			  indices[2] = i;
			  break;
		  }
		  if(a[i] < a[j] && a[j] < least) {
			  least = a[j];
			  indices[0] = i;
			  indices[1] = j;
		  }
		  
	  }
	  
	  for(int i=0; i < 3; i++)
	  {
		  System.out.println(a[indices[i]] + " ");
	  }

Just add all bound checks.

My algorithm:
* an array imin[i] is the index of min element of subarray 0..i
* run from right to left, maintain imax is the index of the max element in subarray i..n-1
* a triplet: imin[i] < i < imax

Code in Python

def find_ijk(a):
	if len(a) < 3:
		return None
	imin = [0]*len(a)
	for i in xrange(1, len(a)):
		imin[i] = imin[i - 1]
		if a[i] <= a[imin[i]]:
			imin[i] = i
	imax = len(a) - 1
	for i in xrange(len(a) - 2, 0, -1):
		if a[i] < a[imax] and i > imin[i]:
			return imin[i], i, imax
		if a[i] > a[imax]:
			imax = i
	return None

#include <stdio.h>
#include <stdlib.h>
void search_index(int *);
int main()
{
    int a[]={10,5,6,13,8,2,25,15,35};
    search_index(a);

    return 0;
}
void search_index(int * a)
{
    int i;
    int first,second,third;
    first=second=third=0;
    for(i=1;i<9;i++)
    {
        if(a[i]>a[first] && first<i)
        {
            first=i;

        }
        else
        {
            if(a[first]>a[second] && second<first)
              {
                  second=i;
              }
              else
              {
                 if(a[second]>a[third] && third<second)

                  third=i;
              }


        }

    }
    printf("%d %d %d\n",third,second,first);
    printf("%d %d %d",a[third],a[second],a[first]);
}

Any thoughts on this implementation? It seems a lot simpler than what is posted here. Am I missing something?

int arr[]={5,8,7,10,3,12,2,32,33};
		int i=1;
		if ((arr[i-1]<arr[i]) && (arr[i]<arr[i+i]))
				{
			System.out.println(i-1+" "+i+" "+(i+1));
			System.out.println(arr[i-1]+" "+arr[i]+" "+arr[i+1]);
				
				}
		else		
		for (i=1; i<arr.length-1;i++)
		{
			if ((arr[i-1]<arr[i]) && (arr[i]<arr[i+1]))
			{
		System.out.println(i-1+" "+i+" "+i+1);
		System.out.println(arr[i-1]+" "+arr[i]+" "+arr[i+1]);
			
			}
		}

My Solution is O(n) for worst case (when traversing the entire array is required) & achieves the desired result, however the medium element finding logic is flexible (for change):

#include <stdio.h>

#define SIZE 7

int main()
{
	int array[SIZE];
	int max_index = 0;
	int min_index = 0;
	int med_index = 0;
	int counter = 0;

	for (counter=0; counter<SIZE; counter++)
	{
		printf ("\nEnter Array Element: ");
		scanf  ("%d", &array[counter]);

		if (array[counter]>array[max_index])
		{
			/* Update Max Index */
			max_index = counter;
		}

		if (array[counter]<array[min_index])
		{
			/* Update Min Index */
			min_index = counter;
		}

		if (max_index-min_index>=2)
		{
			break;
		}
	}

	if (max_index-min_index>=2)
	{
		med_index = max_index-1; /* or min_index+1 */

		printf ("\nMin = %d, Med = %d, Max = %d\n", array[min_index], array[med_index], array[max_index]);
	}
	else
	{
		printf ("\nNo 3 Elements in this Array satisfy the desired property\n");
	}

	return 0;

}

This question is ambiguous. Do you find only one set of {i,j,k} so that the i<j<k and a[i]<a[j]<a[k] are satisfied? Or, you have to find all possible such sets of {i,j,k} ? I feel the comments contained both interpretations....

this should work:

static Tuple<int, int, int> FindIjk(int[] numbers)
        {
            int i = 0, j = -1, k = -1, ip=-1;
            for (var e = 1; e < numbers.Length; e++)
            {
                // if we have potential smaller i, and current position value smaller than current j position value
                // move both i and j forward
                if (ip != -1 && numbers[e] < numbers[j])
                {
                    i = ip;
                    j = e;
                }

                // try to find as i and j couple as small as possible
                if (numbers[e] > numbers[i])
                {
                    // if we can find K to make to triple, then return the finding.
                    if (j != -1 && numbers[e] > numbers[j])
                    {
                        k = e;
                        break;
                    }
                    else
                    {
                        // get a smaller j
                        j = e;
                    }
                }
                else
                {
                    // j never set, then move i to smallest place so far
                    // otherwise consider it as potential next i position
                    if (j == -1)
                    {
                        i = e;
                    }
                    else
                    {
                        ip = e;
                    }
                }
            }

            return new Tuple<int, int, int>(i, j, k);
        }

You dont need two iterations, i think!
store the pair with lowest second number


s1=s2=infinity
for i=0-N
if A[i]>A[i-1]
if A[i]<=s2
s2=A[i]
s1=A[i-1]
else
print s1 s2 s3
return

I has solved this as a geometry problem. The idea is to find three non-increasing sequences - to find to sequences and stop after third is being found. So I need only 2 array of size for 2 sequences < N*sizeof(element).
For example: 3 2 1 3 2 1 3 2 1. There is following sequences: 3 2 1 1 1, 3 2 2, 3. The last elements of each sequence form a solution.

/*
    TASK:
    
    Given a array of integers , find 3 indexes i,j,k such that, i<j<k and a[i] < a[j] < a[k]. Best possible is a O(n) algorithm.
*/

#include <vector>
#include <iostream>

using namespace std;

int main(int argc, char **argv) {
    if (argc <= 1) {
        cout << "Wrong count of arguments" << endl;
        return -1;
    }
    
    vector<int> arrays[2];
    for (int arrayId = 0; arrayId < 2; arrayId++) {
        int numbers = argc - 1;
        arrays[arrayId].reserve(numbers);
    }
    
    bool found = false;
    int value;
    
    for (int i = 1; i < argc; i++) {
        value = atoi(argv[i]);
        cout << value << endl;
        
        for (int arrayId = 0; arrayId < 2; arrayId++) {
            if (arrays[arrayId].size() > 0) {
                if (arrays[arrayId].back() >= value) {
                    arrays[arrayId].push_back(value);
                    break;
                }
            } else {
                arrays[arrayId].push_back(value);
                break;
            }
            
            if (arrayId == 1) {
                // Has not pushed value into first and second array - there is a result
                found = true;
            }
        }
        
        if (found) {
            break;
        }
    }
    
    if (found) {
        cout << "Result: " << arrays[0].back() << ", " << arrays[1].back() << ", " << value << endl;
    } else {
        cout << "Result has not been found" << endl;
    }
    
    return 0;
}

Python version. I use brute force way it is O(n^3) but it is sure the answer is right, getijk.
For getijk2. I use a algorithm

# -*- coding: utf-8 -*-
"""
Created on Tue Nov 27 14:26:17 2012

@author: qzhang
Given a array of integers , find 3 indexes i,j,k such that,
i<j<k and a[i] < a[j] < a[k]. Best possible is a O(n) algorithm.
"""

#brute force answer
def getijk(array):    
    length = len(array)
    for i in range(0,length-2):
        for j in range(i+1,length-1):
            for k in range(j+1,length):
                if (array[i]<array[j] and array[j]<array[k]):
                    #print "getijk i,j,k is:",i,j,k
                    print "while the value is: ",array[i],array[j],array[k]                    

#alogirthm answer
def getijk2(array):
    length = len(array)
    result = []    
    for item in array:
        result.append([item])
        for result_item in result:
            if(len(result_item) == 3):
                print result_item
                result.remove(result_item)
            elif (item > result_item[-1]):
                a = result_item[:]
                a.append(item)
                result.append(a)
                #print result_item
            #print result
            
        
    

if __name__ == "__main__":
    #array = [2,1,4,5,7]
    #getijk(array)
    #getijk2(array)    
    array = [4,7,5,1,3,8,9,6,2]
    getijk(array)
    
    print "another function:"
    getijk2(array)

Let me know if anyone sees any issue with this one:

Algo:
Iterate over the array three times to determine index for: i, j and k.

Complexity:
Time: O(3n) ~= O(n)
Space = O(1)

print3Largest(int a[])
{
    int i = 0, j =0, k = 0;

    // assume a[0] is largest so far
    i = j = k = 0;
    // iterate to determine the indices for
    // three largest elements in an array.
    for (int index = 0; index < MAX; ++index) {
        if (a[index] > a[i]) {
            i = index;
        }
    }

    for (int index = 0; index < MAX; ++index) { 
        if (a[index] > a[j] && a[index] < a[i]) {
            j = index;
        }
    }

    for (int index = 0; index < MAX; ++index) { 
        if (a[index] > a[k] && a[index] < a[j]) {
            k = index;
        }
    }

    cout << "First: " << a[i] << " ,Second: " << a[j] << " ,Third: " <<
        a[k] << "\n";
}

I tried it with repeated array elements, it seems to work fine.

How about using count sort

The code:

void FindThreeIncreasing(vector<int> my_array)
{
	int N=my_array.size();
	vector<int> X(N+1);
	int L=0;
	for(int i=0;i<N;i++)
	{
		int j;
		if(L==0)j=0;
		else
		{
			for(j=1;j<=L;j++)
			{
				if(my_array[X[j]]>my_array[i])
				{
					break;
				}
			}
			j--;
		}
		if(j==L || my_array[X[j+1]]>my_array[i])
		{
			X[j+1]=i;
			L=max(L,j+1);
			if(L==3)
			{
				break;
			}
		}
	}
	for(int i=1;i<=3;i++)
	{
		cout<<my_array[X[i]]<<" ";
	}
	cout<<endl;
}

lonest increasing subsequence algorithm. just need to maintain sortest list of 3 so algo runs on O(n) instead of O(nlogn)