How to find 3 numbers in increasing order and increasing indices in an array in linear time
So here is how you can solve the problem. You need to iterate over the array three times. On the first iteration mark all the values that have an element greater than them on the right and on the second iteration mark all the elements smaller than 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_right[i] = greatest_index; } else { greatest_value_so_far = a[i]; greatest_index = i; }}// Do the same on the left with smaller valuesfor (int i =0;i<n;++i) { if (greater_on_right[i] != -1 && smaller_on_left[i] != -1) { cout << "Indices:" << smaller_on_left[i] << ", " << i << ", " << greater_on_right[i] << endl; }}This solution iterates 3 times over the whole array and is therefore 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 I couldn't figure out how to give a tip without showing the actual solution.
Hope this solves your problem.
One-pass linear time, with O(1) extra space (4 variables). Very efficient (only a couple comparisons/branches per iteration, and not much data shuffling).
This is NOT my original idea or algorithm, I just tidied up and commented the code in an ideone fork. You can add new test-cases to the code there and run it online. The original is by Kenneth, posted in comments on a thread on www.geeksforgeeks.org. Great algorithm, but the original implementation had some really silly code outside of the actual loop. (e.g., instead of local variables, lets use two member-variables in a class, and implement the function as a member-function of class Solution... And the variable-names sucked. I went for quite verbose ones.)
Kenneth, if you want to post your code as an answer, go ahead. I'm not trying to steal credit for the algo. (I did put some work into writing up this explanation, and thinking through why it works, though.)
The main article above the discussion thread has the same solution as Ivaylo Strandjev's answer. (The main-article's code is what Pramod posted as an answer to this question, months after Ivalyo's answer. That's how I found the interesting answers in comments there.)
Since you only need to find a solution, not all of them, there aren't as many corner cases as you'd expect. It turns out you don't need to keep track of every possible start and middle value you've seen, or even backtrack at all, if you choose the right things to keep as state.
The main tricks are:
The last value in a sequence of monotonically decreasing values is the only one you need to consider. This applies to both first(low) and second(mid) candidate elements.
Any time you see a smaller candidate for a middle element, you can start fresh from there, just looking for either a final element or an even better mid-candidate.
If you didn't already find a sequence of 3 increasing elements before an element smaller than your current mid-candidate, min-so-far and the new smaller middle-candidate are as good (as forgiving, as flexible) as you can do out of the numbers you've already checked. (See the comments in the code for a maybe-better way of phrasing this.)
Several other answers make the mistake of starting fresh every time they see a new smallest or largest element, rather than middle. You track the current min that you've seen, but you don't react or make use of it until you see a new middle.
To find new candidate middle elements, you check if they're smaller than the current middle-candidate, and != min element seen so far.
I'm not sure if this idea can be extended to 4 or more values in sequence. Finding a new candidate 3rd value might require tracking the min between the current candidate second and third separately from the overall min. This could get tricky, and require a lot more conditionals. But if it can be done correctly with constant-size state and one pass without backtracking, it would still be linear time.
// Original had this great algorithm, but a clumsy and weird implementation (esp. the code outside the loop itself)#include <iostream>#include <vector>using namespace std;//Find a sorted subsequence of size 3 in one pass, linear time//returns an empty list on not-foundvector<int> find3IncreasingNumbers(int * arr, int n){ int min_so_far = arr[0]; int c_low, c_mid; // candidates bool have_candidates = false; for(int i = 1; i < n; ++i) { if(arr[i] <= min_so_far) // less-or-equal prevents values == min from ending up as mid candidates, without a separate else if()continue; min_so_far = arr[i]; else if(!have_candidates || arr[i] <= c_mid) { // If any sequence exists with a middle-numbers we've already seen (and that we haven't already finished) // then one exists involving these candidates c_low = min_so_far; c_mid = arr[i]; have_candidates = true; } else { // have candidates and arr[i] > c_mid return vector<int> ( { c_low, c_mid, arr[i] } ); } } return vector<int>(); // not-found}int main(){ int array_num = 1;// The code in this macro was in the original I forked. I just put it in a macro. Starting from scratch, I might make it a function.#define TRYFIND(...) do { \ int arr[] = __VA_ARGS__ ; \ vector<int> resultTriple = find3IncreasingNumbers(arr, sizeof(arr)/sizeof(arr[0])); \ if(resultTriple.size()) \ cout<<"Result of arr" << array_num << ": " <<resultTriple[0]<<" "<<resultTriple[1]<<" "<<resultTriple[2]<<endl; \ else \ cout << "Did not find increasing triple in arr" << array_num << "." <<endl; \ array_num++; \ }while(0) TRYFIND( {12, 11, 10, 5, 6, 2, 30} ); TRYFIND( {1, 2, 3, 4} ); TRYFIND( {4, 3, 1, 2} ); TRYFIND( {12, 1, 11, 10, 5, 4, 3} ); TRYFIND( {12, 1, 11, 10, 5, 4, 7} ); TRYFIND( {12, 11, 10, 5, 2, 4, 1, 3} ); TRYFIND( {12, 11, 10, 5, 2, 4, 1, 6} ); TRYFIND( {5,13,6,10,3,7,2} ); TRYFIND( {1, 5, 1, 5, 2, 2, 5} ); TRYFIND( {1, 5, 1, 5, 2, 1, 5} ); TRYFIND( {2, 3, 1, 4} ); TRYFIND( {3, 1, 2, 4} ); TRYFIND( {2, 4} ); return 0;}Making a CPP macro which can take an initializer-list as a parameter is ugly:
Is it possible to pass a brace-enclosed initializer as a macro parameter?
It was very much worth it to be able to add new test-cases easily, though, without editing arr4 to arr5 in 4 places.
I posted another approach to resolve it here.
#include<stdio.h>// A function to fund a sorted subsequence of size 3void find3Numbers(int arr[], int n){ int max = n-1; //Index of maximum element from right side int min = 0; //Index of minimum element from left side int i; // Create an array that will store index of a smaller // element on left side. If there is no smaller element // on left side, then smaller[i] will be -1. int *smaller = new int[n]; smaller[0] = -1; // first entry will always be -1 for (i = 1; i < n; i++) { if (arr[i] < arr[min]) { min = i; smaller[i] = -1; } else smaller[i] = min; } // Create another array that will store index of a // greater element on right side. If there is no greater // element on right side, then greater[i] will be -1. int *greater = new int[n]; greater[n-1] = -1; // last entry will always be -1 for (i = n-2; i >= 0; i--) { if (arr[i] > arr[max]) { max = i; greater[i] = -1; } else greater[i] = max; } // Now find a number which has both a greater number on // right side and smaller number on left side for (i = 0; i < n; i++) { if (smaller[i] != -1 && greater[i] != -1) { printf("%d %d %d", arr[smaller[i]], arr[i], arr[greater[i]]); return; } } // If we reach number, then there are no such 3 numbers printf("No such triplet found"); return;}// Driver program to test above functionint main(){ int arr[] = {12, 11, 10, 5, 6, 2, 30}; int n = sizeof(arr)/sizeof(arr[0]); find3Numbers(arr, n); return 0;}