---
description: 'Author: @wingkwong | https://leetcode.com/problems/find-indices-with-index-and-value-difference-i/'
tags: [Array]
---

# 2903 - Find Indices With Index and Value Difference I (Easy) 

## Problem Link

https://leetcode.com/problems/find-indices-with-index-and-value-difference-i/

## Problem Statement

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`

## Approach 1: Brute Force

Basically just follow the instruction - iterate $i$ and $j$ and check if the given conditions are satisfied, return $[i, j]$ if found, else $[-1, -1]$.

<Tabs>
<TabItem value="py" label="Python">
<SolutionAuthor name="@wingkwong"/>

```py
class Solution:
    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i, n):
                if abs(i - j) >= indexDifference and abs(nums[i] - nums[j]) >= valueDifference:
                    return [i, j]
        return [-1, -1]
```

</TabItem>
</Tabs>

## Approach 2: One Pass

The brute force approach takes $O(n ^ 2)$ complexity. We can further optimize to $O(n)$. Since we know that $abs(i - j) >= indexDifference$, we can start iterating from $indexDifference$, then find the current min index and max index in $nums$. If the second condition is satisfied, then return the current index and the target index (either min index or max index depending on the case). See below code for better understanding.

<Tabs>
<TabItem value="py" label="Python">
<SolutionAuthor name="@wingkwong"/>

```py
class Solution:
    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
        mi_i, mx_i = 0, 0
        for i in range(indexDifference, len(nums)):
            if nums[i - indexDifference] < nums[mi_i]: mi_i = i - indexDifference
            if nums[i - indexDifference] > nums[mx_i]: mx_i = i - indexDifference
            if nums[i] - nums[mi_i] >= valueDifference: return [i, mi_i]
            if nums[mx_i] - nums[i] >= valueDifference: return [i, mx_i]
        return [-1, -1]
```

</TabItem>
</Tabs>