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.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6

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

1
2
3
4

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

Solution

Method 1 – Brute Force Pair Search

Intuition

The problem asks for any pair of indices (i, j) such that the absolute difference of their indices is at least indexDifference and the absolute difference of their values is at least valueDifference. Since the constraints are small, we can check all possible pairs.

Approach

  1. Iterate over all possible pairs (i, j) with two nested loops.
  2. For each pair, check if both abs(i - j) >= indexDifference and abs(nums[i] - nums[j]) >= valueDifference.
  3. If such a pair is found, return [i, j] immediately.
  4. If no such pair exists, return [-1, -1].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    vector<int> findIndices(vector<int>& nums, int indexDifference, int valueDifference) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (abs(i - j) >= indexDifference && abs(nums[i] - nums[j]) >= valueDifference)
                    return {i, j};
            }
        }
        return {-1, -1};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func findIndices(nums []int, indexDifference int, valueDifference int) []int {
    n := len(nums)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if abs(i-j) >= indexDifference && abs(nums[i]-nums[j]) >= valueDifference {
                return []int{i, j}
            }
        }
    }
    return []int{-1, -1}
}
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun findIndices(nums: IntArray, indexDifference: Int, valueDifference: Int): IntArray {
        val n = nums.size
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (kotlin.math.abs(i - j) >= indexDifference && kotlin.math.abs(nums[i] - nums[j]) >= valueDifference)
                    return intArrayOf(i, j)
            }
        }
        return intArrayOf(-1, -1)
    }
}
1
2
3
4
5
6
7
8

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(n):
                if abs(i - j) >= indexDifference and abs(nums[i] - nums[j]) >= valueDifference:
                    return [i, j]
        return [-1, -1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn find_indices(nums: Vec<i32>, index_difference: i32, value_difference: i32) -> Vec<i32> {
        let n = nums.len();
        for i in 0..n {
            for j in 0..n {
                if (i as i32 - j as i32).abs() >= index_difference && (nums[i] - nums[j]).abs() >= value_difference {
                    return vec![i as i32, j as i32];
                }
            }
        }
        vec![-1, -1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    findIndices(nums: number[], indexDifference: number, valueDifference: number): number[] {
        const n = nums.length;
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (Math.abs(i - j) >= indexDifference && Math.abs(nums[i] - nums[j]) >= valueDifference)
                    return [i, j];
            }
        }
        return [-1, -1];
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), where n is the length of nums. We check all pairs of indices.
  • 🧺 Space complexity: O(1), only a few variables are used for iteration and output.