Category Archives: STL

Finding the number of duplicates in a list of numbers

Given a list of numbers, we have to find how many duplicate entries are present in it?

For example consider the list of numbers {5, 1, 9, 5, 2, 1, 6, 4, 5, 8}
It has 3 duplicate numbers.

There are many ways to do this. In this post, I present one of the simplest ways using C++ STL set data structure, and Java HashSet data structure
 
The insert() method of the set returns a pair of type 
pair< set<type>::iterator, bool >
 

The second value in the pair is true if a new element is inserted. It is false if there is already an existing element.

The add() method of HashSet returns true if new element is inserted, and false if no new element is inserted(duplicate)

We can make use of this property to count the number of duplicate elements.

Here is the simple C++ implementation.

Here is the Java Implementation.

C++ STL Algorithms – Sort – Part-2

In the last post, the basic use of STL sort() method is explained. In this post, I will discuss some more options available with this method.
We have seen in the previous post that sort takes the beginning and ending of the array as arguments.
sort( array.begin(), array.end() );
In addition to those parameters, it can also take a third parameter (predicate) which decides the ordering of the elements. If we do not pass the third parameter, the default ordering is assumed. For integer data types such as int,  float, char etc, ascending order is followed. For strings alphabetical order is followed. To sort an array of integers in descending order, simply call the sort routine like this.

sort( array.begin(), array.end(), greater<int>() );

std::greater is a built in comparator object provided by STL. we have to pass the type of objects to be sorted. similarly we have std::less, std::less_equal, std::greater_equal etc…

So far we are sorting only built in data types such as int, double and library class string. We can also sort objects of user defined classes also.

For example in the following program I have defined a class called Pair, which contains two fields. To sort user defined/custom data types we also have to write the comparison functions to decide the ordering. We can sort Pairs either according to the first value or the second value. I have written two comparator functions and passed these while sorting. 

Here is the code which explains these concepts.


C++ STL Algorithms – Sort- Part-1

Sorting is one of the most widely used algorithmic primitive in programming. 
C++ Standard Template Library (STL) provides an efficient implementation of the sort algorithm. It is always better to use this algorithm instead of writing our own implementation because of the following benefits.
  • It’s performance would surely be better than your own implementation. It’s implementation conforms to the C++ standard bench marks and tested by a lot of people. The library version takes advantage of the combination of multiple sorting algorithms to achieve the maximum performance.
  • Writing our own version is error prone and bugs can easily be overlooked.

Here is a simple program which demonstrates the use of library sort() routine to sort an array as well as a vector. 

The sort() method at the minimum requires two parameters; the start of the list and the end of the list. Note that the end should always point to one element beyond the last element. It sorts the element ranging between [begin, end) i.e starting from the first element till the end excluding the last.


For arrays, we know that the array name indicates the address of the first element. If we add the size of the array to the starting address, we get the address of next to last element.

For vectors, there are built-in methods begin() and end() to indicate the starting and ending elements.


    #include <iostream>
    #include <algorithm> //included for using sort
    #include <vector>
    #include <string>
    using namespace std;

    int main()
    {
    int arr[5] = {9, 6, 36, 24, 42};
    int arrSize = sizeof(arr)/sizeof(arr[0]);

    sort(arr, arr+arrSize); //sorts the given numbers in ascending order

    for( int i=0; i < arrSize; i++ )
    {
    cout << arr[i] << " ";
    }
    cout << endl;

    vector<string> names;
    names.push_back("Himalayas");
    names.push_back("Alphs");
    names.push_back("Vindhya");
    names.push_back("Aravali");

    sort( names.begin(), names.end());//sorts the names in alphabetical order

    for( int i = 0; i < names.size(); i++ )
    {
    cout << names[i] << " ";
    }

    cout << endl;

    return 0;

    }

    Program to find the powerset of a given set

    Given a set of numbers, how do we generate its power set?

    For example for the set {1,2} the power set is given below.

    {  {},  {1}, {2}, {1,2} }

    A power set is nothing but all the possible subsets of a given set. If a set contains N elements, it’s power set contains 2N elements. This is evident from the above example.

    Here is how our method works.
    All the subsets can be identified by an integer. The binary representation of that integer says which elements from the original set present in that subset.

    For example let us consider a set of two elements {1,2}, the power set of this can be represented by four integers

    0 = 0000 – Empty subset
    1 = 0001 – Fist element is present
    2 = 0010 – Second element is present
    3 = 0011 – First and Second elements are present

    In the following C++ program, the outer loop runs from 0 to 2n where n is the size of the set. For each integer, the inner loop checks for set bit positions and accordingly add those numbers to the current subset. 

    Since we have to generate all the possible subsets, the complexity of this method is O(2^n).

    #include <iostream>
    #include <set>
    #include <vector>
    using namespace std;

    //Generates the power set of integers provided in inputSet,
    //output in pSet
    void generatePowerSet( vector<int> &inputSet, set< set<int> > &pSet )
    {
    int i = 0;
    int n = inputSet.size();

    //There will be 2^n subsets; generate them
    while ( i < (2 << n) )
    {
    set<int> subSet;

    int j = 0;
    int k = i;

    while( k&(k-1) ) //Until k contains at-least one set bit
    {
    //If jth bit is set, add the jth element to the subset
    if( k & 1)
    {
    subSet.insert( inputSet[j] );
    }

    k = k >> 1;
    j++;
    }
    //Add the subset to the powerset
    pSet.insert(subSet);
    i++;
    }
    }
    //Utility to print the powerset
    void printPowerSet( set< set<int> > &pSet)
    {
    set< set<int> >::iterator setIter;
    set<int>::iterator intIter;

    for( setIter = pSet.begin(); setIter != pSet.end(); ++setIter )
    {
    cout<<"{ ";
    for( intIter = setIter->begin(); intIter != setIter->end(); intIter++ )
    {
    cout<<*intIter<<" ";
    }
    cout<<"}"<<endl;
    }
    }
    int main()
    {
    int n; // number of elements
    cin>>n;
    vector<int> intSet;
    int i;
    //Read the set elements
    for( i = 0; i < n; i++ )
    {
    int x;
    cin>>x;
    intSet.push_back(x);
    }
    set< set<int> > powerSet;
    generatePowerSet( intSet, powerSet );
    printPowerSet( powerSet );
    return 0;
    }

    Check if an array has duplicate numbers

    Given an array numbers, how do we write a function checkDuplicates() which returns true if the array has at least one element repeated; returns false if all the elements are unique.

    We discuss three different implementations of this function with various time and space complexities.

    Method-1: Naive approach

    This approach checks every possible pair in the array to see if there are any duplicates. This is exhaustive  search and we can find the answer in O(n2) time. Because there are n(n-1)/2 possible pairs for an array of size n.

    Time complexity: O(n2)
    Space complexity: O(1)

    The following is the C++ function which implements this approach.

     
    bool checkDuplicates( int array[], int n)
    {
    int i,j;
    for( i = 0; i < n; i++ )
    {
    for( j = i+1; j < n; j++ )
    {
    if( array[i] == array[j] )
    return true;
    }
    }
    return false;
    }
     
    Method-2: Sorting Approach
    First sort the array using any sort which runs in O(n log n) time ( Quick sort/ Heap sort/ Merge sort).
    Then all the duplicate elements comes together. Then simply compare all the adjacent elements to see if there are any duplicates.

    Time complexity: O(n log n)
    Space complexity: O(1) 

    The following is the C++ function which implements this approach.
     

    bool checkDuplicates( int array[], int n)
    {
    std::sort( array, array+n);
    int i;
    for( i = 0; i < n-1; i++)
    {
    if( array[i] == array[i+1] )
    return true;
    }
    return false;
    }
    Method-3: Set/HashTable approach
    Use a data structure like a Set or a Hash Table which keeps track of the elements. When trying to insert into these data structures, we can see if the element already exists; If the element already exists in the data structure, we say that the array has duplicates.

    Time complexity: O(n)
    Space complexity: O(n)

    The following is the Java function which implements this approach.

    public static boolean checkDuplicates(int [] array)
    {
    HashSet<Integer> hSet = new HashSet<Integer>();
    for( int i = 0; i < array.length; i++ )
    {
    if( !hSet.add(array[i]) )
    return true;
    }
    return false;
    }

    Bracket matching problem

    Stack is one of the most widely used data structure. In this post we will learn how to use the stack container (data structure) provided by C++ STL with an example.

    Let us consider the following problem. We have a string which contains only ‘(‘ and ‘)’ characters. We have to write a program to check if it forms a valid expression.
    For example the string “(()())” is a valid expression where as “(()()” and “())” are not.

    The algorithm for solving the question goes like this. 

    1. For each character in the string
        If the symbol is ‘(‘
             push it on to the stack
       else
            If the stack is empty
                return false
           If top of the stack contains ‘(‘
                pop off the top element
    2. If the stack is empty return true otherwise return false

    Here is the program which implements the above algorithm.

    #include <iostream>
    #include <string>
    #include <stack>

    using namespace std;

    bool isValidExpr(string input)
    {
    stack<char> stck;

    for(int i = 0; i < input.length() ; i++)
    {
    char ch = input.at(i);

    if( ch == '(' ) //if open brace, push
    {
    stck.push(ch);
    }
    else //closed brace
    {
    if( stck.empty() )// if stack is empty, there no matching open brace
    return false;
    if ( stck.top() == '(' ) //matching open brace found, so pop
    {
    stck.pop();
    }
    }
    }
    if( stck.empty() )
    return true;
    return false;
    }

    int main()
    {
    string inputExpr;
    cin>>inputExpr;
    if( isValidExpr(inputExpr) )
    cout<<"Valid Expression";
    else
    cout<<"Invalid Expression";
    return 0;
    }

    Counting characters in the given string using C++ STL map

    Map is one of the most useful data structure in solving many programming problems. Today we will see how to use C++ STL map with a simple example. Counting the frequency of letters in a given string. The map data structure stores <key,value> pairs. In this example key will be the character, and the value will be it’s frequency. Here is the code to do this.

    #include <iostream>
    #include <string>
    #include <map>

    using namespace std;

    void getFrequency(string strInput,map<char,int> & fMap)
    {
    map<char,int>::iterator it; //iterator to find the entries in map
    for(int i = 0 ; i < strInput.length() ; i++ )
    {
    char ch = strInput.at(i);
    it = fMap.find(ch); //find the character in the map
    if( it == fMap.end() ) //if not present in the map
    {
    fMap.insert( make_pair(ch,1) );//add an entry
    }
    else
    {
    it->second++; //else increment the frequency
    }
    }
    }

    void printFrequency(map<char,int> & fMap)
    {
    map<char,int>::iterator it;//iterator to loop through all the chars
    for( it = fMap.begin() ; it != fMap.end() ; ++it )
    {
    cout<<"["<< it->first<<"]"<<"->"<<it->second<<endl;
    }
    }

    int main()
    {
    string strInput;
    //read input string; this implementation does not reed space separated strings
    cin>>strInput;
    map<char,int> frequencyMap; //frequency map
    getFrequency(strInput, frequencyMap); //get the frequencies
    printFrequency(frequencyMap); //print the frequencies
    return 0;
    }

    Finding count of a number in a sorted array

    In Competitive programming, learning to use the standard library than coding from scratch saves a lot of time. In this post we will use C++ STL(Standard Template Library) binary search algorithm with an example.
    Given a sorted array of numbers, How to find the frequency of a given number?

    Here is an efficient algorithm to do it. Use binary search to find the left-most(L), and right-most(R) occurrence of the given number. Then R-L+1 gives us the result. 

    C++ STL has two functions namely lower_bound, upper_bound which finds out the left-most and right-most occurrences of a given number in a sorted array.
    The lower_bound() function returns an iterator to the left-most element, and the upper_bound() function returns an iterator to one element beyond right-most occurrence. So the difference of these two gives the count.

    Here is the C++ code.
     

    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>

    using namespace std;

    int getCount(vector<int> & numVector, int d)
    {
    int result = 0;
    vector<int>::iterator left, right;
    //find the left-most occurence
    left = lower_bound( numVector.begin(), numVector.end(), d );
    //find right-most occurence only if the number is present
    if( left != numVector.end() )
    {
    right = upper_bound( numVector.begin(), numVector.end(), d );
    result = right-left; //right points to one element beyond.
    }
    return result;
    }
    int main()
    {
    int n;
    //read array size
    cin>>n;
    int i,num;
    vector<int> nums;
    //read the array
    for( i = 0 ; i < n ; i++ )
    {
    cin>>num;
    nums.push_back(num);
    }
    //read the number to be counted
    cin>>num;
    cout<<getCount(nums,num);
    return 0;
    }