2
\$\begingroup\$

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";        
    }
}
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.