Improve valid pairs algorithm time complexity

Question

I was solving a task:

Input n,m,k - integer numbers and integer array arr of size n The pair of elements in arr is valid if two conditions are true

1. std::abs(arr[i] - arr[j]) <= m
2. arr[i] + arr[j] <= k

Output - number of valid pairs

Example:

Input
4 1 5
1 3 2 3

Output
3

The output is 3, because of pairs (1,2) (3, 2) and (2, 3)

My code is working. But it's time complexity is O(N^2) and I have a TIME LIMIT error

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;


int main() {
    int n, m, k;
    cin >> n >> m >> k;

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

    int res = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (arr[i] + arr[j] <= k and abs(arr[i] - arr[j]) <= m) {
                res++;
            } else {
                break;
            }
        }
    }
    cout << res;
    return 0;
}

I think that I should apply idea of sorting, how to reduce time complexity of my code? I guess it should be O(N*logN)

Answer 1

You can use binary search to find the range of valid numbers less than the current element that can be matched to create a pair. The absolute value can be removed in this way since the current element will always be the larger element in the pair.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstddef>
int main() {
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<int> vec(n);
    for (int& x : vec) std::cin >> x;
    std::ranges::sort(vec);
    std::size_t res = 0;
    for (int i = 1; i < n; ++i) {
        auto left = std::lower_bound(vec.begin(), vec.begin() + i, vec[i] - m), 
            right = std::upper_bound(vec.begin(), vec.begin() + i, k - vec[i]);
        res += left < right ? right - left : 0;
    }
    std::cout << res;
    return 0;
}