2905

2905. Find Indices With Index and Value Difference II (Medium)

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.

 

Example 1:

Input: nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
Output: [0,3]
Explanation: In this example, i = 0 and j = 3 can be selected.
abs(0 - 3) >= 2 and abs(nums[0] - nums[3]) >= 4.
Hence, a valid answer is [0,3].
[3,0] is also a valid answer.

Example 2:

Input: nums = [2,1], indexDifference = 0, valueDifference = 0
Output: [0,0]
Explanation: In this example, i = 0 and j = 0 can be selected.
abs(0 - 0) >= 0 and abs(nums[0] - nums[0]) >= 0.
Hence, a valid answer is [0,0].
Other valid answers are [0,1], [1,0], and [1,1].

Example 3:

Input: nums = [1,2,3], indexDifference = 2, valueDifference = 4
Output: [-1,-1]
Explanation: In this example, it can be shown that it is impossible to find two indices that satisfy both conditions.
Hence, [-1,-1] is returned.

 

Constraints:

• 1 <= n == nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= indexDifference <= 105
• 0 <= valueDifference <= 109

Similar Questions:

• Minimum Absolute Difference Between Elements With Constraint (Medium)

Hints:

• For each index i >= indexDifference, keep the indices j1 and j2 in the range [0, i - indexDifference] such that nums[j1] and nums[j2] are the minimum and maximum values in the index range.
• Check if abs(nums[i] - nums[j1]) >= valueDifference or abs(nums[i] - nums[j2]) >= valueDifference.
• j1 and j2 can be updated dynamically, or they can be pre-computed since they are just prefix minimum and maximum.

Solution 1.

// OJ: https://leetcode.com/problems/find-indices-with-index-and-value-difference-ii
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    vector<int> findIndices(vector<int>& A, int id, int vd) {
        set<pair<int, int>> s;
        int N = A.size();
        for (int i = 0; i < N; ++i) {
            if (i - id >= 0) s.emplace(A[i - id], i - id);
            if (s.size()) {
                auto [a, ia] = *s.begin();
                if (abs(A[i] - a) >= vd) return {ia, i};
                auto [b, ib] = *s.rbegin();
                if (abs(A[i] - b) >= vd) return {ib, i};
            }
        }
        return {-1,-1};
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/find-indices-with-index-and-value-difference-ii
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> findIndices(vector<int>& A, int id, int vd) {
        int N = A.size(), mini = 0, maxi = 0;
        for (int i = id; i < N; ++i) {
            if (A[i - id] < A[mini]) mini = i - id;
            if (A[i - id] > A[maxi]) maxi = i - id;
            if (A[i] - A[mini] >= vd) return {i, mini};
            if (A[maxi] - A[i] >= vd) return {i, maxi};
        }
        return {-1, -1};
    }
};