LeetCode 2903 - Find Indices With Index and Value Difference I

LeetCode Problem 2903

Difficulty: 🟢 Easy
Topics: Array, Two Pointers

Solution

Problem Understanding

The problem asks us to find two indices i and j in the array such that two conditions are satisfied simultaneously:

1. The indices must be far enough apart:

$$|i - j| \geq indexDifference$$

1. The values at those indices must differ enough:

$$|nums[i] - nums[j]| \geq valueDifference$$

We may return any valid pair if multiple answers exist. If no such pair exists, we return [-1, -1].

An important detail is that i and j are allowed to be equal. This means if indexDifference == 0 and valueDifference == 0, then [0,0] is immediately valid because:

• abs(0 - 0) = 0
• abs(nums[0] - nums[0]) = 0

The input consists of:

• nums, a 0-indexed integer array of length n
• indexDifference, the minimum allowed index distance
• valueDifference, the minimum allowed value distance

The output is a list of two integers representing a valid pair of indices, or [-1, -1] if no valid pair exists.

The constraints are very small:

• n <= 100
• nums[i] <= 50

This tells us that even an O(n²) solution is perfectly acceptable because:

$$100^2 = 10,000$$

which is extremely small for modern computers.

Several edge cases are important to recognize upfront. If indexDifference is larger than the maximum possible index distance, then no pair can exist. If valueDifference == 0, then any pair satisfying the index requirement works because absolute differences are always non-negative. Since i and j may be equal, we must avoid accidentally assuming they must be distinct.

Approaches

Brute Force Approach

The simplest approach is to check every possible pair (i, j).

We iterate through all indices i, and for each i, we iterate through all indices j. For every pair, we check:

• whether abs(i - j) >= indexDifference
• whether abs(nums[i] - nums[j]) >= valueDifference

If both conditions are true, we immediately return [i, j].

This works because it exhaustively checks all possible combinations. Since the problem allows returning any valid answer, we can stop as soon as we find one.

Although brute force is often inefficient, here it is completely acceptable because n <= 100. The worst case requires checking:

$$100 \times 100 = 10,000$$

pairs, which is trivial.

Key Insight for an Improved Solution

Because the constraints are so small, there is actually no need for a more sophisticated optimization. However, we can still slightly improve clarity by observing that we only care about pairs whose index distance is large enough.

Instead of considering arbitrary combinations in an uncontrolled way, we can systematically scan valid pairs and return immediately once a match is found.

The optimal solution for this problem is effectively still quadratic, because no further optimization is necessary under the given constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every pair of indices
Optimal	O(n²)	O(1)	Same complexity, but structured with early return

Algorithm Walkthrough

1. Start by iterating through every index i in the array.

We treat i as the first candidate index. 2. For each i, iterate through every index j.

Since i and j may be equal, we include all indices from 0 to n - 1. 3. Check the index difference condition.

Compute:

$$|i - j|$$

If it is smaller than indexDifference, then this pair is invalid and we continue. 4. Check the value difference condition.

Compute:

$$|nums[i] - nums[j]|$$

If it is at least valueDifference, then both requirements are satisfied. 5. Return the valid pair immediately.

Since the problem allows returning any valid answer, there is no reason to continue searching. 6. If all pairs are exhausted and none satisfy both conditions, return [-1, -1].

Why it works

The algorithm examines every possible pair of indices (i, j). Since every candidate pair is checked exactly once, no valid solution can be missed. If a valid pair exists, it will eventually be encountered and returned. If no valid pair exists, the algorithm correctly finishes and returns [-1, -1].

Python Solution

from typing import List

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]

The implementation directly mirrors the algorithm.

We first compute n, the length of the array. Then we use two nested loops to examine every possible pair (i, j).

For each pair, we check both required conditions in a single if statement. If both are satisfied, we immediately return [i, j].

The early return is important because the problem only asks for one valid answer, not all of them.

If the loops finish without finding a valid pair, we return [-1, -1].

Go Solution

func findIndices(nums []int, indexDifference int, valueDifference int) []int {
	n := len(nums)

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			indexDiff := i - j
			if indexDiff < 0 {
				indexDiff = -indexDiff
			}

			valueDiff := nums[i] - nums[j]
			if valueDiff < 0 {
				valueDiff = -valueDiff
			}

			if indexDiff >= indexDifference &&
				valueDiff >= valueDifference {
				return []int{i, j}
			}
		}
	}

	return []int{-1, -1}
}

The Go implementation follows the same logic as the Python version.

Since Go does not have a built-in integer abs() function, we manually compute absolute values using conditional negation.

