Find Indices With Index and Value Difference II solution and explanation
9 more videos on this problem
2905. Find Indices With Index and Value Difference II || Suffix max and min 🔥 || C++,Python,JAVAAyush Rao · 7:33 · 1K views
2905. Find Indices With Index and Value Difference II - BEATS 100% with NO DATA STRUCTURESTechTalk · 6:15 · 1K views
Leetcode 2905 Find Indices With Index and Value Difference IIThinkCode · 8:40 · 1K views
Find Indices With Index and Value Difference II | Leetcode 2905 | Contest 367Tech Courses · 9:39 · 620 views
2905. Find Indices With Index and Value Difference II (Leetcode Medium)Programming Live with Larry · 14:09 · 571 views
Leetcode 2905. Find Indices With Index and Value Difference IIElite Code · 25:54 · 250 views
Find Indices With Index and Value Difference II - LEETCODE WEEKLY CONTEST 367Joyjit Codes · 7:07 · 226 views
Find indices with index and value difference IIDCC NITA · 5:32 · 182 views
2905. Find Indices With Index and Value Difference II | Weekly Contest-367 | 3rd Problem ExplainedAlgoArtist · 19:32 · 127 views
LEETCODE weekly-contest-367 | A,C | 2903 & 2905 | Find Indices With Index & Value Difference I & IICodingVerse · 14:01 · 54 views
The 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) >= indexDifference, andabs(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 <= 1050 <= nums[i] <= 1090 <= indexDifference <= 1050 <= valueDifference <= 109
Approach overview
Problem Overview: You are given an integer array nums and two integers indexDifference and valueDifference. The task is to return any pair of indices (i, j) such that |i - j| >= indexDifference and |nums[i] - nums[j]| >= valueDifference. If no such pair exists, return [-1, -1].
Approach 1: Brute Force (O(n²) time, O(1) space)
The direct approach checks every pair of indices in the array. Use two nested loops: the outer loop fixes index i, and the inner loop scans every j. For each pair, compute the index distance and value difference using absolute values. If both constraints are satisfied, return the pair immediately. This method is simple and useful for validating logic or small inputs, but the quadratic scan becomes slow as n grows. It relies only on basic array traversal with no additional data structures.
Approach 2: Sliding Window with Multiset (O(n log n) time, O(n) space)
A more scalable strategy maintains a dynamic set of candidate values whose indices are far enough away from the current index. While iterating through the array, once i >= indexDifference, insert nums[i - indexDifference] into an ordered structure such as a multiset or balanced BST. This guarantees all stored elements satisfy the index constraint.
For the current value nums[i], search the set for numbers that differ by at least valueDifference. Two checks are enough: find the smallest element >= nums[i] + valueDifference or the largest element <= nums[i] - valueDifference. Ordered structures support these queries with lower_bound in O(log n). If either candidate exists, return the corresponding indices.
This technique effectively forms a sliding eligibility window: indices become valid only after they are indexDifference positions behind the current pointer. The ordered set allows fast range checks on values while scanning the array once. It combines ideas from two pointers and sliding window processing while maintaining sorted access.
Recommended for interviews: Start by explaining the brute force approach to demonstrate the constraints clearly. Interviewers typically expect the optimized sliding window with an ordered structure because it reduces the search to O(n log n). The key insight is separating the index constraint (handled by the window) from the value constraint (handled by ordered lookups).
Approach 1: Brute Force Approach
The brute force approach is straightforward where we iterate through each possible pair of indices (i, j) and check if they satisfy both conditions: abs(i - j) >= indexDifference and abs(nums[i] - nums[j]) >= valueDifference. If such a pair exists, return it, otherwise return [-1, -1].
This approach is simple but not efficient for large inputs as it involves nested loops over all possible indices, leading to a time complexity of O(n^2).
def find_indices(nums, index_difference, value_difference):
n = len(nums)
for i in range(n):
for j in range(i, n):
if abs(i - j) >= index_difference and abs(nums[i] - nums[j]) >= value_difference:
return [i, j]
return [-1, -1]
result = find_indices([5, 1, 4, 1], 2, 4)
print(result)import java.util.Arrays;
public class FindIndices {
public static int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
if (Math.abs(i - j) >= indexDifference && Math.abs(nums[i] - nums[j]) >= valueDifference) {
return new int[]{i, j};
}
}
}
return new int[]{-1, -1};
}
public static void main(String[] args) {
int[] nums = {5, 1, 4, 1};
int[] result = findIndices(nums, 2, 4);
System.out.println(Arrays.toString(result));
}
}#include <vector>
#include <iostream>
#include <cmath>
std::vector<int> findIndices(const std::vector<int>& nums, int indexDifference, int valueDifference) {
int n = nums.size();
std::vector<int> result = {-1, -1};
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
if (abs(i - j) >= indexDifference && abs(nums[i] - nums[j]) >= valueDifference) {
return {i, j};
}
}
}
return result;
}
int main() {
std::vector<int> nums = {5, 1, 4, 1};
std::vector<int> result = findIndices(nums, 2, 4);
std::cout << '[' << result[0] << ',' << result[1] << ']' << std::endl;
return 0;
}function findIndices(nums, indexDifference, valueDifference) {
let n = nums.length;
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
if (Math.abs(i - j) >= indexDifference && Math.abs(nums[i] - nums[j]) >= valueDifference) {
return [i, j];
}
}
}
return [-1, -1];
}
let result = findIndices([5, 1, 4, 1], 2, 4);
console.log(result);#include <stdio.h>
#include <stdlib.h>
int* findIndices(int* nums, int numsSize, int indexDifference, int valueDifference, int* returnSize) {
*returnSize = 2;
int* result = (int*)malloc(2 * sizeof(int));
result[0] = -1;
result[1] = -1;
for (int i = 0; i < numsSize; ++i) {
for (int j = i; j < numsSize; ++j) {
if (abs(i - j) >= indexDifference && abs(nums[i] - nums[j]) >= valueDifference) {
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}
int main() {
int nums[] = {5, 1, 4, 1};
int returnSize;
int* result = findIndices(nums, 4, 2, 4, &returnSize);
printf("[%d, %d]\n", result[0], result[1]);
free(result);
return 0;
}using System;
public class FindIndicesProgram {
public static int[] FindIndices(int[] nums, int indexDifference, int valueDifference) {
int n = nums.Length;
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
if (Math.Abs(i - j) >= indexDifference && Math.Abs(nums[i] - nums[j]) >= valueDifference) {
return new int[] { i, j };
}
}
}
return new int[] { -1, -1 };
}
public static void Main() {
int[] nums = { 5, 1, 4, 1 };
int[] result = FindIndices(nums, 2, 4);
Console.WriteLine("[" + result[0] + ", " + result[1] + "]");
}
}The Python solution iteratively checks each pair of indices and determines if they meet the criteria specified in the problem. It returns the first successful index pair it finds. Python's built-in abs() function is used to ensure conditions are met.
Time Complexity: O(n^2).
Space Complexity: O(1), considering only constant space for variables.
Approach 2: Optimized Sliding Window with Multiset
This approach optimizes the solution by using a sliding window technique combined with a data structure that can efficiently maintain elements within a sliding window, such as a Java SortedSet.
We keep track of elements in a sliding window of size indexDifference and efficiently compute if the absolute difference condition on the values abs(nums[i] - nums[j]) >= valueDifference holds for any element within this window.
This approach reduces the complexity as we avoid checking pairs unnecessarily, especially those that cannot possibly satisfy the indexDifference criterion.
from sortedcontainers import SortedList
def find_indices(nums, index_difference, value_difference):
window = SortedList()
for i, num in enumerate(nums):
if i > index_difference:
window.remove(nums[i - index_difference - 1])
pos = window.bisect_left(num - value_difference)
if pos < len(window) and abs(window[pos] - num) >= value_difference:
return [i - (index_difference + 1) if i - (index_difference + 1) > 0 else 0, i]
window.add(num)
return [-1, -1]
result = find_indices([5, 1, 4, 1], 2, 4)
print(result)import java.util.TreeSet;
public class FindIndices {
public static int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
TreeSet<Integer> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
if (i > indexDifference) {
set.remove(nums[i - indexDifference - 1]);
}
Integer lower = set.ceiling(nums[i] - valueDifference);
if (lower != null && Math.abs(lower - nums[i]) >= valueDifference) {
return new int[] {i - (indexDifference + 1) <= 0 ? 0 : i - (indexDifference + 1), i};
}
set.add(nums[i]);
}
return new int[] {-1, -1};
}
public static void main(String[] args) {
int[] nums = {5, 1, 4, 1};
int[] result = findIndices(nums, 2, 4);
System.out.println("[" + result[0] + ", " + result[1] + "]");
}
}#include <vector>
#include <set>
#include <cmath>
std::vector<int> findIndices(const std::vector<int>& nums, int indexDifference, int valueDifference) {
std::set<int> window;
for (int i = 0; i < nums.size(); ++i) {
if (i > indexDifference) {
window.erase(nums[i - indexDifference - 1]);
}
auto pos = window.lower_bound(nums[i] - valueDifference);
if (pos != window.end() && abs(*pos - nums[i]) >= valueDifference) {
return {static_cast<int>(i - (indexDifference + 1) <= 0 ? 0 : i - (indexDifference + 1)), i};
}
window.insert(nums[i]);
}
return {-1, -1};
}
int main() {
std::vector<int> nums = {5, 1, 4, 1};
std::vector<int> result = findIndices(nums, 2, 4);
std::cout << '[' << result[0] << ',' << result[1] << ']' << std::endl;
return 0;
}The Python implementation uses the SortedList from the sortedcontainers module to efficiently manage and query the current sliding window. It checks for valid pairs by maintaining and querying the sorted order of elements.
Time Complexity: O(n log(min(n, index_difference))).
Space Complexity: O(min(n, index_difference)), required for SortedList storage.
Approach 3: Default Approach
function findIndices(nums: number[], indexDifference: number, valueDifference: number): number[] {
let [mi, mx] = [0, 0];
for (let i = indexDifference; i < nums.length; ++i) {
const j = i - indexDifference;
if (nums[j] < nums[mi]) {
mi = j;
}
if (nums[j] > nums[mx]) {
mx = j;
}
if (nums[i] - nums[mi] >= valueDifference) {
return [mi, i];
}
if (nums[mx] - nums[i] >= valueDifference) {
return [mx, i];
}
}
return [-1, -1];
}func findIndices(nums []int, indexDifference int, valueDifference int) []int {
mi, mx := 0, 0
for i := indexDifference; i < len(nums); i++ {
j := i - indexDifference
if nums[j] < nums[mi] {
mi = j
}
if nums[j] > nums[mx] {
mx = j
}
if nums[i]-nums[mi] >= valueDifference {
return []int{mi, i}
}
if nums[mx]-nums[i] >= valueDifference {
return []int{mx, i}
}
}
return []int{-1, -1}
}impl Solution {
pub fn find_indices(nums: Vec<i32>, index_difference: i32, value_difference: i32) -> Vec<i32> {
let index_difference = index_difference as usize;
let mut mi = 0;
let mut mx = 0;
for i in index_difference..nums.len() {
let j = i - index_difference;
if nums[j] < nums[mi] {
mi = j;
}
if nums[j] > nums[mx] {
mx = j;
}
if nums[i] - nums[mi] >= value_difference {
return vec![mi as i32, i as i32];
}
if nums[mx] - nums[i] >= value_difference {
return vec![mx as i32, i as i32];
}
}
vec![-1, -1]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2). |
| Optimized Sliding Window with Multiset | Time Complexity: O(n log(min(n, index_difference))). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n²) | O(1) | Useful for understanding constraints or very small arrays |
| Sliding Window with Multiset | O(n log n) | O(n) | General case solution; efficient for large inputs with ordered lookups |
Frequently asked questions
Is Find Indices With Index and Value Difference II easy or hard?
Find Indices With Index and Value Difference II is rated Medium on LeetCode. The challenge comes from handling two constraints simultaneously: index distance and value difference. Recognizing that a sliding window combined with ordered search solves both efficiently is the key insight.
Find Indices With Index and Value Difference II Python/Java solution
Python solutions often use the sortedcontainers module or maintain sorted lists with binary search, while Java implementations typically rely on TreeSet. C++ solutions commonly use multiset with lower_bound. All follow the same sliding window idea with O(n log n) complexity.
How to solve Find Indices With Index and Value Difference II in O(n)?
A strict O(n) solution is difficult because the algorithm must quickly search for values that differ by a threshold while maintaining index constraints. The typical accepted solution uses an ordered set or multiset, giving O(n log n) time due to balanced tree operations such as lower_bound.
What is the best approach for Find Indices With Index and Value Difference II?
The most practical solution uses a sliding window with an ordered data structure such as a multiset or balanced BST. As you iterate through the array, insert elements whose indices are at least indexDifference behind the current index. Then check if any stored value differs from the current value by at least valueDifference using ordered lookups. This runs in O(n log n) time.
Is Find Indices With Index and Value Difference II asked at Google/Amazon/Meta?
Problems involving index constraints and value thresholds frequently appear in interviews at companies like Amazon, Google, and Meta. Variations often test sliding window reasoning, ordered data structures, or efficient pair searching in arrays.
What data structure is used in Find Indices With Index and Value Difference II?
The optimized solution uses an ordered container such as a multiset (C++), TreeSet (Java), or a balanced BST–like structure. This allows efficient insertion and range queries such as finding the first element greater than or equal to a target value.
What is the time complexity of Find Indices With Index and Value Difference II?
The brute force method checks every pair of indices and runs in O(n²) time with O(1) space. The optimized sliding window with multiset reduces the complexity to O(n log n) time and O(n) space because each insertion and lookup in the ordered set costs O(log n).