Program to Count Number of Good Pair.

Given an integer array num of size n, return the count of possible good pairs. A pair of elements is called a good pair if (num[i] == num[j]) and i < j.

Example:

Example 1:
Input: num[] = {2, 1, 3, 2, 2, 3};
Output: 4

Explanation: 
There are four good pairs (0, 3), (0, 4), (2, 5) and (3, 4)

Example 2:
Input: num[] = {3, 3, 3, 3}
Output: 6

Approach 1: Brute Force Solution.

Take a count variable and initialize it with 0. Run two nested for loops for each element of the array, pick each element one by one and then compare it with the remaining element and then keep on increasing the count variable whenever the given condition is satisfied. 

C++ Solution Code:

/*C++ code for count number of good pairs*/
#include<bits/stdc++.h>
using namespace std;

int goodPairs(vector<int> &num){
    int count = 0;

    for(int i = 0; i < num.size(); i++){
        for(int j = i+1; j < num.size(); j++){
            if(num[i] == num[j])
              count++;
        }
    }
    return count;
}

int main(){
    vector<int> num = {2, 1, 3, 2, 2, 3};

    int count = goodPairs(num);
    cout<<"Number of Good Pairs: "<<count;

    return 0;   
}

Output:

Number of Good Pairs: 4

• Time Complexity: Running two nested loops for n elements takes O(n^2) time complexity.
• Space Complexity: No extra space is required in the above solution so space complexity is O(1).

Approach 2: Using Hash Map.

You can optimize the previous solution by using a hash map to get the count of each unique element of the array. 

Given num = [2, 1, 3, 2, 2, 3]

Structure of map:

Key      Value(count)

 2          3 (Value 2 appears 3 times)

 1          1 (Value 1 appears 1 times)

 3          2 (Value 3 appears 2 times)       

When you have n number of similar values then it can create [n*(n-1)/2] number of unique good pairs. 

[3, 3, 3, 3]

Number of Good Pairs = 4*(4-1)/2 = 6

Similarly, you can calculate the number of unique good pairs for each value of the map and sum them up to get the total number of good pairs possible from all array elements.

Key      Value(count)      Good Pairs

 2          3            [3*(3-1)/2 = 3] 

 1          1            [1*(1-1)/2 = 0]

 3          2            [2*(2-1)/2 = 1]  

Total number of Good Pairs = 3+0+1 = 4     

C++ Solution Code:

/*C++ code for count number of good pairs(Optimized)*/
#include<bits/stdc++.h>
using namespace std;

int goodPairs(vector<int> &num){
    int count = 0;
    unordered_map<int, int> mp;

    //Storing count of each unique element
    for(int i = 0; i < num.size(); i++){
        mp[num[i]]++;
    }

    //counting good pairs
    for(auto i:mp){
        int n = i.second;
        count += (n*(n-1))/2;
    }
    return count;
}

int main(){
    vector<int> num = {2, 1, 3, 2, 2, 3};

    int count = goodPairs(num);
    cout<<"Number of Good Pairs: "<<count;

    return 0;   
}

Output:

Number of Good Pairs: 4

• Time Complexity: We run two separate loops one for storing the count in the map and the next loop for counting good pairs so the average time complexity will be O(n).
• Space Complexity: We are using one map to store the count of elements so space complexity will be O(n).

Next:

(getButton) #text=(Count Number of Elements Smaller than Current Element) #icon=(link) #color=(#2339bd)

Count number of elements smaller than current number.

Given an array num of size n, for each element of num count the number of elements of the array that are smaller than the current element. It means for each element num[i] you need to count the number of elements such that num[j] < num[i] and j != i. Return the counts in an array.

Example:

Example 1:
Input: num[] = {3, 2, 5, 1, 7};
Output: {2, 1, 3, 0, 4}

Explanation: 
Number of Elements smaller than num[0] = 3 are (1 and 2) = 2 
Number of Elements smaller than num[1] = 2 are (1) = 1
Number of Elements smaller than num[2] = 5 are (1, 2 and 3) = 3
Number of Elements smaller than num[3] = 1 are () = 0
Number of Elements smaller than num[4] = 7 are (1, 2, 3 and 5) = 4

