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 <= 109The 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.
C++
Java
Python
C#
JavaScript
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.
Java
Python
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. |
2905. Find Indices With Index and Value Difference II || Suffix max and min 🔥 || C++,Python,JAVA • Ayush Rao • 1,637 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