Reduce Time Complexity -part 1

The idea behind time complexity is that it can measure the execution time of the algorithm in a way that depends only on the algorithm itself and its input, But to understand the theoretic concepts of time complexity click here, This blog is all about to optimize your approach and adept at programming. There are miscellaneous techniques to reach the best time complexity of the given problem and to perceive it, it requires excellence in understanding in algorithms. Thus, Here's a noob to pro strategy to implement any given problem.

DISCLAIMER: To understand the concept well it prerequisites are a basic understanding of programming & little knowledge about data structures like - BSTs, Hash maps.

Problem: Print pair sum to K

According to the problem, you are given an array of integers and a number k, the goal is to print the pairs that sum up to k.

Sample Input :
9
1 3 6 2 5 4 3 2 4
7
Sample Output :
1 6
3 4
3 4
2 5
2 5
3 4
3 4

There are sundry techniques available to solve this problem, But to implement with the most optimistic approach can make you dexterous. But let us consider the primary approach that is easily observable -

NAIVE APPROACH: The fundamental approach that everyone might have come across is to traverse each element of an array and look if there's another pair available that can be added to the given sum K.

void printPair(int* arr,int n , int k)
{
    for(int i = 0;i<n;i++)
    {
        for(int j = i;j<n;j++)
        {
            if(i == j)
                continue;
            else
            {
                if(arr[i]+arr[j] == k)
                {
                    cout<<min(arr[i],arr[j])<<" "<<max(arr[i],arr[j]<<endl;
                }
            }
        }
    }
}

Time Complexity

To evaluate the time complexity consider the first element of the array, for the first element we've to traverse all the elements behind the first index, similarly for the second, we've to traverse all the elements behind the second element, thus we can conclude for n elements we've to traverse all n-1 elements. The regular expression for time complexity can be T(n) = T(n-1)+b where 'b' be any constant. Thus, the time complexity of this approach - T(n) = T(n-1)+T(n-2)+....+2+1+0

TIME COMPLEXITY : T(n) = O(n^2)  // very Bad

This time complexity is quite bad, Thus we'll have to improve our approach for better results. Generally in most cases, while dealing with arrays sorting helps, So let's introduce 2 more factors in the existing approach :

• Sort the array (Time complexity = O(n logn)

• Traverse array from both ends

Method 2-

By sorting the array, we'll have the smallest at the beginning and the largest at the end, and then traversing the array from both the ends might be helpful. So, let's start by adding the smallest and the largest element i.e. leftmost and rightmost element of the array :

• if the resultant sum is less than the given sum, then look for element just greater than the smallest i.e. element next to the smallest.

• if the resultant sum is greater than the given sum, then look for element just smaller than the greatest i.e. element previous of greatest.

• if resultant sum == given sum, then check for the redundant element on both ends and print them accordingly.

#include<algorithm>
void pairSum(int input[], int size, int x) {
sort(input,input+size);
int left = 0,right = size -1;
while(left<right)
{
    if(input[left]+input[right] < x)
        left++;
    else if(input[left]+input[right] > x)
        right--;
    else
    {
        int tempLeft = input[left];
        int leftCtr = 0;
        while(tempLeft == input[left])
        {
            leftCtr++;left++;
        }
        int tempRight = input[right];
        int printCtr;
        if(tempLeft == tempRight)
        {
            printCtr = (leftCtr*(leftCtr-1))/2;
        }
        else
        {    int rightCtr = 0;
            while(tempRight == input[right])
            {
                rightCtr++;right--;
            }
            printCtr = leftCtr*rightCtr;
        }
        for(int i = 0;i<printCtr;i++)
            cout<<tempLeft<<" "<<tempRight<<endl;
    }}
}

Time Complexity

The Time complexity for this approach can be evaluated as follows -

the time complexity of ->Sorting (n logn) + traverse each element O(n), that can be enumerated as - TIME COMPLEXITY : T(n) = O(n logn) , which is much better than the previous one.

Is there any scope to improve more???? YES, This can be done using a data structure called Hashmaps. It is a very helpful data structure that stores data in key-value pair, but the amazing thing about hash maps is its time complexity. The time complexity of insertion & searching of an element in a hashMap is O(1) that makes it a prominent resource.

Using Hashmaps : The fundamental step is to insert all elements into the hash map and store their frequency as value, now for each element of array look for the pair (k-element) if both the elements are present in the hash map, then handle the redundant elements, if present and print the pair. Now, at last, erase the element or update its frequency to 0 to avoid unnecessary repetition.

#include<unordered_map>
void pairSum(int input[], int n, int x) {
    unordered_map<int,int> myMap;
    for(int i = 0;i<n;i++)
    {
        int find = x-input[i];
        if(myMap.count(find) > 0)
        {
            int count = myMap[find];
            for(int x=0;x<count;x++)
            {
                cout<<min(input[i],find)<<" "<<max(input[i],find)<<endl;
            }
        }
        
       myMap[input[i]]++;
    }
}

Time complexity

The time complexity estimation involves -

• the insertion of n elements in the hash map = O(n).

• Finding pair = O(n).

Thus, the final Time complexity = O(n). Which is much better than from where we started.

This problem can be solved using binary trees too, but the time complexity is the same as that of method 2, to look at the code of binary trees approach click here

Thanks, Hope, it helped!

GitHub : https://github.com/shreyasharma98