Example 2:
Input: num[] = {3, 3, 3, 3}
Output: {0, 0, 0, 0}

Example 3:
Input: num[] = {3, 2, 2, 5, 1, 7}
Output: {3, 1, 1, 4, 0, 5}

The question is very simple, you just have to get the counts of smaller elements for each and store them one by one in an array or vector and return them as your output. This question can be solved by multiple approaches let's discuss them here.

Note: We are using a C++ vector in our solution instead of an array because vectors are dynamic in nature and provide more functionality. (alert-passed)  

Approach 1: Brute Force Solution.

You can run two nested loops, the outer loop will pick elements of the array one by one, and the inner loop will traverse the whole array each time to check and count the elements that satisfy the given condition. Each time the inner loop terminates store the count value into a new resulting array and return this array at the end. 

 

C++ Solution code:

/*C++ program for how many number of elements smaller
 than current number.*/
#include<iostream>
#include<vector>
using namespace std;

vector<int> smallerNumber(vector<int> &num){
    vector<int> ans;
    int count;

    for(int i = 0; i < num.size(); i++){
        count = 0;
        for(int j = 0; j < num.size(); j++){
            if(num[i] > num[j])
               count++;
        }
        ans.push_back(count);
    }
    return ans;
}

int main(){
    vector<int> num = {3, 2, 2, 5, 1, 7};

    vector<int> result = smallerNumber(num);

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

    return 0;   
}

Output:

3 1 1 4 0 5

• Time Complexity: Running two nested loops from 0 to n will take n x n units of time so the time complexity will be O(n^2).
• Space Complexity: No extra space is required to perform any operation except the answer vector that is used to store the counts but we cannot consider this for calculating space complexity so overall space complexity will be O(1).

Approach 2: Using Hash Map and Sorting.

The above approach is solving the problem in O(n^2) time complexity but we can optimize the solution and can bring it to O(nlogn) time complexity by following the below algorithm.

Given num = [3, 2, 2, 5, 1, 7]

Step 1: Make a copy of the given array and sort it in ascending order.

copy = [1, 2, 2, 3, 5, 7]

Step 2: Store the values in a hash map corresponding to their index in reverse order. A map can store only unique values and storing values in reverse will help you to get the count of smaller values by their index.

mp[copy[5]] = mp[7] = 5
mp[copy[4]] = mp[5] = 4
mp[copy[3]] = mp[3] = 3
mp[copy[2]] = mp[2] = 1(overwritten 2 to 1)  
mp[copy[0]] = mp[1] = 0

Step 3: Store the values back in the num array.

num[0] = mp[num[0]] = mp[3] = 3
num[1] = mp[num[1]] = mp[2] = 1
num[2] = mp[num[2]] = mp[2] = 1
num[3] = mp[num[3]] = mp[5] = 4
num[4] = mp[num[4]] = mp[1] = 0
num[5] = mp[num[5]] = mp[7] = 5

Step 4: Return the num array as our answer.

num = [3, 1, 1, 4, 0, 5]

C++ Solution code:

/*C++ Optimized program for how many number of elements 
smaller than current number.*/
#include<bits/stdc++.h>
using namespace std;

vector<int> smallerNumber(vector<int> &num){
    unordered_map<int, int> mp;

    //make a copy vector
    vector<int> copy = num;
    //sort the copy vector in ascending order
    sort(copy.begin(), copy.end());

    //store elements corresponding to their index
    for(int i = num.size() - 1; i >= 0; i--){
        mp[copy[i]] = i;
    }
    
    //store map value back to num array
    for(int i = 0; i < num.size(); i++){
        num[i] = mp[num[i]];
    }
    return num;
}

int main(){
    vector<int> num = {3, 2, 2, 5, 1, 7};

    vector<int> result = smallerNumber(num);

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

    return 0;   
}

Output:

3 1 1 4 0 5

• Time Complexity: Sorting the copied array will take O(nlogn) time, and running two separate loops for n elements will take 2O(n) time so the overall time complexity of our solution is O(nlogn).
• Space Complexity: As we are using a new copy vector and unordered map for storing the element so overall space complexity is O(n). 

How To Pass Array to Function in C++.

As we know that an array is a collection same kind of data in a contiguous memory location but can we pass the array data as an argument to a function? The answer to this question is no. We cannot pass the entire array as an argument to a function but we can pass a pointer to an array. 

We have totally different methods for passing a one-dimensional and two-dimensional array to a function in C++. Let's discuss both of them one by one:

Passing One-Dimensional Array to Function.

We have passed the name of our array without an index to a function and the name of the array behaves like a pointer folding the address of the first element of the array. Any changes made in the array inside the function will directly affect the elements of the main array. 

C++ Example Code:

//C++ Example to show ways of Passing Array to Function
#include<iostream>
using namespace std;

//Formal parameter as unsized array
void funType1(int arr[], int n){

	int size = sizeof(arr)/sizeof(arr[0]);
	cout<<"\nSize of array inside fun1: "<<size<<endl;

	arr[2] = 10;  
	cout<<"Array Elements in fun1: ";
	for(int i = 0; i < n; i++)
	  cout<<arr[i]<<" ";
}

//Formal parameter as a pointer
void funType2(int *arr, int n){

	int size = sizeof(arr)/sizeof(arr[0]);
	cout<<"Size of array inside fun2: "<<size<<endl;

	arr[n-1] = 23; 
	cout<<"Array Elements in fun2: ";
	for(int i = 0; i < n; i++)
	  cout<<arr[i]<<" "; 
}

int main(){

	int arr[] = {3, 4, 5, 7, 8, 9};
	//size of array
	int n = sizeof(arr)/sizeof(arr[0]);
	cout<<"Size of given array: "<<n<<endl;

	cout<<"Array Elements: ";
	for(int i = 0; i < n; i++)
	  cout<<arr[i]<<" ";
        
        //function 1 call
	funType1(arr, n);
	cout<<endl;

        //function 2 call
	funType2(arr, n);

	return 0;
}

Output:

Size of given array: 6
Array Elements: 3 4 5 7 8 9
Size of array inside fun1: 2
Array Elements in fun1: 3 4 10 7 8 9
Size of array inside fun2: 2
Array Elements in fun2: 3 4 10 7 8 23

We have two ways of writing an array into a function as an argument, 

• The first is passing an unsized array as a parameter. (syntax: fun(int arr[])) 
• The second is passing as a pointer. (syntax: fun(int *arr))

Both hold the address of only the first element of the array.

We cannot calculate the size of the array inside the function we must have to pass the array size as a parameter. 

Passing Two-Dimensional Array to Function.

To pass a 2D array (also known as a matrix) to a function we must have to pass the second dimension value to the function were passing the first dimension value is totally optional. 

Syntax: fun(int arr[][m])

C++ Example Code:

//C++ Example code for passing 2D array to function
#include<iostream>
using namespace std;

//Passing matrix to a function
void fun2DArray(int arr[][3], int r, int c){
	cout<<"Elements of 2D Array: "<<endl;
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			cout<<arr[i][j]<<" ";
		}
		cout<<endl;
	}
}
int main(){
	
	int arr[][3] = {{2, 3, 7},{9, 5, 1},{4, 6, 2}};
	
	int row = sizeof(arr)/sizeof(arr[0]);
	int col = sizeof(arr[0])/sizeof(arr[0][0]);

	fun2DArray(arr, row, col);

	return 0;
}

Output:

Elements of 2D Array: 
2 3 7
9 5 1
4 6 2

In the above code, you can also check how we can calculate the number of rows and columns of a 2D Array using the sizeof() operator.

Next:

(getButton) #text=(Difference between Subarrays, Subsequences and Subsets.) #icon=(link) #color=(#2339bd)

Vector Type STL in C++

Vectors are sequence containers that work the same as variable-size Arrays. It is a kind of STL (Standard Template Library) based on a class template that can provide standard functionality like a Dynamic Array. Similarly, like an array, a vector can be of any type like a character array, integer array, boolean array, string array, etc. 

A Template is not a class or function it is like a blueprint or a guideline for the compiler to use the template to create a specific class or function. We specify which class to instantiate by supplying additional information depending on the template in our case we will specify the vector data type in between two angle brackets after the template name.

• syntax: vector<datatype> vector_name;
• example: vector<int> myvec;(alert-success)

