Find Indices With Index and Value Difference II

Med

#2586Time: O(n^2), where `n` is the number of elements in `nums`. The nested loops iterate through all `n*n` pairs of indices.Space: O(1), as we only use a constant amount of extra space for variables.1 company

Patterns

Two Pointers

Data structures

Array

Companies

Paytm

Prompt

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 <= 10⁵
0 <= nums[i] <= 10⁹
0 <= indexDifference <= 10⁵
0 <= valueDifference <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible pair of indices (i, j) in the array. For each pair, we verify if it satisfies both the indexDifference and valueDifference conditions.

Algorithm

Get the length of the array, n.
Iterate through the array with an index i from 0 to n-1.
Inside the first loop, iterate through the array with an index j from 0 to n-1.
For each pair (i, j), check if abs(i - j) >= indexDifference.
If the index difference condition is met, check if abs(nums[i] - nums[j]) >= valueDifference.
If both conditions are true, return the pair [i, j].
If the loops finish without returning, it means no valid pair was found. Return [-1, -1].

Walkthrough

We use two nested loops to generate all pairs of indices (i, j). The outer loop iterates i from 0 to n-1, and the inner loop iterates j from 0 to n-1. Inside the inner loop, we check two conditions: abs(i - j) >= indexDifference and abs(nums[i] - nums[j]) >= valueDifference. If both conditions are met, we have found a valid pair, and we can immediately return [i, j]. If the loops complete without finding any such pair, it means no solution exists, and we return [-1, -1]. This method is straightforward but inefficient for large inputs due to its quadratic time complexity.

1class Solution {2    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {3        int n = nums.length;4        for (int i = 0; i < n; i++) {5            for (int j = 0; j < n; j++) {6                if (Math.abs(i - j) >= indexDifference && Math.abs(nums[i] - nums[j]) >= valueDifference) {7                    return new int[]{i, j};8                }9            }10        }11        return new int[]{-1, -1};12    }13}

Complexity

Time

O(n^2), where `n` is the number of elements in `nums`. The nested loops iterate through all `n*n` pairs of indices.

Space

O(1), as we only use a constant amount of extra space for variables.

Trade-offs

Pros

Simple to understand and implement.
Correctly solves the problem for small inputs.

Cons

Highly inefficient for large arrays.
Time complexity of O(n^2) will lead to a 'Time Limit Exceeded' error on platforms with large test cases.

This optimized approach avoids the nested loops by iterating through the array just once. For each element, it efficiently checks for a valid partner by keeping track of the minimum and maximum values seen so far in the valid preceding part of the array.

Algorithm

Initialize minIdx = 0 and maxIdx = 0 to track the indices of the minimum and maximum values.
Iterate with an index j from indexDifference to n-1.
Let i = j - indexDifference. This i is the latest index that can be paired with j.
Update minIdx and maxIdx based on nums[i]. The range for finding min/max is [0, i].
- If nums[i] < nums[minIdx], update minIdx = i.
- If nums[i] > nums[maxIdx], update maxIdx = i.
Now, check if nums[j] can form a valid pair with the historical min or max.
- Check with the minimum value found so far: if nums[j] - nums[minIdx] >= valueDifference, return [minIdx, j].
- Check with the maximum value found so far: if nums[maxIdx] - nums[j] >= valueDifference, return [maxIdx, j].
If the loop completes without finding a pair, return [-1, -1].

Walkthrough

The core idea is to rephrase the problem: for each index j, we need to find an index i such that i <= j - indexDifference and abs(nums[i] - nums[j]) >= valueDifference. The second condition means we need an i where nums[i] is either very small (<= nums[j] - valueDifference) or very large (>= nums[j] + valueDifference).

To find such an i efficiently, as we iterate j from indexDifference to n-1, we can maintain the minimum and maximum values in the prefix nums[0...j - indexDifference]. We can do this in a single pass. In each iteration, we first update our knowledge of the minimum and maximum values in the valid prefix. The new element to consider for the prefix is at index i = j - indexDifference. We update the indices of the running minimum (minIdx) and maximum (maxIdx) seen so far. After updating, minIdx and maxIdx point to the minimum and maximum values in the range [0, j - indexDifference]. We then check if nums[j] can form a valid pair with nums[minIdx] or nums[maxIdx]. If a pair is found, we return it. If the loop finishes, no such pair exists.

1class Solution {2    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {3        int n = nums.length;4        int minIdx = 0;5        int maxIdx = 0;6 7        for (int j = indexDifference; j < n; j++) {8            int i = j - indexDifference;9 10            // Update min and max indices from the valid range [0, i]11            if (nums[i] < nums[minIdx]) {12                minIdx = i;13            }14            if (nums[i] > nums[maxIdx]) {15                maxIdx = i;16            }17 18            // Check if the current element nums[j] satisfies the valueDifference19            // with the min or max element found so far.20            if (nums[j] - nums[minIdx] >= valueDifference) {21                return new int[]{minIdx, j};22            }23            if (nums[maxIdx] - nums[j] >= valueDifference) {24                return new int[]{maxIdx, j};25            }26        }27 28        return new int[]{-1, -1};29    }30}

Complexity

Time

O(n), where `n` is the number of elements in `nums`. We perform a single pass through the array.

Space

O(1), as we only use a few variables to store indices, regardless of the input size.

Trade-offs

Pros

Highly efficient with a linear time complexity.
Optimal solution for the given constraints.
Uses constant extra space.

Cons

The logic is slightly more complex to reason about compared to the brute-force approach.

Solutions

Solution

1class Solution {2public3  int[] findIndices(int[] nums, int indexDifference, int valueDifference) {4    int mi = 0;5    int mx = 0;6    for (int i = indexDifference; i < nums.length; ++i) {7      int j = i - indexDifference;8      if (nums[j] < nums[mi]) {9        mi = j;10      }11      if (nums[j] > nums[mx]) {12        mx = j;13      }14      if (nums[i] - nums[mi] >= valueDifference) {15        return new int[]{mi, i};16      }17      if (nums[mx] - nums[i] >= valueDifference) {18        return new int[]{mx, i};19      }20    }21    return new int[]{-1, -1};22  }23}

1class Solution {2public:3  vector<int> findIndices(vector<int> &nums, int indexDifference,4                          int valueDifference) {5    int mi = 0, mx = 0;6    for (int i = indexDifference; i < nums.size(); ++i) {7      int j = i - indexDifference;8      if (nums[j] < nums[mi]) {9        mi = j;10      }11      if (nums[j] > nums[mx]) {12        mx = j;13      }14      if (nums[i] - nums[mi] >= valueDifference) {15        return {mi, i};16      }17      if (nums[mx] - nums[i] >= valueDifference) {18        return {mx, i};19      }20    }21    return {-1, -1};22  }23};

1class Solution:2    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]: mi = mx = 0 for i in range(indexDifference, len(nums)): j = i - indexDifference if nums[j] < nums[mi]: mi = j if nums[j] > nums[mx]: mx = j if nums[i] - nums[mi] >= valueDifference: return [mi, i] if nums[mx] - nums[i] >= valueDifference: return [mx, i] return [- 1, - 1]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem