Find Indices With Index and Value Difference I

Difficulty: Easy | Acceptance: 60.30% | Paid: No Topics: Array, Two Pointers

You are given a 0-indexed integer array nums of length n, and two integers indexDifference and valueDifference.

Return the indices i and j such that:

• i != j,
• abs(i - j) >= indexDifference, and
• abs(nums[i] - nums[j]) >= valueDifference.

If there are multiple valid pairs, return any of them.

If no such pair exists, return [-1, -1].

• Examples
• Constraints
• Brute Force
• Sliding Window with Min/Max Tracking

Examples

Input: nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
Output: [0,3]
Explanation: (0,3) is a valid pair because abs(0 - 3) >= 2 and abs(nums[0] - nums[3]) >= 4.

Input: nums = [2,2], indexDifference = 2, valueDifference = 0
Output: [0,1]
Explanation: (0,1) is a valid pair because abs(0 - 1) >= 2 and abs(nums[0] - nums[1]) >= 0.
Note that (0,1) and (1,0) are both valid pairs.

Input: nums = [3,0,3,2,4,2], indexDifference = 2, valueDifference = 1
Output: [0,2]
Explanation: (0,2) is a valid pair because abs(0 - 2) >= 2 and abs(nums[0] - nums[2]) >= 1.

Constraints

n == nums.length
1 <= n <= 100
0 <= nums[i] <= 50
0 <= indexDifference <= 100
0 <= valueDifference <= 50

Brute Force

Intuition Since the constraints are small (n <= 100), we can simply check every possible pair of indices (i, j) to see if they satisfy the conditions.

Steps

• Iterate through the array with index i.
• For each i, iterate through the array with index j.
• Check if i != j, abs(i - j) >= indexDifference, and abs(nums[i] - nums[j]) >= valueDifference.
• If a valid pair is found, return it immediately.
• If the loops finish without finding a pair, return [-1, -1].

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]

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple and effective for the given constraints.

Sliding Window with Min/Max Tracking

Intuition For a given index i, we only need to check indices j such that abs(i - j) >= indexDifference. This means j must be at least indexDifference away from i. We can iterate through the array and maintain a sliding window of valid j indices. To satisfy the value difference efficiently, we only need to know the minimum and maximum values in the valid window, as these are the only candidates that can satisfy abs(nums[i] - nums[j]) >= valueDifference.

Steps

• Initialize variables to track the minimum value (minVal), its index (minIdx), maximum value (maxVal), and its index (maxIdx) in the valid window.
• Iterate through the array with index i.
• The valid window for j is indices 0 to i - indexDifference.
• If i - indexDifference >= 0, we expand the window to include the element at i - indexDifference. Update minVal, minIdx, maxVal, and maxIdx if this new element is smaller or larger.
• Check if nums[i] satisfies the value difference condition with minVal or maxVal from the window.
• If abs(nums[i] - minVal) >= valueDifference and minIdx != i, return [i, minIdx].
• If abs(nums[i] - maxVal) >= valueDifference and maxIdx != i, return [i, maxIdx].
• If the loop completes, return [-1, -1].

class Solution:
    def findIndices(self, nums: list[int], indexDifference: int, valueDifference: int) -> list[int]:
        n = len(nums)
        min_val = nums[0]
        min_idx = 0
        max_val = nums[0]
        max_idx = 0
        
        for i in range(n):
            # The valid window for j is [0, i - indexDifference]
            if i - indexDifference >= 0:
                j = i - indexDifference
                if nums[j] < min_val:
                    min_val = nums[j]
                    min_idx = j
                if nums[j] > max_val:
                    max_val = nums[j]
                    max_idx = j
            
            # Check against the min and max in the valid window
            if abs(nums[i] - min_val) >= valueDifference and min_idx != i:
                return [i, min_idx]
            if abs(nums[i] - max_val) >= valueDifference and max_idx != i:
                return [i, max_idx]
                
        return [-1, -1]

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimized for larger input sizes by reducing the inner loop to constant time checks.