In a vector, elements are in contiguous memory locations, and when we insert a value in a vector stored at the end. Removing or inserting values into a vector takes a constant amount of time and their size grows dynamically as their storage is handled by a container. We need to include a specific <vector> header file in our C++ program to use all the functionality of vector. 

Vector Functions.

There is a list of member functions available in the vector header file that we can directly use for solving our coding problems. Let's understand them one by one.

Iterator member functions:

Member Function	Definition
begin()	This function returns an iterator pointer pointing to the first element of the vector.
end()	This function returns an iterator pointer pointing to the last element of the vector.
rbegin()	This function returns a reverse iterator pointer pointing to the last element of the vector. It follows a reverse order and moves from the last element toward the first.
rend()	This function returns a reverse iterator pointer pointing to the first element of the vector. It follows a reverse order and moves from the first element toward the last.
cbegin()	This function returns a const_iterator pointing to the first element of the vector container. This const_iterator is used to point to a const value.
cend()	This function returns a const_iterator pointing to the last element of the vector container. This const_iterator is used to point to a const value.
crbegin()	This function returns a const_reverse_iterator pointing to the last element of the vector container.
crend()	This function returns a const_reverse_iterator pointing to the first element of the vector container.

C++ Example Code:

//C++ Program to show iterator function of vector STL
#include<iostream>
#include<vector>
using namespace std;

int main(){
    //declaration of integer type vector
    vector<int> myVec;

    //inserting elements in vector
    for(int i = 0; i < 6; i++)
       myVec.push_back(i+2);

    cout<<"Printing values using begin() and end() fun: ";
    for(auto it = myVec.begin(); it != myVec.end(); it++)
       cout<<*it<<" ";  

    cout<<"\nPrinting values using rbegin() and rend(): ";
    for(auto it = myVec.rbegin(); it != myVec.rend(); it++)
       cout<<*it<<" ";

    cout<<"\nPrinting values using cbegin() and cend(): ";
    for(auto it = myVec.cbegin(); it != myVec.cend(); it++)
       cout<<*it<<" ";  

    cout<<"\nPrinting values using crbegin() and crend(): ";
    for(auto it = myVec.crbegin(); it != myVec.crend(); it++)
       cout<<*it<<" ";   

    return 0;        
}

Output:

Printing values using begin() and end() fun: 2 3 4 5 6 7
Printing values using rbegin() and rend(): 7 6 5 4 3 2
Printing values using cbegin() and cend(): 2 3 4 5 6 7
Printing values using crbegin() and crend(): 7 6 5 4 3 2

Vector Functions to Check Capacity.

Member Function	Definition
size()	This function returns the size of the vector or we can say it returns a number of elements present in the vector.
capacity()	This function returns the current allocated storage space to the vector. This capacity might not be equal to the size of the vector.
shrink_to_fit()	This function decreases the current capacity of the vector container and makes it equal to the size.
resize(n)	This function changes the vector's current size to make it fit for n elements.
reserve()	This function requests that the vector capacity be at least enough for n elements only when the current capacity is not enough for n elements.
empty()	This function is used to check if the vector is empty or not or if the size is equal to 0 then it returns true else returns false.
max_size()	This function gives us an idea about the maximum number of elements the vector can hold.

C++ Example Code:

//C++ Program to show capacity function of vector STL
#include<iostream>
#include<vector>
using namespace std;

int main(){
    //declaration of integer type vector
    vector<int> myVec;

    //inserting elements in vector
    for(int i = 0; i < 6; i++)
       myVec.push_back(i+2);

    if(!myVec.empty()){
        cout<<"Size: "<<myVec.size()<<endl;
        cout<<"Capacity: "<<myVec.capacity()<<endl;
        cout<<"Maximum Size: "<<myVec.max_size()<<endl;

        myVec.shrink_to_fit();
        cout<<"Capacity after shrinking: "<<myVec.capacity()<<endl;
    }
    else{
        cout<<"Vector is empty!!!"<<endl;
    } 

    cout<<"Elements present in the vector: ";
    for(auto it = myVec.begin(); it != myVec.end(); it++)
       cout<<*it<<" ";  

    return 0;        
}

Output:

