2903. Find Indices With Index and Value Diff I Solution

The 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.

Example 1:

Input: nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
Output: [0,3]
Explanation: 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]
Explanation: 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]
Explanation: 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 <= 100
0 <= nums[i] <= 50
0 <= indexDifference <= 100
0 <= valueDifference <= 50

Approach overview

Problem Overview: You are given an integer array nums and two integers indexDifference and valueDifference. The task is to return two indices i and j such that |i - j| >= indexDifference and |nums[i] - nums[j]| >= valueDifference. If multiple pairs exist, any valid pair works. If none exist, return [-1, -1].

Approach 1: Brute Force (O(n^2) time, O(1) space)

The simplest strategy is to check every possible pair of indices. Iterate i from 0 to n-1, and for each index iterate j from i + indexDifference to the end of the array. For each pair, compute |nums[i] - nums[j]| and verify the value constraint. The moment both constraints are satisfied, return the pair. This method uses only basic iteration over the array and requires constant extra memory. The downside is the quadratic time complexity O(n^2), which becomes slow when the array grows large. Still, it clearly demonstrates the problem constraints and is often the first approach you would write during an interview.

Approach 2: Optimized Sorted Map (O(n log n) time, O(n) space)

A more efficient solution avoids comparing every pair. Iterate through the array while maintaining a sorted map (like TreeMap in Java or a balanced ordered structure in C++/Python). When you reach index j, insert indices that are at least indexDifference behind into the map. The map stores values from nums[i] along with their indices. Because the map is sorted by value, you can quickly search for numbers ≤ nums[j] - valueDifference or ≥ nums[j] + valueDifference. Either case satisfies the value condition. Each insertion and lookup takes O(log n), giving an overall complexity of O(n log n) with O(n) extra space. This approach works well when constraints make the brute force scan too slow.

The problem itself is fundamentally about scanning an array while respecting a minimum index gap. Some brute implementations resemble a sliding window or two pointers scan, but the optimized version relies on ordered value lookups rather than pointer movement.

Recommended for interviews: Start with the brute force idea because it directly reflects the problem definition and shows you understand the constraints. Then optimize using a sorted map to reduce the pair comparisons. Interviewers typically expect candidates to move from O(n^2) to O(n log n) by exploiting ordered value searches.

Approach 1: Brute Force Approach

The brute force approach involves checking every possible pair of indices (i, j) to determine if they satisfy both the index difference and value difference conditions. This can be achieved using two nested loops. Given the constraints, this method is viable.

Python

def find_indices(nums, index_difference, value_difference):
    n = len(nums)
    for i in range(n):
        for j in range(n):
            if abs(i - j) >= index_difference and abs(nums[i] - nums[j]) >= value_difference:
                return [i, j]
    return [-1, -1]

nums = [5, 1, 4, 1]
print(find_indices(nums, 2, 4))

Java

import java.util.Arrays;

public class FindIndices {
    public static int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (Math.abs(i - j) >= indexDifference && Math.abs(nums[i] - nums[j]) >= valueDifference) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[] {-1, -1};
    }
    
    public static void main(String[] args) {
        int[] nums = {5, 1, 4, 1};
        int[] result = findIndices(nums, 2, 4);
        System.out.println(Arrays.toString(result));
    }
}

C++

#include <iostream>
#include <vector>
#include <cmath>

std::vector<int> findIndices(std::vector<int>& nums, int indexDifference, int valueDifference) {
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (std::abs(i - j) >= indexDifference && std::abs(nums[i] - nums[j]) >= valueDifference) {
                return {i, j};
            }
        }
    }
    return {-1, -1};
}

int main() {
    std::vector<int> nums = {5, 1, 4, 1};
    auto result = findIndices(nums, 2, 4);
    std::cout << "[" << result[0] << ", " << result[1] << "]" << std::endl;
}

JavaScript

function findIndices(nums, indexDifference, valueDifference) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (Math.abs(i - j) >= indexDifference && Math.abs(nums[i] - nums[j]) >= valueDifference) {
                return [i, j];
            }
        }
    }
    return [-1, -1];
}

const nums = [5, 1, 4, 1];
console.log(findIndices(nums, 2, 4));

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

int* findIndices(int* nums, int numsSize, int indexDifference, int valueDifference, int* returnSize) {
    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) {
                int* result = (int*)malloc(2 * sizeof(int));
                result[0] = i;
                result[1] = j;
                *returnSize = 2;
                return result;
            }
        }
    }
    int* result = (int*)malloc(2 * sizeof(int));
    result[0] = -1;
    result[1] = -1;
    *returnSize = 2;
    return result;
}

int main() {
    int nums[] = {5, 1, 4, 1};
    int returnSize;
    int* result = findIndices(nums, 4, 2, 4, &returnSize);
    printf("[%d, %d]\n", result[0], result[1]);
    free(result);
    return 0;
}

using System;

class Program {
    public static int[] FindIndices(int[] nums, int indexDifference, int valueDifference) {
        int n = nums.Length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (Math.Abs(i - j) >= indexDifference && Math.Abs(nums[i] - nums[j]) >= valueDifference) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[] {-1, -1};
    }

    static void Main() {
        int[] nums = {5, 1, 4, 1};
        int[] result = FindIndices(nums, 2, 4);
        Console.WriteLine($"[{result[0]}, {result[1]}]");
    }
}

This Python script checks all index pairs using double loops and returns the first valid pair found, meeting the index and value difference requirements.

Complexity

Time Complexity: O(n^2), where n denotes nums length.
Space Complexity: O(1) for constant space usage.

Try this approach in the editor

Approach 2: Optimized Sorted Map Approach

This optimized approach leverages a SortedMap (TreeMap in some languages) to efficiently manage ranges without a direct O(n^2) comparison. The idea is to keep a sliding window of past values sorted and perform a range query over it. This approach can be useful for large input sizes.

Python

from sortedcontainers import SortedList

def find_indices_optimized(nums, index_difference, value_difference):
    sorted_list = SortedList()
    for i in range(len(nums)):
        # Check for a valid range
        idx1 = sorted_list.bisect_left(nums[i] - value_difference)
        idx2 = sorted_list.bisect_right(nums[i] + value_difference)
        if idx1 != idx2:
            for j in range(idx1, idx2):
                if abs(nums[i] - sorted_list[j]) >= value_difference:
                    return [i, i-index_difference]  # returning i as placeholder
        # Keep the window fixed
        sorted_list.add(nums[i])
        if i >= index_difference:
            sorted_list.remove(nums[i - index_difference])
    return [-1, -1]

nums = [5, 1, 4, 1]
print(find_indices_optimized(nums, 2, 4))

Java

import java.util.TreeSet;

public class FindIndicesOptimized {
    public static int[] findIndicesOptimized(int[] nums, int indexDifference, int valueDifference) {
        TreeSet<Integer> sortedSet = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            Integer floor = sortedSet.floor(nums[i] - valueDifference);
            Integer ceil = sortedSet.ceiling(nums[i] + valueDifference);
            if ((floor != null && Math.abs(nums[i] - floor) >= valueDifference) ||
                (ceil != null && Math.abs(nums[i] - ceil) >= valueDifference)) {
                return new int[] {i, sortedSet.contains(nums[i]) ? i - indexDifference : i};
            }
            sortedSet.add(nums[i]);
            if (i >= indexDifference) sortedSet.remove(nums[i - indexDifference]);
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] nums = {5, 1, 4, 1};
        int[] result = findIndicesOptimized(nums, 2, 4);
        System.out.println("[" + result[0] + ", " + result[1] + "]");
    }
}

C++

#include <iostream>
#include <vector>
#include <set>
#include <cmath>

std::vector<int> findIndicesOptimized(const std::vector<int>& nums, int indexDifference, int valueDifference) {
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = i + indexDifference; j < nums.size(); ++j) {
            if (std::abs(nums[i] - nums[j]) >= valueDifference) {
                return {i, j};
            }
        }
    }
    return {-1, -1};
}

int main() {
    std::vector<int> nums = {5, 1, 4, 1};
    auto result = findIndicesOptimized(nums, 2, 4);
    std::cout << "[" << result[0] << ", " << result[1] << "]" << std::endl;
    return 0;
}

This Python example leverages the SortedList from the sortedcontainers library to facilitate efficient order manipulation. The solution queues elements, ensuring past indices meeting the required conditions can be identified swiftly.

Complexity

Time Complexity: O(n log n) due to sorted insertions and deletions.
Space Complexity: O(n) for maintaining the SortedList.

Try this approach in the editor

Approach 3: Two Pointers + Maintaining Maximum and Minimum Values

