Find Indices With Index and Value Difference II

MEDIUM

Description

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

Checkout 2 different approaches to solve Find Indices With Index and Value Difference II. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

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].

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 Analysis

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

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find Indices With Index and Value Difference II. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Find Indices With Index and Value Difference II

Patterns:

Two Pointers

Data Structures:

Array

Companies:

Paytm |