Watch 10 video solutions for Find Indices With Index and Value Difference II, a medium level problem involving Array, Two Pointers. This walkthrough by Ayush Rao has 1,727 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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]) >= valueDifferenceReturn 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 <= 109Problem 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 | 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 |