Find Indices With Index and Value Difference I - Solution & Explanation
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, 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 <= 1000 <= nums[i] <= 500 <= indexDifference <= 1000 <= valueDifference <= 50
Approach Overview
Problem Overview: You are given an integer array nums and two integers indexDifference and valueDifference. The task is to return two indices i and j such that |i - j| >= indexDifference and |nums[i] - nums[j]| >= valueDifference. If multiple pairs exist, any valid pair works. If none exist, return [-1, -1].
Approach 1: Brute Force (O(n^2) time, O(1) space)
The simplest strategy is to check every possible pair of indices. Iterate i from 0 to n-1, and for each index iterate j from i + indexDifference to the end of the array. For each pair, compute |nums[i] - nums[j]| and verify the value constraint. The moment both constraints are satisfied, return the pair. This method uses only basic iteration over the array and requires constant extra memory. The downside is the quadratic time complexity O(n^2), which becomes slow when the array grows large. Still, it clearly demonstrates the problem constraints and is often the first approach you would write during an interview.
Approach 2: Optimized Sorted Map (O(n log n) time, O(n) space)
A more efficient solution avoids comparing every pair. Iterate through the array while maintaining a sorted map (like TreeMap in Java or a balanced ordered structure in C++/Python). When you reach index j, insert indices that are at least indexDifference behind into the map. The map stores values from nums[i] along with their indices. Because the map is sorted by value, you can quickly search for numbers ≤ nums[j] - valueDifference or ≥ nums[j] + valueDifference. Either case satisfies the value condition. Each insertion and lookup takes O(log n), giving an overall complexity of O(n log n) with O(n) extra space. This approach works well when constraints make the brute force scan too slow.
The problem itself is fundamentally about scanning an array while respecting a minimum index gap. Some brute implementations resemble a sliding window or two pointers scan, but the optimized version relies on ordered value lookups rather than pointer movement.
Recommended for interviews: Start with the brute force idea because it directly reflects the problem definition and shows you understand the constraints. Then optimize using a sorted map to reduce the pair comparisons. Interviewers typically expect candidates to move from O(n^2) to O(n log n) by exploiting ordered value searches.
Approach 1: Brute Force Approach
The brute force approach involves checking every possible pair of indices (i, j) to determine if they satisfy both the index difference and value difference conditions. This can be achieved using two nested loops. Given the constraints, this method is viable.
This C program iterates through all pairs of indices using two nested loops. For each pair (i, j), it checks if the conditions abs(i - j) >= indexDifference and abs(nums[i] - nums[j]) >= valueDifference are met. If found, it returns an array with those indices; otherwise, returns [-1, -1].
Complexity
Time Complexity: O(n^2), where n is the length of nums.
Space Complexity: O(1) for constant space usage.
Approach 2: Optimized Sorted Map Approach
This optimized approach leverages a SortedMap (TreeMap in some languages) to efficiently manage ranges without a direct O(n^2) comparison. The idea is to keep a sliding window of past values sorted and perform a range query over it. This approach can be useful for large input sizes.
This optimized solution involves tracking potential indexes using a data structure that maintains order, achieving more efficient comparison. Note that this example uses regular loops as a conceptual enhancement since direct sorted map implementation varies by language support.
Complexity
Time Complexity: O(n log n) with efficient, sorted queries if implemented correctly.
Space Complexity: O(n), for potential storage of indices in a map or set.
Approach 3: Two Pointers + Maintaining Maximum and Minimum Values
We use two pointers i and j to maintain a sliding window with a gap of indexDifference, where j and i point to the left and right boundaries of the window, respectively. Initially, i points to indexDifference, and j` points to 0.
We use mi and mx to maintain the indices of the minimum and maximum values to the left of pointer j.
When pointer i moves to the right, we need to update mi and mx. If nums[j] \lt nums[mi], then mi is updated to j; if nums[j] \gt nums[mx], then mx is updated to j. After updating mi and mx, we can determine whether we have found a pair of indices that satisfy the condition. If nums[i] - nums[mi] \ge valueDifference, then we have found a pair of indices [mi, i] that satisfy the condition; if nums[mx] - nums[i] >= valueDifference, then we have found a pair of indices [mx, i] that satisfy the condition.
If pointer i moves to the end of the array and we have not found a pair of indices that satisfy the condition, we return [-1, -1].
The time complexity is O(n), where n is the length of the array. The space complexity is O(1)$.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), where n is the length of nums. |
| Optimized Sorted Map Approach | Time Complexity: O(n log n) with efficient, sorted queries if implemented correctly. |
| Two Pointers + Maintaining Maximum and Minimum Values | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n^2) | O(1) | Good for understanding constraints or when the array size is small |
| Sorted Map Optimization | O(n log n) | O(n) | General case where you need faster lookups for value differences |
Video Solution
Leetcode | 2903. Find Indices With Index and Value Difference I | Easy | Java Solution • Developer Docs • 722 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find Indices With Index and Value Difference I easy or hard?
Find Indices With Index and Value Difference I Python/Java solution
How to solve Find Indices With Index and Value Difference I in O(n)?
What is the best approach for Find Indices With Index and Value Difference I?
Is Find Indices With Index and Value Difference I asked at Google/Amazon/Meta?
What data structure is used in Find Indices With Index and Value Difference I?
What is the time complexity of Find Indices With Index and Value Difference I?
Ready to solve this problem?
Practice Find Indices With Index and Value Difference I with our built-in code editor and test cases.
Practice on FleetCode