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, andabs(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 <= 1000 <= nums[i] <= 500 <= indexDifference <= 1000 <= valueDifference <= 50
Solutions#
Solution 1: Two Pointers + Maintaining Maximum and Minimum Values#
We use two pointers $i$ and $j$ to maintain a sliding window with a gap of $indexDifference$, where $j$ and $i$ point to the left and right boundaries of the window, respectively. Initially, $i$ points to $indexDifference$, and $j` points to $0$.
We use $mi$ and $mx$ to maintain the indices of the minimum and maximum values to the left of pointer $j$.
When pointer $i$ moves to the right, we need to update $mi$ and $mx$. If $nums[j] \lt nums[mi]$, then $mi$ is updated to $j$; if $nums[j] \gt nums[mx]$, then $mx$ is updated to $j$. After updating $mi$ and $mx$, we can determine whether we have found a pair of indices that satisfy the condition. If $nums[i] - nums[mi] \ge valueDifference$, then we have found a pair of indices $[mi, i]$ that satisfy the condition; if $nums[mx] - nums[i] >= valueDifference$, then we have found a pair of indices $[mx, i]$ that satisfy the condition.
If pointer $i$ moves to the end of the array and we have not found a pair of indices that satisfy the condition, we return $[-1, -1]$.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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};
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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};
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| func findIndices(nums []int, indexDifference int, valueDifference int) []int {
mi, mx := 0, 0
for i := indexDifference; i < len(nums); i++ {
j := i - indexDifference
if nums[j] < nums[mi] {
mi = j
}
if nums[j] > nums[mx] {
mx = j
}
if nums[i]-nums[mi] >= valueDifference {
return []int{mi, i}
}
if nums[mx]-nums[i] >= valueDifference {
return []int{mx, i}
}
}
return []int{-1, -1}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| function findIndices(nums: number[], indexDifference: number, valueDifference: number): number[] {
let [mi, mx] = [0, 0];
for (let i = indexDifference; i < nums.length; ++i) {
const 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];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| impl Solution {
pub fn find_indices(nums: Vec<i32>, index_difference: i32, value_difference: i32) -> Vec<i32> {
let index_difference = index_difference as usize;
let mut mi = 0;
let mut mx = 0;
for i in index_difference..nums.len() {
let j = i - index_difference;
if nums[j] < nums[mi] {
mi = j;
}
if nums[j] > nums[mx] {
mx = j;
}
if nums[i] - nums[mi] >= value_difference {
return vec![mi as i32, i as i32];
}
if nums[mx] - nums[i] >= value_difference {
return vec![mx as i32, i as i32];
}
}
vec![-1, -1]
}
}
|