Size: 6
Capacity: 8
Maximum Size: 230584300921363951
Capacity after shrinking: 6
Elements present in the vector: 2 3 4 5 6 7

Element Access member functions:

Member Function	Definition
operator[i]	This function returns a reference to the element at the position mentioned in the square bracket in the vector.
at(i)	This function works the same as the previous one and returns a reference to the element present at position i in the vector.
front()	This function returns a reference to the first element of the vector.
back()	This function returns a reference to the first element of the vector.
data()	This function returns a direct pointer to the memory array used internally by the vector to store its owned elements.

C++ Example Code:

//C++ Program to show Element access function of vector STL
#include<iostream>
#include<vector>
using namespace std;

int main(){
    //declaration of integer type vector
    vector<int> myVec;

    //inserting elements in vector
    for(int i = 0; i < 6; i++)
       myVec.push_back(i+2);

    cout<<"Elements present in the vector: ";
    for(auto it = myVec.begin(); it != myVec.end(); it++)
       cout<<*it<<" ";  

    cout<<"\nElement at position myVec[3]: "<<myVec[3]<<endl;
    myVec[3] = 10;
    cout<<"Element at position myVec[3]: "<<myVec.at(3)<<endl;

    cout<<"First element of vector: "<<myVec.front()<<endl;
    cout<<"Last element of vector: "<<myVec.back()<<endl;

    int *p = myVec.data();
    cout<<"First element of vector: "<<*p;

    return 0;        
}

Output:

Elements present in the vector: 2 3 4 5 6 7
Element at position myVec[3]: 5
Element at position myVec[3]: 10
First element of vector: 2
Last element of vector: 7
First element of vector: 2

Vector Modifier member functions.

Member Function	Definition
push_back()	This function is used to insert or add an element at the end of the vector.
pop_back()	This function is used to delete an element from the end of the vector.
insert()	This function is used to insert an element before the element at the specified position.
assign()	This function is used to assign new values to the vector elements by replacing the old values.
erase()	This function is used to remove a single element or a range of elements from a vector.
swap()	This function is used to swap the values of one vector with the values of other vectors of the same type. The size of both vectors might not be the same.
clear()	This function is used to remove all the elements of the vector and empty it.
emplace()	This function is used to insert a new element at a specific position and extend the size of the vector by one.
emplace_back()	This function is used to insert a new element at the end position and effectively extend the size of the vector by one.

C++ Example Code:

//C++ Program to show Element access function of vector STL
#include<iostream>
#include<vector>
using namespace std;

int main(){
    //declaration of integer type vector
    vector<int> myVec;

    //inserting elements in vector
    for(int i = 0; i < 6; i++)
       myVec.push_back(i+2);

    cout<<"Elements present in the vector: ";
    for(auto it = myVec.begin(); it != myVec.end(); it++)
       cout<<*it<<" ";  

    myVec.push_back(50);
    cout<<"\nLast Element after push_back: "<<myVec.back()<<endl;
    //removing the last element
    myVec.pop_back();
    cout<<"Last Element after pop_back: "<<myVec.back()<<endl;

    //inserting element at pos 4
    myVec.insert(myVec.begin()+3, 35);
    cout<<"Element at position 4: "<<myVec[4]<<endl;
    
    cout<<"Size of vector before emplace: "<<myVec.size()<<endl;
    myVec.emplace(myVec.begin()+4, 55);
    cout<<"Size of vector after emplace: "<<myVec.size()<<endl;

    myVec.clear();
    cout<<"Size of vector after clear: "<<myVec.size()<<endl;

    return 0;        
}

Output:

Elements present in the vector: 2 3 4 5 6 7
Last Element after push_back: 50
Last Element after pop_back: 7
Element at position 4: 5
Size of vector before emplace: 7
Size of vector after emplace: 8
Size of vector after clear: 0

Various operations that we perform on the vector has different time complexity like,

• Accessing any random element takes a constant amount of time O(1).
• Inserting or removing elements takes a linear amount of time O(n) except for the last element which takes a constant amount of time O(1).
• Resizing the vector size in an operation like insert or emplace takes a linear amount of time O(n). 

Next:

(getButton) #text=(Stack STL Container in C++) #icon=(link) #color=(#2339bd)