# Find Indices With Index and Value Difference I
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-indices-with-index-and-value-difference-i)
Canonical: https://scaleengineer.com/dsa/problems/find-indices-with-index-and-value-difference-i
**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 <= 100`
* `0 <= nums[i] <= 50`
* `0 <= indexDifference <= 100`
* `0 <= valueDifference <= 50`

# Approaches
## Brute-Force Nested Loops
The most straightforward approach is to check every possible pair of indices `(i, j)` in the array. We can use nested loops to iterate through all pairs and verify if they satisfy both the index difference and value difference conditions.
**Time:** O(n^2), where `n` is the number of elements in `nums`. This is because we have two nested loops, each iterating up to `n` times. · **Space:** O(1), as we only use a constant amount of extra space for loop variables.
**Pros:** Simple to understand and implement.; Guaranteed to find a solution if one exists.; Acceptable for the given small constraints.
**Cons:** Inefficient for large input arrays due to its quadratic time complexity.; Performs many redundant checks.
### Explanation
This method involves iterating through each element of the array with an outer loop (let's say with index `i`) and then, for each `i`, iterating through all elements again with an inner loop (with index `j`). For every pair of indices `(i, j)`, we perform two checks:

1.  `abs(i - j) >= indexDifference`
2.  `abs(nums[i] - nums[j]) >= valueDifference`

If both conditions are true, 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]`. Given the small constraints of the problem (`n <= 100`), this approach is feasible and will pass.

**Algorithm:**
*   Iterate through each index `i` from `0` to `n-1`, where `n` is the length of the array.
*   For each `i`, start a nested loop for index `j` from `0` to `n-1`.
*   Inside the inner loop, check if the two conditions are met:
    1.  The absolute difference of indices is sufficient: `abs(i - j) >= indexDifference`.
    2.  The absolute difference of values is sufficient: `abs(nums[i] - nums[j]) >= valueDifference`.
*   If both conditions are true, a valid pair `(i, j)` has been found. Return `[i, j]` immediately.
*   If the loops complete without finding any such pair, it means no solution exists. Return `[-1, -1]`.

```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
*   Iterate through each index `i` from `0` to `n-1`, where `n` is the length of the array.
*   For each `i`, start a nested loop for index `j` from `0` to `n-1`.
*   Inside the inner loop, check if the two conditions are met:
    1.  The absolute difference of indices is sufficient: `abs(i - j) >= indexDifference`.
    2.  The absolute difference of values is sufficient: `abs(nums[i] - nums[j]) >= valueDifference`.
*   If both conditions are true, a valid pair `(i, j)` has been found. Return `[i, j]` immediately.
*   If the loops complete without finding any such pair, it means no solution exists. Return `[-1, -1]`.

## Single Pass with Min/Max Tracking
A more efficient approach is to iterate through the array just once. For each index `j`, we need to find an index `i` such that `i <= j - indexDifference` and `abs(nums[i] - nums[j]) >= valueDifference`. We can achieve this by keeping track of the minimum and maximum values encountered in the valid range for `i` as we iterate through `j`.
**Time:** O(n), where `n` is the length of `nums`. We iterate through the array a single time, and all operations inside the loop are constant time. · **Space:** O(1), as we only use a few variables to store the indices of the running minimum and maximum values.
**Pros:** Optimal time complexity.; Highly efficient, making it suitable for much larger inputs.; Requires only a single pass through the array.
**Cons:** The logic is slightly more complex to devise compared to the brute-force method.
### Explanation
The core idea is to rephrase the problem: for each index `j`, we are looking for a suitable `i` in the prefix of the array, specifically `i` in `[0, j - indexDifference]`. The value condition `abs(nums[i] - nums[j]) >= valueDifference` is most likely to be satisfied if `nums[i]` is either the minimum or the maximum value in that prefix.

We can iterate `j` from `indexDifference` to `n-1`. In each step, we maintain the running minimum and maximum values (and their indices) from the part of the array we are allowed to pick `i` from. The index to consider for updating our running min/max at step `j` is `i = j - indexDifference`. Then, for the current `j`, we check if `nums[j]` paired with the running minimum or maximum satisfies the `valueDifference` condition. If it does, we've found our pair.

**Algorithm:**
*   Initialize `minIdx = 0` and `maxIdx = 0` to keep track of the indices of the minimum and maximum values seen so far.
*   Iterate with index `j` from `indexDifference` to `n-1`.
*   In each iteration, determine the corresponding index `i = j - indexDifference`. This `i` is the latest index to be included in the valid window for the first element of the pair.
*   Update `minIdx` and `maxIdx` by comparing `nums[i]` with the current `nums[minIdx]` and `nums[maxIdx]`.
*   Check if the current element `nums[j]` can form a valid pair with the best candidates found so far (i.e., `nums[minIdx]` or `nums[maxIdx]`):
    *   If `abs(nums[j] - nums[minIdx]) >= valueDifference`, return `[minIdx, j]`.
    *   If `abs(nums[j] - nums[maxIdx]) >= valueDifference`, return `[maxIdx, j]`.
*   If the loop finishes without finding a pair, return `[-1, -1]`.

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

            if (nums[i] < nums[minIdx]) {
                minIdx = i;
            }
            if (nums[i] > nums[maxIdx]) {
                maxIdx = i;
            }

            if (Math.abs(nums[j] - nums[minIdx]) >= valueDifference) {
                return new int[]{minIdx, j};
            }
            if (Math.abs(nums[j] - nums[maxIdx]) >= valueDifference) {
                return new int[]{maxIdx, j};
            }
        }

        return new int[]{-1, -1};
    }
}
```
### Algorithm
*   Initialize `minIdx = 0` and `maxIdx = 0` to keep track of the indices of the minimum and maximum values seen so far.
*   Iterate with index `j` from `indexDifference` to `n-1`.
*   In each iteration, determine the corresponding index `i = j - indexDifference`. This `i` is the latest index to be included in the valid window for the first element of the pair.
*   Update `minIdx` and `maxIdx` by comparing `nums[i]` with the current `nums[minIdx]` and `nums[maxIdx]`.
*   Check if the current element `nums[j]` can form a valid pair with the best candidates found so far (i.e., `nums[minIdx]` or `nums[maxIdx]`):
    *   If `abs(nums[j] - nums[minIdx]) >= valueDifference`, return `[minIdx, j]`.
    *   If `abs(nums[j] - nums[maxIdx]) >= valueDifference`, return `[maxIdx, j]`.
*   If the loop finishes 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]

```