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

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;
}

You can also try this code with Online C++ Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

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 -

• Product Array Puzzle
• Beautiful Array

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!