Find non duplicateTriangle Triplets from a list of given numbers

Question

I implemented an O(N^2) algorithmic solution but not sure it is better than my previous implementation Find Triangle Triplets from a list of given numbers in case of performance. I adapted almost all suggestions from answer except a structure to keep the triangle triplets.The reasons to ignore the suggestion are follows:

• This program added additional feature to remove duplicates from the output

• To achieve this additional feature in better way is to keep the data structure as vector instead of suggested data structure 'structure' in place of vector.

• Moreover there is no additional advantage, instead a change in the coding style with this suggested change in my perspective

And @nhgrif pointed out in chat my previous solution spitting duplicate triplets and that flaw is taken care here. Let me know is there any other option to make my code better.

#include<vector>
#include<iostream>
#include<algorithm>
#include<set>
bool isTriangleTriplet(const int a, const int b, const int c)
{
 if( ( a + b ) > c && ( a + c ) > b && ( b + c ) > a)
 {
 return true;
 }
 return false; 
}
std::vector<std::vector<int>> findTriangleTriplets( const std::vector<int>& vec_input )
{
 auto size = vec_input.size();
 std::vector<std::vector<int>> triplets;
 for( unsigned int i = 0; i < size; ++i )
 {
 for( unsigned int j = i+1; j < size; ++j )
 {
 std::vector<int> temp;
 temp.emplace_back( vec_input.at( i ) );
 temp.emplace_back( vec_input.at( j ) ); 
 triplets.emplace_back( temp ); 
 } }
 std::vector<std::vector<int>> temp_triplets;
 for(auto &pair : triplets)
 {
 std::vector<int> pers_vec( pair );
 bool flag = false;
 for( auto &num : vec_input )
 {
 if( isTriangleTriplet( pair.at( 0 ), pair.at( 1 ) , num) )
 { 
 if( flag )
 {
 std::vector<int> temp( pers_vec );
 temp.emplace_back( num );
 temp_triplets.push_back( temp ); 
 }
 else if( std::count( std::begin( pair ), std::end( pair ), num ) < 2 )
 {
 pair.emplace_back( num );
 flag=true;
 }
 }
 } 
 }
 for( auto & x: temp_triplets )
 {
 triplets.emplace_back( x );
 } 
 return triplets;
}
std::set<std::vector<int>> SieveDuplicates( std::vector<std::vector<int>> & triplets )
{
 std::set<std::vector<int>> sieved_triplets;
 for( auto &x : triplets )
 {
 std::sort( std::begin( x ), std::end( x ) );
 sieved_triplets.emplace( x ); 
 }
 return sieved_triplets;
}
int main()
{ 
 const std::vector<int> vec_input { 2, 3, 4, 1, 5, 6};
 std::vector<std::vector<int>> triplets = findTriangleTriplets( vec_input );
 std::cout<< "Triplet size:" << triplets.size()<<"\n";
 for ( auto &x : triplets)
 {
 for( auto &y : x )
 { 
 std::cout<<y<<" ";
 }
 std::cout<<"\n"; 
 }
 std::set<std::vector<int>> sieved_triplets=SieveDuplicates( triplets );
 std::cout<< "Sieved Triplet size:" << sieved_triplets.size()<<"\n";
 for ( auto &x : sieved_triplets )
 {
 for( auto &y : x )
 { 
 std::cout<<y<<" ";
 }
 std::cout<<"\n"; 
 }
}

Answer 1

Not an O(N^2) algorithm

1. You create a vector that contains every (i,j) pair. This vector contains O(N^2) elements.

2. For each pair, you loop across the original vector of N elements.

Outer loop = O(N^2)
Inner loop = O(N)

Total = O(N^3)

By the way, unless you allow printing ranges of answers, there is no O(N^2) solution to this problem because there can be O(N^3) triplets that need to be printed.