#2905

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Find Indices With Index and Value Difference II

Locate two indices in an array where both index and value differences meet specified thresholds using precise scanning techniques.

array two pointers

Problem Statement

Given a 0-indexed integer array nums of length n, an integer indexDifference, and an integer valueDifference, find a pair of indices i and j such that abs(i - j) >= indexDifference and abs(nums[i] - nums[j]) >= valueDifference. If multiple pairs exist, any valid pair may be returned.

Return an array answer = [i, j] representing the found indices. If no such pair exists, return [-1, -1]. Constraints: 1 <= n <= 10^5, 0 <= nums[i] <= 10^9, 0 <= indexDifference <= 10^5, 0 <= valueDifference <= 10^9.

Examples

Example 1

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

Output: [0,3]

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]

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]

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 <= 105
0 <= nums[i] <= 109
0 <= indexDifference <= 105
0 <= valueDifference <= 109

Solution Approach

Two-Pointer Scanning with Sliding Window

Maintain a window of candidate indices j in the range [0, i - indexDifference] for each i. Move the window forward as i increases, keeping only indices that could satisfy the valueDifference condition. Check each candidate j for abs(nums[i] - nums[j]) >= valueDifference and return immediately once a valid pair is found.

Invariant Tracking

Within the sliding window, track the minimum and maximum nums[j] to quickly evaluate if any index j can satisfy the valueDifference. This prevents unnecessary comparisons for every i and ensures efficient two-pointer evaluation.

Early Termination and Edge Cases

If indexDifference is zero, allow comparisons within the entire array. Terminate the scan immediately when a valid pair is found. Handle small arrays where no valid indices exist by returning [-1,-1] without extra computation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(n) to O(n log n) depending on whether auxiliary structures like balanced trees are used for min/max tracking. Space complexity depends on window size and tracking structures but is typically O(indexDifference) for the sliding window.

What Interviewers Usually Probe

Focus on how to maintain a candidate range efficiently as i increments.
Watch for missed edge cases when indexDifference is zero or large.
Expect discussion on early termination and value tracking optimizations.

Common Pitfalls or Variants

Common pitfalls

Comparing all pairs blindly leads to O(n^2) time which fails large constraints.
Not updating the sliding window properly can cause invalid index selections.
Forgetting to handle indexDifference = 0 or valueDifference = 0 allows invalid pairs.

Follow-up variants

Find all valid pairs instead of the first pair using the same two-pointer scan.
Use a hash map to track previously seen values to quickly check valueDifference constraints.
Extend the problem to multidimensional arrays with Manhattan distance as indexDifference.

FAQ

What pattern does this problem exemplify?

It follows the two-pointer scanning with invariant tracking pattern, focusing on maintaining a candidate range while checking constraints.

Why is a sliding window needed for indexDifference?

The window ensures we only consider indices j where abs(i - j) >= indexDifference, avoiding unnecessary checks for invalid pairs.

Can indexDifference be zero?

Yes, when zero, the entire array can be compared for valueDifference, but care must be taken to avoid duplicates unless allowed.

How do I handle large arrays efficiently?

Use the sliding window with min/max or balanced tree tracking to limit comparisons and maintain O(n log n) or O(n) performance.

What if multiple valid pairs exist?

Any pair meeting the constraints can be returned; GhostInterview provides the first pair found efficiently.

terminal

Solution

Solution 1

#### Python3

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]

Continue Practicing

#2903 find indices with index and value difference i #2856 minimum array length after pair removals #2970 count the number of incremovable subarrays i