We use two pointers i and j to maintain a sliding window with a gap of indexDifference, where j and i point to the left and right boundaries of the window, respectively. Initially, i points to indexDifference, and j` points to 0.

We use mi and mx to maintain the indices of the minimum and maximum values to the left of pointer j.

When pointer i moves to the right, we need to update mi and mx. If nums[j] \lt nums[mi], then mi is updated to j; if nums[j] \gt nums[mx], then mx is updated to j. After updating mi and mx, we can determine whether we have found a pair of indices that satisfy the condition. If nums[i] - nums[mi] \ge valueDifference, then we have found a pair of indices [mi, i] that satisfy the condition; if nums[mx] - nums[i] >= valueDifference, then we have found a pair of indices [mx, i] that satisfy the condition.

If pointer i moves to the end of the array and we have not found a pair of indices that satisfy the condition, we return [-1, -1].

The time complexity is O(n), where n is the length of the array. The space complexity is O(1)$.

TypeScript

function findIndices(nums: number[], indexDifference: number, valueDifference: number): number[] {
    let [mi, mx] = [0, 0];
    for (let i = indexDifference; i < nums.length; ++i) {
        const 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];
}

func findIndices(nums []int, indexDifference int, valueDifference int) []int {
	mi, mx := 0, 0
	for i := indexDifference; i < len(nums); i++ {
		j := i - indexDifference
		if nums[j] < nums[mi] {
			mi = j
		}
		if nums[j] > nums[mx] {
			mx = j
		}
		if nums[i]-nums[mi] >= valueDifference {
			return []int{mi, i}
		}
		if nums[mx]-nums[i] >= valueDifference {
			return []int{mx, i}
		}
	}
	return []int{-1, -1}
}

Rust

impl Solution {
    pub fn find_indices(nums: Vec<i32>, index_difference: i32, value_difference: i32) -> Vec<i32> {
        let index_difference = index_difference as usize;
        let mut mi = 0;
        let mut mx = 0;

        for i in index_difference..nums.len() {
            let j = i - index_difference;

            if nums[j] < nums[mi] {
                mi = j;
            }

            if nums[j] > nums[mx] {
                mx = j;
            }

            if nums[i] - nums[mi] >= value_difference {
                return vec![mi as i32, i as i32];
            }

            if nums[mx] - nums[i] >= value_difference {
                return vec![mx as i32, i as i32];
            }
        }

        vec![-1, -1]
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Brute Force Approach	Time Complexity: O(n^2), where n denotes nums length. Space Complexity: O(1) for constant space usage.
Optimized Sorted Map Approach	Time Complexity: O(n log n) due to sorted insertions and deletions. Space Complexity: O(n) for maintaining the SortedList.
Two Pointers + Maintaining Maximum and Minimum Values	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Pair Check	O(n^2)	O(1)	Good for understanding constraints or when the array size is small
Sorted Map Optimization	O(n log n)	O(n)	General case where you need faster lookups for value differences

Frequently asked questions

Is Find Indices With Index and Value Difference I easy or hard?

The problem is classified as Easy on LeetCode with an acceptance rate around 60%. The brute force approach is straightforward, but recognizing the sorted map optimization demonstrates stronger algorithmic thinking and familiarity with ordered data structures.

Find Indices With Index and Value Difference I Python/Java solution

In Python, the brute force solution uses nested loops over the array, while optimized solutions rely on ordered structures like SortedList or manual binary search logic. In Java and C++, TreeMap or ordered maps are commonly used to maintain sorted values and perform O(log n) lookups.

How to solve Find Indices With Index and Value Difference I in O(n)?

A strict O(n) solution is generally not guaranteed because the problem requires ordered comparisons on values. Most optimized implementations use a balanced tree or ordered map, leading to O(n log n) time. The algorithm iterates through the array and performs logarithmic range queries for values outside the allowed difference.

What is the best approach for Find Indices With Index and Value Difference I?

The most efficient approach uses a sorted map (such as TreeMap or an ordered structure) while iterating through the array. It keeps track of candidate indices that satisfy the index difference constraint and performs ordered lookups to find values that meet the value difference condition. This reduces the complexity to O(n log n) compared to the O(n^2) brute force approach.

Is Find Indices With Index and Value Difference I asked at Google/Amazon/Meta?

This problem represents a common interview pattern involving array scanning with index constraints and value comparisons. Variations of this pattern appear in interviews at companies like Amazon and Google where candidates are expected to optimize from brute force to a structure that supports faster value lookups.

What data structure is used in Find Indices With Index and Value Difference I?

The optimized solution uses a sorted map or balanced binary search tree such as TreeMap in Java or ordered containers in C++. This structure allows efficient range queries to quickly check whether a value satisfying the required difference exists among earlier indices.

What is the time complexity of Find Indices With Index and Value Difference I?

The brute force solution runs in O(n^2) time because it checks many pairs of indices. An optimized solution using a sorted map reduces this to O(n log n) by inserting elements and performing logarithmic lookups based on the value difference condition.

Find Indices With Index and Value Difference I solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Sorted Map Approach

Approach 3: Two Pointers + Maintaining Maximum and Minimum Values

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Indices With Index and Value Difference I solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Sorted Map Approach

Approach 3: Two Pointers + Maintaining Maximum and Minimum Values

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems