LeetCode 2905 - Find Indices With Index and Value Difference II

Difficulty: 🟡 Medium
Topics: Array, Two Pointers

Solution

Problem Understanding

The problem asks us to find two indices i and j in an integer array nums that satisfy two conditions simultaneously: the absolute difference between the indices must be at least indexDifference (abs(i - j) >= indexDifference) and the absolute difference between the values at these indices must be at least valueDifference (abs(nums[i] - nums[j]) >= valueDifference). The output is a pair of indices [i, j] that satisfies these conditions, or [-1, -1] if no such pair exists.

The input array nums can be large (up to 10^5 elements), and the values themselves can be very large (up to 10^9). The index difference and value difference constraints can also reach their maximums, which means a naive O(n²) comparison approach could be too slow. Notably, i and j can be the same, which simplifies some cases when indexDifference or valueDifference is 0.

Key edge cases include small arrays (length 1 or 2), cases where indexDifference = 0 or valueDifference = 0, and cases where no valid indices exist. These can easily trip up implementations that assume i != j or that always require a positive difference.

Approaches

Brute Force Approach

The brute force solution is straightforward: iterate over every pair (i, j) in the array and check if both abs(i - j) >= indexDifference and abs(nums[i] - nums[j]) >= valueDifference hold. This guarantees correctness because it explicitly checks all possible pairs. However, it requires O(n²) time since every pair of indices must be compared, which is too slow for the input constraints (n up to 10^5).

Optimal Approach

To optimize, observe that for each index i, we only need to compare nums[i] with numbers that are at least indexDifference away. This suggests maintaining a sliding window of previously seen numbers that are at least indexDifference apart.

We can use a balanced search tree (or a data structure that allows fast min/max queries, like a SortedList in Python) to quickly check if there exists a number x in the window such that abs(nums[i] - x) >= valueDifference. The logic is: for the current nums[i], check if any number in the sliding window is ≤ nums[i] - valueDifference or ≥ nums[i] + valueDifference. If such a number exists, the corresponding indices form a valid answer.

By using this approach, we can reduce the time complexity from O(n²) to O(n log n), as insertion and search in a balanced tree take O(log n) time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks all index pairs explicitly
Sliding Window + BST	O(n log n)	O(indexDifference)	Maintains a window of size up to indexDifference using a sorted data structure for fast range queries

Algorithm Walkthrough

Initialize an empty balanced tree or sorted list window to store values that are eligible for comparison (i.e., numbers that are at least indexDifference apart from the current index).
Iterate through the array nums using index i.
For the current nums[i], check in window if there exists any value x such that x <= nums[i] - valueDifference or x >= nums[i] + valueDifference. If found, return [index_of_x, i].
Insert nums[i] into the window along with its index so we can recover the original index.
If the size of window exceeds indexDifference, remove the oldest element to maintain the sliding window constraint.
If no valid pair is found by the end of iteration, return [-1, -1].

Why it works: The sliding window ensures that all comparisons respect the indexDifference requirement. The sorted nature of the window ensures we can efficiently check for any value that meets the valueDifference condition. Together, these guarantee correctness.

Python Solution

from bisect import bisect_left, bisect_right, insort
from typing import List

class Solution:
    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
        if indexDifference == 0 and valueDifference == 0:
            return [0, 0]
        
        window = []  # will store tuples (num, index)
        for i, num in enumerate(nums):
            # Find the position where num - valueDifference would fit
            pos_low = bisect_left(window, (num - valueDifference, -float('inf')))
            if pos_low < len(window):
                candidate_num, candidate_index = window[pos_low]
                if abs(candidate_num - num) >= valueDifference:
                    return [candidate_index, i]
            
            # Check the element just before pos_low
            if pos_low > 0:
                candidate_num, candidate_index = window[pos_low - 1]
                if abs(candidate_num - num) >= valueDifference:
                    return [candidate_index, i]

            # Insert current number into the window
            insort(window, (num, i))

            # Maintain window size according to indexDifference
            if len(window) > indexDifference:
                # remove the element which is too far
                to_remove = (nums[i - indexDifference], i - indexDifference)
                del window[bisect_left(window, to_remove)]

        return [-1, -1]

Explanation: We use bisect operations to find potential matches in the sorted window efficiently. The window only contains numbers whose indices are at least indexDifference behind the current index, guaranteeing the index constraint. Inserting and removing elements preserves sorted order.

Go Solution

package main

import (
	"sort"
)

type NumIndex struct {
	num   int
	index int
}

func findIndices(nums []int, indexDifference int, valueDifference int) []int {
	if indexDifference == 0 && valueDifference == 0 {
		return []int{0, 0}
	}

	window := []NumIndex{}

	for i, num := range nums {
		posLow := sort.Search(len(window), func(j int) bool { return window[j].num >= num - valueDifference })
		if posLow < len(window) && abs(window[posLow].num - num) >= valueDifference {
			return []int{window[posLow].index, i}
		}
		if posLow > 0 && abs(window[posLow-1].num - num) >= valueDifference {
			return []int{window[posLow-1].index, i}
		}

		// insert current num
		window = append(window, NumIndex{num, i})
		sort.Slice(window, func(a, b int) bool { return window[a].num < window[b].num })

		if len(window) > indexDifference {
			toRemove := NumIndex{nums[i - indexDifference], i - indexDifference}
			for j, val := range window {
				if val == toRemove {
					window = append(window[:j], window[j+1:]...)
					break
				}
			}
		}
	}

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

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

Go-specific notes: We use a slice to represent the window and sort.Search for binary search. Inserting and deleting requires re-sorting or linear removal, which is less efficient than Python's SortedList. For production-scale performance, a balanced tree implementation would be better in Go.

Worked Examples

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

i	num	window (num,index)	Action
0	5	[]	insert (5,0)
1	1	[(5,0)]	no candidate, insert (1,1)
2	4	[(1,1),(5,0)]	candidate (0,5) satisfies valueDifference and indexDifference, return [0,2]

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

Since both differences are 0, return [0,0] immediately.

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

No element pair satisfies both constraints. Return [-1,-1].

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log indexDifference)	Each insert/search in the window takes O(log window_size), window_size ≤ indexDifference
Space	O(indexDifference)	Only store up to indexDifference elements in the window

The optimization comes from avoiding O(n²) pairwise checks and maintaining only a sliding window of relevant elements.

Test Cases

# Provided examples
assert Solution().findIndices([5,1,4,1], 2, 4) in [[0,2],[2,0],[0,3],[