Find Indices With Index and Value Difference I

Find Indices With Index and Value Difference I - 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, and
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 = [4,1,2,3], indexDifference = 1, valueDifference = 1

› Output: [2,3]

💡 Note: At indices 2 and 3: abs(2-3) = 1 >= 1 (index diff), abs(2-3) = 1 >= 1 (value diff). Both conditions satisfied.

Example 2 — No Valid Pair

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

› Output: [-1,-1]

💡 Note: Only valid index pairs are (0,2) with values (1,3). Value difference is |1-3| = 2 < 4, so no solution exists.

Example 3 — Same Index

$ Input: nums = [5], indexDifference = 0, valueDifference = 0

› Output: [0,0]

💡 Note: With single element and both differences = 0, we can return the same index twice: abs(0-0) = 0 >= 0, abs(5-5) = 0 >= 0.

Constraints

1 ≤ nums.length ≤ 100
0 ≤ indexDifference ≤ nums.length - 1
0 ≤ valueDifference ≤ 50
0 ≤ nums[i] ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Input

Array with index and value difference requirements

Process

Find pair satisfying both distance conditions

Output

Return indices or [-1,-1] if none found

Key Takeaway

🎯 Key Insight: Need to find two indices satisfying both distance constraints simultaneously

Asked in

G Google 15 M Microsoft 12

The key insight is to check both index distance and value difference conditions systematically. The brute force approach checks all pairs in O(n²) time. An optimized version can skip pairs that don't meet the index difference requirement first. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Two Pointers	O(n²)	O(1)	Skip unnecessary pairs by checking index difference first
Brute Force	O(n²)	O(1)	Check all possible pairs of indices

Optimized Two Pointers — Algorithm Steps

For each index i
Only check indices j where abs(i-j) >= indexDifference
Check value difference condition
Return first valid pair

Visualization

Tap to expand

Step-by-Step Walkthrough

Filter by Index

For each i, only check j where abs(i-j) >= indexDiff

Check Value

Among valid index pairs, check value difference

Result

Return first pair satisfying both conditions

Code -

solution.c — C

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

int max(int a, int b) {
    return (a > b) ? a : b;
}

int* solution(int* nums, int numsSize, int indexDifference, int valueDifference) {
    int* result = (int*)malloc(2 * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        // Check indices to the left
        for (int j = max(0, i - indexDifference); j < i; j++) {
            if (abs(nums[i] - nums[j]) >= valueDifference) {
                result[0] = j;
                result[1] = i;
                return result;
            }
        }
        // Check indices to the right
        for (int j = i + indexDifference; j < numsSize; j++) {
            if (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* ptr = strchr(line, '[');
    ptr++;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    int indexDifference = atoi(line);
    
    fgets(line, sizeof(line), stdin);
    int valueDifference = atoi(line);
    
    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²)

In worst case still checks many pairs, but fewer than brute force

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses constant extra variables

✓ Linear Space

8.5K Views

Medium Frequency

~15 min Avg. Time

234 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

Optimized Two Pointers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler