2905. Find Indices With Index and Value Difference II

You are given a 0-indexed integer array nums having length n, an integer indexDifference, and an integer valueDifference.

Your task is to find two indices i and j, both in the range [0, n - 1], that satisfy the following conditions:

• abs(i - j) >= indexDifference, and
• abs(nums[i] - nums[j]) >= valueDifference

Return an integer array answer, where answer = [i, j] if there are two such indices, and answer = [-1, -1] otherwise. If there are multiple choices for the two indices, return any of them.

Note: i and j may be equal.

class Solution {
public:
    vector<int> findIndices(vector<int>& nums, int indexDifference, int valueDifference) {
        map<int,int> mp;
        for(int i = indexDifference; i < nums.size(); i++) mp[nums[i]] = i;
        for(int i = 0; i < nums.size(); i++) {
            int lo = nums[i] - valueDifference, hi = nums[i] + valueDifference;
            auto ub = mp.upper_bound(lo), lb = mp.lower_bound(hi);
            if(lb != end(mp)) {
                return {i,lb->second};
            }
            if(ub != begin(mp)) {
                --ub;
                return {i,ub->second};
            }
            
            if(i + indexDifference >= nums.size()) break;
            int x = nums[i+indexDifference];
            if(mp[x] == i+indexDifference) mp.erase(x);
        }
        return {-1,-1};
    }
};