CODEWITHSUNDEEP
c++algorithmsearch
Babra Cunningham
Babra Cunningham

Reputation: 2967

Efficient methods of searching vectors for specific int's that meet a condition?

I'm trying to write an efficient operation to search through a vector, specifically identify the existence of three int's (A1, A2, A3) where A1 > A2 && A2 < A3.

So given A {5,3,1,2,3}, the operation with output: [3,1,2], [3,2,3],[5,1,3], [5,1,2]

The obvious approach would be to use three nested loops:

int my_function()
{
  std::vector<int> A {3,5,3,1,2,3};
  for(auto IT1 = A.begin(); IT != A.end(); IT1++)
  {
    for(auto IT2 = IT1 + 1; IT2 != A.end(); IT2++)
    {
      for(auto IT3 = IT2 + 1; IT3 != A.end(); IT3++)
      {
        if(*IT1 > *IT2 && *IT3 > *IT2)
        {
          //Do stuff
        }
      }
    }
  }
}

Clearly this is very inefficient, are there any known ways of performing an operation such as this in a single loop? Or more efficiently than three nested loops?

Upvotes: 1

Views: 79

Answers (1)

alexeykuzmin0
alexeykuzmin0

Reputation: 6440

If you want to find all such triplets, nothing is asymptotically faster since the number of such triplets can be up to O(N^3).

UP: Hovewer, if you somehow have a guarantee that there're not so much such triplets (let's say you have T = o(N^3) of them), you can write a more efficient algorithm.

Let's iterate through all the elements of the array and try place current element in the middle of the triplet. To do so, we need to maintain two ordered sets of values: one of all the values to the left of current, and sencond - to the right. Here's the code:

// Initialization
std::multiset<int> left;                      // empty set
std::multiset<int> right(A.begin(), A.end()); // set of all elements in A
// Iterations
for (int x : A) {
    right.erase(x);
    for (auto l = left.rbegin(); l != left.rend() && *l > x; ++l) {
        for (auto r = right.rbegin(); r != right.rend() && *r > x; ++r) {
            // Do stuff with triplet *l, x, *r.
        }
    }
    left.insert(x);
}

The complexity of such solution is O(T + NlogN), which is much less than O(N^3) if T is small. The downside is that the triplets are processed in a different order.

Upvotes: 4

Related Questions