O(N) solution required

general
,
1

Given an array of numbers find all such triplets that satisfy the given condition.

Condition: a[i] < a[j] < a[k] where I < j < k.

2

Suppose i give you a sorted array .

Number of possible ordered triplets in an array is n choose 3 = O(n^3)

Finding all of them ( meaning printing or storing them would require O(n^3) time .

You should change your question to :

  1. find one such triplet if its exists ( can be done in O(n) ) .

  2. find number of such triplets ( not sure if it can be done in O(n) ) . Will have to work on it to find best possible complexity .

Please clarify your question for you to get an appropriate answer .

1 Like
3

As @vineetpaliwal mentioned, if the question is finding one such triplet (a sorted subsequence of 2 elements) then 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;
  }
}

Sources and References:

  1. http://stackoverflow.com/questions/10008118/how-to-find-3-numbers-in-increasing-order-and-increasing-indices-in-an-array-in
  2. http://www.geeksforgeeks.org/find-a-sorted-subsequence-of-size-3-in-linear-time/