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).
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.
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.
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.
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.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), where n is the length of the array. |
| Optimized Sliding Window with Multiset | Time Complexity: O(n log(min(n, indexDifference))), where n is the length of nums. |
| Default Approach | — |
| 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 |
2905. Find Indices With Index and Value Difference II || Suffix max and min 🔥 || C++,Python,JAVA • Ayush Rao • 1,727 views views
Watch 9 more video solutions →Practice Find Indices With Index and Value Difference II with our built-in code editor and test cases.
Practice on FleetCode