Find Indices With Index and Value Difference II

Problem

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) >= 2, and
abs(nums[i] - nums[j]) >= 4

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.

Examples

Example 1

1
2
3
4
5
6


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

1
2
3
4
5
6


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

1
2
3
4


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 <= 10^5
0 <= nums[i] <= 10^9
0 <= indexDifference <= 10^5
0 <= valueDifference <= 10^9

Solution

Method 1 – Sliding Window with Monotonic Queue

Intuition

Since the constraints are large, a brute-force approach is too slow. We can use a sliding window and monotonic queues to efficiently track the minimum and maximum values in a window of size at least indexDifference.

Approach

Use two monotonic deques: one for the minimum and one for the maximum in the window.
For each index i, maintain the window of indices at least indexDifference apart.
For each i, check if there exists a j (with |i-j| >= indexDifference) such that |nums[i] - nums[j]| >= valueDifference by comparing with the min and max in the window.
If found, return the pair [i, j].
If no such pair exists, return [-1, -1].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
public:
    vector<int> findIndices(vector<int>& nums, int indexDifference, int valueDifference) {
        int n = nums.size();
        deque<int> minq, maxq;
        for (int i = 0; i < n; ++i) {
            if (i >= indexDifference) {
                while (!minq.empty() && minq.front() < i - indexDifference) minq.pop_front();
                while (!maxq.empty() && maxq.front() < i - indexDifference) maxq.pop_front();
                if (abs(nums[i] - nums[minq.front()]) >= valueDifference)
                    return {i, minq.front()};
                if (abs(nums[i] - nums[maxq.front()]) >= valueDifference)
                    return {i, maxq.front()};
            }
            while (!minq.empty() && nums[i] <= nums[minq.back()]) minq.pop_back();
            minq.push_back(i);
            while (!maxq.empty() && nums[i] >= nums[maxq.back()]) maxq.pop_back();
            maxq.push_back(i);
        }
        return {-1, -1};
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


func findIndices(nums []int, indexDifference int, valueDifference int) []int {
    n := len(nums)
    minq, maxq := []int{}, []int{}
    for i := 0; i < n; i++ {
        if i >= indexDifference {
            for len(minq) > 0 && minq[0] < i-indexDifference {
                minq = minq[1:]
            }
            for len(maxq) > 0 && maxq[0] < i-indexDifference {
                maxq = maxq[1:]
            }
            if abs(nums[i]-nums[minq[0]]) >= valueDifference {
                return []int{i, minq[0]}
            }
            if abs(nums[i]-nums[maxq[0]]) >= valueDifference {
                return []int{i, maxq[0]}
            }
        }
        for len(minq) > 0 && nums[i] <= nums[minq[len(minq)-1]] {
            minq = minq[:len(minq)-1]
        }
        minq = append(minq, i)
        for len(maxq) > 0 && nums[i] >= nums[maxq[len(maxq)-1]] {
            maxq = maxq[:len(maxq)-1]
        }
        maxq = append(maxq, i)
    }
    return []int{-1, -1}
}
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        int n = nums.length;
        Deque<Integer> minq = new ArrayDeque<>(), maxq = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (i >= indexDifference) {
                while (!minq.isEmpty() && minq.peekFirst() < i - indexDifference) minq.pollFirst();
                while (!maxq.isEmpty() && maxq.peekFirst() < i - indexDifference) maxq.pollFirst();
                if (Math.abs(nums[i] - nums[minq.peekFirst()]) >= valueDifference)
                    return new int[]{i, minq.peekFirst()};
                if (Math.abs(nums[i] - nums[maxq.peekFirst()]) >= valueDifference)
                    return new int[]{i, maxq.peekFirst()};
            }
            while (!minq.isEmpty() && nums[i] <= nums[minq.peekLast()]) minq.pollLast();
            minq.addLast(i);
            while (!maxq.isEmpty() && nums[i] >= nums[maxq.peekLast()]) maxq.pollLast();
            maxq.addLast(i);
        }
        return new int[]{-1, -1};
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
    fun findIndices(nums: IntArray, indexDifference: Int, valueDifference: Int): IntArray {
        val n = nums.size
        val minq = ArrayDeque<Int>()
        val maxq = ArrayDeque<Int>()
        for (i in 0 until n) {
            if (i >= indexDifference) {
                while (minq.isNotEmpty() && minq.first() < i - indexDifference) minq.removeFirst()
                while (maxq.isNotEmpty() && maxq.first() < i - indexDifference) maxq.removeFirst()
                if (kotlin.math.abs(nums[i] - nums[minq.first()]) >= valueDifference)
                    return intArrayOf(i, minq.first())
                if (kotlin.math.abs(nums[i] - nums[maxq.first()]) >= valueDifference)
                    return intArrayOf(i, maxq.first())
            }
            while (minq.isNotEmpty() && nums[i] <= nums[minq.last()]) minq.removeLast()
            minq.addLast(i)
            while (maxq.isNotEmpty() && nums[i] >= nums[maxq.last()]) maxq.removeLast()
            maxq.addLast(i)
        }
        return intArrayOf(-1, -1)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def findIndices(self, nums: list[int], indexDifference: int, valueDifference: int) -> list[int]:
        from collections import deque
        n = len(nums)
        minq, maxq = deque(), deque()
        for i in range(n):
            if i >= indexDifference:
                while minq and minq[0] < i - indexDifference:
                    minq.popleft()
                while maxq and maxq[0] < i - indexDifference:
                    maxq.popleft()
                if abs(nums[i] - nums[minq[0]]) >= valueDifference:
                    return [i, minq[0]]
                if abs(nums[i] - nums[maxq[0]]) >= valueDifference:
                    return [i, maxq[0]]
            while minq and nums[i] <= nums[minq[-1]]:
                minq.pop()
            minq.append(i)
            while maxq and nums[i] >= nums[maxq[-1]]:
                maxq.pop()
            maxq.append(i)
        return [-1, -1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


impl Solution {
    pub fn find_indices(nums: Vec<i32>, index_difference: i32, value_difference: i32) -> Vec<i32> {
        use std::collections::VecDeque;
        let n = nums.len();
        let mut minq = VecDeque::new();
        let mut maxq = VecDeque::new();
        for i in 0..n {
            if i as i32 >= index_difference {
                while let Some(&idx) = minq.front() {
                    if idx < i as i32 - index_difference { minq.pop_front(); } else { break; }
                }
                while let Some(&idx) = maxq.front() {
                    if idx < i as i32 - index_difference { maxq.pop_front(); } else { break; }
                }
                if (nums[i] - nums[*minq.front().unwrap() as usize]).abs() >= value_difference {
                    return vec![i as i32, *minq.front().unwrap()];
                }
                if (nums[i] - nums[*maxq.front().unwrap() as usize]).abs() >= value_difference {
                    return vec![i as i32, *maxq.front().unwrap()];
                }
            }
            while let Some(&idx) = minq.back() {
                if nums[i] <= nums[idx as usize] { minq.pop_back(); } else { break; }
            }
            minq.push_back(i as i32);
            while let Some(&idx) = maxq.back() {
                if nums[i] >= nums[idx as usize] { maxq.pop_back(); } else { break; }
            }
            maxq.push_back(i as i32);
        }
        vec![-1, -1]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
    findIndices(nums: number[], indexDifference: number, valueDifference: number): number[] {
        const n = nums.length;
        const minq: number[] = [], maxq: number[] = [];
        for (let i = 0; i < n; i++) {
            if (i >= indexDifference) {
                while (minq.length && minq[0] < i - indexDifference) minq.shift();
                while (maxq.length && maxq[0] < i - indexDifference) maxq.shift();
                if (Math.abs(nums[i] - nums[minq[0]]) >= valueDifference)
                    return [i, minq[0]];
                if (Math.abs(nums[i] - nums[maxq[0]]) >= valueDifference)
                    return [i, maxq[0]];
            }
            while (minq.length && nums[i] <= nums[minq[minq.length-1]]) minq.pop();
            minq.push(i);
            while (maxq.length && nums[i] >= nums[maxq[maxq.length-1]]) maxq.pop();
            maxq.push(i);
        }
        return [-1, -1];
    }
}

Complexity

⏰ Time complexity: O(n), where n is the length of nums. Each index is pushed and popped from the deques at most once.
🧺 Space complexity: O(n), for the deques used to maintain the window.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Sliding Window with Monotonic Queue#

Intuition#

Approach#

Code#

Complexity#