Find Indices With Index and Value Difference I — Easy Problem & Solution

Problem statement

Find indices i and j with |i - j| >= indexDifference and |nums[i] - nums[j]| >= valueDifference. The two indices may be equal.

Return such a pair as [i, j], or [-1,-1] if none exists. To make the answer unique, return the lexicographically smallest pair with i <= j.

Example 1

Input: nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
Output: [0,3]
Explanation: Indices 0 and 3 are 3 apart and their values differ by 4.

Example 2

Input: nums = [2,1], indexDifference = 0, valueDifference = 0
Output: [0,0]
Explanation: Both differences may be zero, so an index paired with itself works.

Example 3

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

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= indexDifference <= 100
• 0 <= valueDifference <= 50

How to solve Find Indices With Index and Value Difference I

Both conditions are simple comparisons, so enumerate the pairs in lexicographic order and return the first that satisfies them.

Approach

1. Loop i from 0 upward and j from i upward.
2. Check j - i >= indexDifference and |nums[i] - nums[j]| >= valueDifference.
3. Return the first pair that passes; return [-1,-1] if none does.

Why it works

Scanning i then j in increasing order visits pairs in lexicographic order, so the first hit is the smallest. The faster O(n) version slides a gap and keeps the extreme values seen so far, since only the running minimum or maximum can maximise the value gap.

Complexity

• Time — O(n²)
• Space — O(1)

Pitfalls

• indexDifference may be 0, so i == j is a legal answer.
• Restricting to i < j misses that case.
• The result is a pair, not a single index.

Reference solution

Python

from typing import List

def findIndices(nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
    n = len(nums)
    for i in range(n):
        for j in range(i, n):
            if j - i >= indexDifference and abs(nums[i] - nums[j]) >= valueDifference:
                return [i, j]
    return [-1, -1]

JavaScript

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

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy