Skip to main content
Talentd

Find Indices With Index and Value Difference II - Solution & Explanation

MediumArrayTwo Pointers14 min readAsked at: Paytm
Practice this problem

Problem Statement

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

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).

This C solution utilizes two nested loops to explore all pairs of indices (i, j). For each pair, it checks if both conditions are met, immediately returning a valid answer as soon as one is found. Memory is allocated for the returned result array, which needs to be freed by the caller to prevent memory leaks.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the length of the array.
Space Complexity: O(1), ignoring the space required for the output array.

Try this approach in the editor →

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.

The C++ implementation employs a std::set to keep track of the window of values. For each element nums[i], it checks for any potential matching value within the sliding window that satisfies the valueDifference constraint. If it doesn't breach the window limit, it updates the index range.

Code

C++JavaPython

C++

Java

Python

Complexity

Time Complexity: O(n log(min(n, indexDifference))), where n is the length of nums.
Space Complexity: O(min(n, indexDifference)), for the set holding the window.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n^2), where n is the length of the array.
Space Complexity: O(1), ignoring the space required for the output array.

Optimized Sliding Window with Multiset

Time Complexity: O(n log(min(n, indexDifference))), where n is the length of nums.
Space Complexity: O(min(n, indexDifference)), for the set holding the window.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckO(n²)O(1)Useful for understanding constraints or very small arrays
Sliding Window with MultisetO(n log n)O(n)General case solution; efficient for large inputs with ordered lookups

Video Solution

2905. Find Indices With Index and Value Difference II || Suffix max and min 🔥 || C++,Python,JAVA • Ayush Rao • 1,768 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Find Indices With Index and Value Difference II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Indices With Index and Value Difference I

Next

Minimum Absolute Difference Between Elements With Constraint