Slices are returned directly as []int{i, j} or []int{-1, -1}. Integer overflow is not a concern because values are extremely small under the problem constraints.

Worked Examples

Example 1

Input:

nums = [5,1,4,1]
indexDifference = 2
valueDifference = 4

We iterate through pairs:

i	j	abs(i-j)	abs(nums[i]-nums[j])	Valid?
0	0	0	0	No
0	1	1	4	No
0	2	2	1	No
0	3	3	4	Yes

At (0,3):

• abs(0 - 3) = 3 >= 2
• abs(5 - 1) = 4 >= 4

We immediately return:

[0,3]

Example 2

Input:

nums = [2,1]
indexDifference = 0
valueDifference = 0

First iteration:

i	j	abs(i-j)	abs(nums[i]-nums[j])	Valid?
0	0	0	0	Yes

Both conditions are satisfied immediately:

[0,0]

Example 3

Input:

nums = [1,2,3]
indexDifference = 2
valueDifference = 4

Checking all possible pairs:

i	j	abs(i-j)	abs(nums[i]-nums[j])	Valid?
0	0	0	0	No
0	1	1	1	No
0	2	2	2	No
1	0	1	1	No
1	1	0	0	No
1	2	1	1	No
2	0	2	2	No
2	1	1	1	No
2	2	0	0	No

No valid pair exists, so we return:

[-1,-1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	We check every pair of indices
Space	O(1)	Only a few variables are used

The nested loops examine at most n × n pairs. Since n <= 100, this is extremely efficient in practice. No additional data structures proportional to input size are used, so the space complexity remains constant.

Test Cases

sol = Solution()

# Provided examples
assert sol.findIndices([5, 1, 4, 1], 2, 4) != [-1, -1]  # example 1
assert sol.findIndices([2, 1], 0, 0) != [-1, -1]  # example 2
assert sol.findIndices([1, 2, 3], 2, 4) == [-1, -1]  # example 3

# Single element array
assert sol.findIndices([7], 0, 0) == [0, 0]  # i == j allowed
assert sol.findIndices([7], 1, 0) == [-1, -1]  # impossible index difference

# Exact threshold match
assert sol.findIndices([1, 5], 1, 4) != [-1, -1]  # exact equality works

# Index difference too large
assert sol.findIndices([1, 2, 3], 5, 0) == [-1, -1]  # impossible constraint

# Value difference too large
assert sol.findIndices([1, 2, 3], 1, 100) == [-1, -1]  # impossible value condition

# Multiple valid answers
assert sol.findIndices([10, 1, 20], 1, 5) != [-1, -1]  # several valid pairs

# Equal values
assert sol.findIndices([5, 5, 5], 1, 0) != [-1, -1]  # zero value difference allowed

# Equal indices required
assert sol.findIndices([10], 0, 0) == [0, 0]  # same index valid

# Large boundary size
large_nums = [0] * 100
assert sol.findIndices(large_nums, 99, 1) == [-1, -1]  # max size boundary

Test	Why
[5,1,4,1], 2, 4	Validates standard successful case
[2,1], 0, 0	Ensures equal indices are allowed
[1,2,3], 2, 4	Validates impossible scenario
[7], 0, 0	Tests smallest array
[7], 1, 0	Tests impossible index requirement
[1,5], 1, 4	Confirms equality threshold works
[1,2,3], 5, 0	Tests oversized index difference
[1,2,3], 1, 100	Tests oversized value difference
[10,1,20], 1, 5	Multiple valid answers
[5,5,5], 1, 0	Zero value difference edge case
[0]*100, 99, 1	Maximum input size stress case

Edge Cases

When i == j is the only valid answer

A common mistake is assuming the two indices must be different. The problem explicitly allows i and j to be equal. For example, with nums = [7], indexDifference = 0, and valueDifference = 0, [0,0] is valid. Our implementation handles this naturally because the nested loops include all pairs, including (i, i).

When indexDifference is larger than any possible distance

If indexDifference exceeds n - 1, no pair can satisfy the requirement. For example:

nums = [1,2,3]
indexDifference = 5

The algorithm correctly checks all pairs and eventually returns [-1,-1].

When valueDifference is zero

Since absolute differences are always non-negative, any pair meeting the index requirement automatically satisfies the value condition. A buggy implementation might accidentally use strict comparison (>) instead of inclusive comparison (>=). Our solution correctly uses >=, ensuring exact threshold matches are accepted.

When the threshold is matched exactly

The problem uses greater than or equal to, not strict inequality. For example:

nums = [1,5]
indexDifference = 1
valueDifference = 4

The value difference is exactly 4, which should count as valid. Our implementation correctly handles equality by using >= in both checks.