Optimizing number of pairs

Given an integer X, find the number of pairs (i, j) such that A[i] + B[j] ≤ X

Note: It is given that the above question can be solved in O(n), also, we may assume that the array given are sorted. Here’s my approach:

int count_pairs(vector<ll> a, vector<ll> b, ll x)
    int ap = 0,bp = 0;
    int c = 0;
    while(ap<a.size() && bp<b.size() && a[ap]+b[bp]<=x)
    while(ap<a.size() && a[ap]+b[0]<=x)
        for(int i=0; i<bp; ++i)
    return c;

However, we can see that this is not an optimal solution. So what should be the approach?

For each A_i, binary search B for the largest value that satisfies the condition. Let’s say you find it at index j. Then, you can add j to final answer. (Here, i and j are 1-based indices.)
This should work in O(N*\log_2{N})
I am finding O(N).

Yeah I figured it using two pointers, one starting from end(j), the other one from beginning(i).
keep incrementing i till a[i]+b[j]<=x, and keep updating the counter simultaneously. Also decrement j when a[i]+b[j]>x. Make the loop run till i<a.size() && j>=0

1 Like

Can you share the code?

int getNumOfPairs(long long int n, vector<long long int> A, vector<long long int> B) {
    int i = 0;
    int j = B.size() - 1;
    int result = 0;
    while (i < A.size() && j >= 0) {
        if (A[i] + B[j] <= n) {
            result += (j+1);
        } else {
    return result;