OA question asked in a company | Count number of pairs query | MUST DO | OA | Medium

Given A list of Pairs {L,R}
An array
Find out the total number of pairs (i, j) where(A[ i ], A[ j ]) should be equal to exactly one of the given Q pairs. And i < j.
Example
Pairs - [[4,10],[10,5],[5,4]]
Array - [1,4,5,10,1,10,5,4]

Answer -
6
4,10
4,10
10,5
10,5
5,4
5,4

pairs.length = 10^5
array.lenght = 10^7
max (A[i]) = 10^9

---------------------------------------------------------------------------------------------------------------------------------------
BRUTE FORCE

#include  <bits/stdc++.h>
using namespace std;

void solve(vector<vector<int>> &pairs, vector<int> &arr){
    unordered_map<int,unordered_map<int,int>> pps;
    unordered_map<int,int> running;
    for(int i=arr.size()-1;i>=0;i--){
        for(auto m: running){
            pps[arr[i]][m.first]+=m.second;
        }
        running[arr[i]]++;
    }
    int res=0;
    for(auto q: pairs){
        cout<<"{"<<q[0]<<","<<q[1]<<"} -> ";
        if(pps.find(q[0])==pps.end()){
            cout<<0<<endl;
        }
        else{
            cout<<pps[q[0]][q[1]]<<endl;
            res+=pps[q[0]][q[1]];
        }
    }
    cout<<"res= "<<res<<endl;
}

int main() {

    // vector<vector<int>> pairs = {{4,10},{10,5},{5,4}};
    // vector<int> arr = {1,4,5,10,1,10,5,4};
    // solve(pairs,arr);

    vector<vector<int>> pairs = {{4,3},{3,4},{4,4},{3,3},{1,4},{1,3},{4,0}};
    vector<int> arr = {4,3,4,3,1,3,3,3,4,3,4};
    solve(pairs,arr);

    return 0;
}
TC - O(N*N)
Each query can be answered in O(1) time. Though, I doubt it will pass. We can also do it in Nq time, which is more of the right approach considering the constraints.

------------------------------------------------------------------------------------------------------------------------------------

Time : O(N*q)
Space : O(1)

maintains an ans variable
for every query (consider the values as left and right)
traverse the array and keep a counter for left value , initalize to zero .
if the element is left increment the counter
if element is right add the counter to ans




P.S. THIS IS NOT THE PERFECT ANSWER YET. I AM STILL WORKING ON IT USING SEGMENT TREE/ SQRT DECOMPOSITION ETC. IF YOU ARE READING THIS, PLEASE WAIT


The main idea of my solution is sqrt-decomposition.
0. Remove duplicates from the list of (L, R) pairs. This way, if (A[i], A[j]) is equal to at least one pair then it is equal to exactly one pair.

For each R store a set of paired Ls. I call such set small if its size is <= sqrt(q) and large otherwise. Note that there are at most sqrt(q) large sets.
Scan through the array A and keep track of already encountered values. When looking at A[j], you want to count A[i] that are in the set paired to R.
3.1. If the set of Ls paired to R is small then you can process them in O(sqrt(q)). n such steps will take O(n sqrt(q)) total which is acceptable.
3.2. If the set of Ls paired to R is large then lookup the answer (computed in the next step).
3.3. When looking at A[j], loop through all large sets to which it belongs, and record the fact that you've seen it. There are at most sqrt(q) large sets, so n such steps will take O(n sqrt(q)) total which is acceptable.
Update: fixed C++ code (no I/O, no dedup)

[#include](https://leetcode.com/problems/minimum-interval-to-include-each-query) <bits/stdc++.h>
using namespace std;

constexpr int SQRT = 300;  // other values may work faster.

int64_t count_pairs(const vector<pair<int, int>>& lr, const vector<int>& a) {
  map<int, vector<int>> r2ls;  // unordered_map may work faster
  for (const auto& [l, r] : lr) {
    r2ls[r].push_back(l);
  }

  map<int, vector<int>> l2rs;  // unordered_map may work faster
  for (const auto& [l, r] : lr) {
    if (r2ls[r].size() > SQRT) {
      l2rs[l].push_back(r);
    }
  }

  int64_t answer = 0;
  map<int, int> small, large;  // unordered_map may work faster

  for (const auto ak : a) {
    if (r2ls[ak].size() <= SQRT) {
      for (const auto l : r2ls[ak]) {
        answer += small[l];
      }
    } else {
      answer += large[ak];
    }

    ++small[ak];
    for (const auto r : l2rs[ak]) {
      ++large[r];
    }
  }
  return answer;
}

int main() {
  {
    vector<pair<int, int>> lr{{4, 10}, {10, 5}, {5, 4}};
    vector<int> a{1, 4, 5, 10, 1, 10, 5, 4};
    cout << count_pairs(lr, a) << '\n';  // 6
  }

  {
    vector<pair<int, int>> lr{{1, 3}};
    vector<int> a1{1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1,
                   1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 3};
    cout << count_pairs(lr, a1) << '\n';  // 46
    vector<int> a2{1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 3, 3,
                   3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3};
    cout << count_pairs(lr, a2) << '\n';  // 39
  }
}