Find Indices With Index and Value Difference II

Find Indices With Index and Value Difference II - 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
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.

Input & Output

Example 1 — Basic Case

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

› Output: [0,3]

💡 Note: Index difference: |0-3| = 3 ≥ 2 ✓, Value difference: |5-1| = 4 ≥ 4 ✓

Example 2 — No Valid Pair

$ Input: nums = [2,1], indexDifference = 0, valueDifference = 0

› Output: [0,0]

💡 Note: Index difference: |0-0| = 0 ≥ 0 ✓, Value difference: |2-2| = 0 ≥ 0 ✓

Example 3 — Large Differences Required

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

› Output: [-1,-1]

💡 Note: No pair satisfies both constraints: max value difference is |1-3| = 2 < 4

Constraints

2 ≤ nums.length ≤ 5 × 10⁵
0 ≤ indexDifference < nums.length
0 ≤ valueDifference ≤ 10⁹
0 ≤ nums[i] ≤ 5 × 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input

Array [5,1,4,1] with indexDiff=2, valueDiff=4

Process

Find indices i,j where |i-j|≥2 and |nums[i]-nums[j]|≥4

Output

Return [0,3] as |0-3|=3≥2 and |5-1|=4≥4

Key Takeaway

🎯 Key Insight: Use efficient min/max tracking to avoid checking all pairs while maintaining index difference constraints

Asked in

G Google 12 a Amazon 8 m Microsoft 6

The key insight is to track minimum and maximum values efficiently while maintaining the index difference constraint. The optimized approach uses a single pass with min/max tracking to achieve O(n) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Pairs	O(n²)	O(1)	Check every possible pair of indices to see if they satisfy both conditions
Optimized with Min/Max Tracking	O(n)	O(1)	Track minimum and maximum values with their indices in a single pass for efficient comparison
Two Pointers with Sliding Window	O(n²)	O(1)	Use sliding window to maintain index difference constraint while tracking min/max values

Brute Force - Check All Pairs — Algorithm Steps

Iterate through all pairs of indices (i, j)
Check if |i - j| >= indexDifference
Check if |nums[i] - nums[j]| >= valueDifference
Return first valid pair or [-1, -1]

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with first pair (0,0)

Check Conditions

Verify index and value differences

Return Result

First valid pair or [-1,-1]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int indexDifference, int valueDifference) {
    int* result = (int*)malloc(2 * sizeof(int));
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < numsSize; j++) {
            if (abs(i - j) >= indexDifference && abs(nums[i] - nums[j]) >= valueDifference) {
                result[0] = i;
                result[1] = j;
                return result;
            }
        }
    }
    
    result[0] = -1;
    result[1] = -1;
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int indexDifference, valueDifference;
    scanf("%d", &indexDifference);
    scanf("%d", &valueDifference);
    
    int* result = solution(nums, numsSize, indexDifference, valueDifference);
    printf("[%d,%d]\n", result[0], result[1]);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops check all n×n pairs of indices

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses constant extra variables

✓ Linear Space

12.4K Views

Medium Frequency

~25 min Avg. Time

289 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler