Find Indices With Index and Value Difference II
MediumUpdated: Aug 2, 2025
Practice on:
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, andabs(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
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 <= 10^50 <= nums[i] <= 10^90 <= indexDifference <= 10^50 <= 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 leastindexDifferenceapart. - For each
i, check if there exists aj(with|i-j| >= indexDifference) such that|nums[i] - nums[j]| >= valueDifferenceby 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
C++
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};
}
};
Go
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
}
Java
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};
}
}
Kotlin
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)
}
}
Python
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]
Rust
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]
}
}
TypeScript
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.