Scale Engineer

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 <= 105
  • 0 <= nums[i] <= 109
  • 0 <= indexDifference <= 105
  • 0 <= valueDifference <= 109

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

  1. Get the length of the array, n.
  2. Iterate through the array with an index i from 0 to n-1.
  3. Inside the first loop, iterate through the array with an index j from 0 to n-1.
  4. For each pair (i, j), check if abs(i - j) >= indexDifference.
  5. If the index difference condition is met, check if abs(nums[i] - nums[j]) >= valueDifference.
  6. If both conditions are true, return the pair [i, j].
  7. 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.

class Solution {    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {        int n = nums.length;        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                if (Math.abs(i - j) >= indexDifference && Math.abs(nums[i] - nums[j]) >= valueDifference) {                    return new int[]{i, j};                }            }        }        return new int[]{-1, -1};    }}

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.

Solutions

class Solution {public  int[] findIndices(int[] nums, int indexDifference, int valueDifference) {    int mi = 0;    int mx = 0;    for (int i = indexDifference; i < nums.length; ++i) {      int j = i - indexDifference;      if (nums[j] < nums[mi]) {        mi = j;      }      if (nums[j] > nums[mx]) {        mx = j;      }      if (nums[i] - nums[mi] >= valueDifference) {        return new int[]{mi, i};      }      if (nums[mx] - nums[i] >= valueDifference) {        return new int[]{mx, i};      }    }    return new int[]{-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 →

Next problem