Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding the Problem
2.1.
Example
2.1.1.
Input
2.1.2.
Output
2.1.3.
Explanation
3.
Solution Appraoch
3.1.
Approach 1: Brute Force Intuition
3.2.
C++ Implementation
3.2.1.
Input
3.2.2.
Output
3.3.
Time Complexity
3.4.
Space Complexity
3.5.
Approach 2: Merge Sort Intuition
3.6.
C++ implementation
3.6.1.
Input
3.6.2.
Output
3.7.
Time Complexity
3.8.
Space Complexity
4.
Frequently Asked Questions
4.1.
What do you mean by array data structure?
4.2.
What is merge sort?
4.3.
Why merge sort is Outplace?
4.4.
Does merge sort require extra space?
4.5.
Is merge sort in place sort?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Count Pairs (i, j) From a Given Array Such that ARR[i] > K * ARR[j]

Author Teesha Goyal
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Arrays are like building blocks when it comes to programming. One should have a solid command over its algorithm, and one such algorithm is merge sort. Questions can be asked on direct merge sort as well as they can be framed into tricky ones as well. Today we will see one such question and will help you to strengthen your merge sort basics, i.e., count pairs (i, j) from a given array such that ARR[i] > K * ARR[j]. Now let’s discuss the problem statement in detail.

Count Pairs (i, j) From a Given Array Such that ARR[i] > K * ARR[j]

Also see, kth largest element in an array, and Euclid GCD Algorithm

Understanding the Problem

The problem is fairly simple to understand. We will be given an array, ‘ARR’ and an integer ‘K’. We have to count the pairs (ARR[i], ARR[j]) in such a way that i < j and ARR[i] > K * ARR[j].

Example

Input

ARR = [6, 2, 3, 1], K = 2

Output

3

Explanation

Here we can see that there are three pairs where i < j and ARR[i] > K * ARR[j].

  • When i = 0 and j =1, 6 > (2 * 2 = 4).
  • When i = 0 and j = 3, 6 > (2 * 1 = 2).
  • When i = 2 and j = 3, 3 > (2 * 1 = 2).
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution Appraoch

Approach 1: Brute Force Intuition

Intuition for brute force is straightforward. We will first keep a COUNT variable that will store the count of pairs. We will then use nested loops and count each possibility, i.e., from the first loop, we will traverse the array using ‘i’, and in the second loop, we will traverse the array using ‘j’, which will be initialized to i + 1. Then we will check for every possible pair if ARR[i] > K * ARR[j]. If it is true, then we will increase the value of ‘COUNT’ variable, which is going to store our final answer.

Below is the code for the above explanation.

C++ Implementation

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

// Function that will return the count of pairs.
int countPairs(vector<int> &arr, int k)
{
   // It will store the count.
   int count = 0;

   // Looping over the array.
   for (int i = 0; i < arr.size(); i++)
   {
       for (int j = i + 1; j < arr.size(); j++)
       {
           // Check if the condition is satisfied or not.
           if (arr[i] > k * arr[j]) {
               count++;
           }
       }
   }
   return count;
}

// Main function.
int main()
{
   // Taking input.
   int n;
   cin >> n;

   vector<int> arr(n, 0);
   for (int i = 0; i < n; i++)
   {
       int x;
       cin >> x;
       arr[i] = x;
   }

   int k;
   cin >> k;

   // Calling the function 'countPairs()'.
   cout << countPairs(arr, k);

   return 0;
}

Input

4
6 2 3 1
2

Output

3

Time Complexity

O(N ^ 2), where ‘N’ is the length of the string.

As we are using two nested for loops and each loop costs us O(N) time thus the overall time complexity is O(N ^ 2).

Space Complexity

O(1) that is constant space complexity.

As no extra space is being used.

Approach 2: Merge Sort Intuition

Now, we know that merge sort works on the principle of Divide and Conquer, in which we divide the array into two parts and then club their answer. We will use a similar approach here so as to reduce the complexity from O(N ^ 2) to somewhere around O(N* log N). Let’s look at the steps.

As we have to divide the array, we will start off by initializing two-variable ‘i’ and ‘j’ for the first and second half, respectively. Now, as these ‘i’ and ‘j’ are of different halves, it is certain that i < j. All we need to check is whether ARR[i] > K *  ARR[j]. Now, if this condition is true, then we will add (j - (M + 1)) to answer. This is because it’s a sorted array (as we are using merge sort, then we are also sorting it side by side). Thus all elements to the right of ‘j’ will also satisfy the condition. We will keep calling the function till ‘L’< ‘R.’ These variables are used while performing merge sort( namely ‘L,’ ‘R,’ ‘MID’). You can refer here for more depth about merge sort.

Below is the code for the above words

C++ implementation

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

// Function to merge two sorted arrays.
int merge(vector<int> arr, vector<int> tempArr,
    int l, int m, int r, int K)
{
    // i: index to left subarray && j index of the right subarray.
    int i = l;
    int j = m + 1;

    // Counts the number of pairs that meet the specified criteria.
    int cnt = 0;
    int pass = 1;

    while (i <= m)
    {
        bool found = 0;

        // Check the conditions to see if they're still valid.
        while (pass && j <= r)
        {

            if (arr[i] >= K *arr[j])
            {
                found = 1;
            }
            else
                break;
            j++;
        }

        // All elements in the left subarray's right side satisfy the same criteria.
        if (pass && found)
        {
            cnt += j;
            cnt -= (m + 1);
            int flg = 1;
            j -= flg;
        }
        i++;
    }

    // Sort the two arrays and save the result in a new array.
    int k = l;
    i = l;
    j = m + 1;
    for (; i <= m && j <= r;)
    {
        if (arr[i] <= arr[j])
        {

            tempArr[k] = arr[i];
            k++;
            i++;
        }
        else
        {

            tempArr[k] = arr[j];
            k++;
            j++;
        }
    }

    // Elements that are left in left subarray
    for (; i <= m;)
    {
        tempArr[k] = arr[i];
        k++;
        i++;
    }

    // Elements that are left in right subarray
    for (; j <= r;)
    {
        tempArr[k] = arr[j];
        k++;
        j++;
    }
    int ind = l;
    while (ind <= r)
    {
        arr[ind] = tempArr[ind];
        ind++;
    }

    //cnt value
    return cnt;
}

// Function to partition array into two halves.
int mergeSortUtil(vector<int> arr, vector<int> tempArr,
    int l, int r, int K)
{
    int cnt = 0;
    while (l < r)
    {

        int m = 0;
        m += (l + r);
        m = m / 2;

        // Sorting both ends.
        int fHalv = mergeSortUtil(arr, tempArr, l, m, K);
        cnt += fHalv;

        int sHalv = mergeSortUtil(arr, tempArr, m + 1, r, K);
        cnt += sHalv;

        // Call the merging function.
        cnt += merge(arr, tempArr, l, m, r, K);
        break;
    }

    return cnt;
}

// Merge Sort function to print the number of necessary pairs.
int mergeSort(vector<int> arr, int K)
{
    vector<int> tempArr(arr.size(), 0);

    cout << mergeSortUtil(arr, tempArr, 0, arr.size() - 1, K);
}

// Driver code
int main()
{
    int n;
    cin >> n;
    vector<int> arr(n, 0);
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        arr[i] = x;
    }
    int K;
    cin >> K;

    mergeSort(arr, K);

    return 0;
}

Input

4
5 6 2 1
2

Output

5

Time Complexity

O(N * log N), where ‘N’ is the length of the array.

This is because the recurrence relation for the merge sort algorithm can be written as :

T(N)  =  2T(N / 2)  +  θ(N) 

Upon solving this, we get O(N * log N). Refer here for a detailed solution.

Space Complexity

O(N), where ‘N’ is the length of the array. 

As we are using an auxiliary array to copy the left and right subarray. But if we also consider space used by recursive stack, it will be a maximum of log N. So total space complexity becomes O(N + logN). As N > logN, O(N + logN) ~ O(N).

Check out this problem - Count Inversions

Frequently Asked Questions

What do you mean by array data structure?

An array is basically a collection of similar types of data items stored at contiguous memory locations. It helps us to store multiple items of the same data type together. 

What is merge sort?

Merge sort is a divide and conquer algorithm. It divides the array repeatedly into smaller subarrays until each subarray contains a single element and merges back these subarrays in such a manner that results in a sorted array.

Why merge sort is Outplace?

The standard implementation of merge sort is outplace as it requires an extra space of O(n) for temporary arrays.

Does merge sort require extra space?

Yes, merge sort requires O(n) extra space for temporary arrays in outplace implementation and no extra space for in-place implementation(if the stack space is not considered).

Is merge sort in place sort?

No, the standard approach is not in-place, but we can optimise the merge sort to work in-place.

Conclusion

We saw how we solved the problem, print pairs (i, j) from a given array such that ARR[i] > K * ARR[j].’ Using merge sort, we reduced the time complexity from O(N ^2) to O(N * log N). 

Recommended problems -

 

There are a lot more questions indirectly related to merge sort. So head over to our practice platform Coding Ninjas Studio to practice top problems on every topic, read Interview Experiences, and many more. Till then, Happy Coding!

Previous article
Check if the array can be split into subarrays such that the XOR of the length of the Longest Decreasing Subsequences of those subarrays is 0
Next article
Count the number of inversions in an array using merge sort
Live masterclass