# Find Indices With Index and Value Difference II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-indices-with-index-and-value-difference-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-indices-with-index-and-value-difference-ii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array
**Companies:** [Paytm](https://scaleengineer.com/companies/paytm)
---
## Problem
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
## 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.
**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.
**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.
### Explanation
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.

```java
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};
    }
}
```
### 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]`.

## Single Pass with Min/Max Tracking
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        int n = nums.length;
        int minIdx = 0;
        int maxIdx = 0;

        for (int j = indexDifference; j < n; j++) {
            int i = j - indexDifference;

            // Update min and max indices from the valid range [0, i]
            if (nums[i] < nums[minIdx]) {
                minIdx = i;
            }
            if (nums[i] > nums[maxIdx]) {
                maxIdx = i;
            }

            // Check if the current element nums[j] satisfies the valueDifference
            // with the min or max element found so far.
            if (nums[j] - nums[minIdx] >= valueDifference) {
                return new int[]{minIdx, j};
            }
            if (nums[maxIdx] - nums[j] >= valueDifference) {
                return new int[]{maxIdx, j};
            }
        }

        return new int[]{-1, -1};
    }
}
```
### Algorithm
1. Initialize `minIdx = 0` and `maxIdx = 0` to track the indices of the minimum and maximum values.
2. Iterate with an index `j` from `indexDifference` to `n-1`.
3. Let `i = j - indexDifference`. This `i` is the latest index that can be paired with `j`.
4. 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`.
5. 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]`.
6. If the loop completes without finding a pair, return `[-1, -1]`.

# Solutions
### Java

```java
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};
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> findIndices(vector<int> &nums, int indexDifference,
                          int valueDifference) {
    int mi = 0, mx = 0;
    for (int i = indexDifference; i < nums.size(); ++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 {mi, i};
      }
      if (nums[mx] - nums[i] >= valueDifference) {
        return {mx, i};
      }
    }
    return {-1, -1};
  }
};

```

### Python

```python
class Solution:
    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]

```