Find Indices With Index and Value Difference I

Easy
757.

Find Indices With Index and Value Difference I

Find Indices With Index and Value Difference I is an easy coding problem on arrays and two pointers, asked in Amazon, Adobe and TCS interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} indexDifference
 * @param {number} valueDifference
 * @return {number[]}
 */
var findIndices = function(nums, indexDifference, valueDifference) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Indices With Index and Value Difference I — Solution

Find Indices With Index and Value Difference I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find Indices With Index and Value Difference I is an easy coding problem on arrays and two pointers, asked in Amazon, Adobe and TCS interviews.

  • Difficulty: Easy
  • Topics: Arrays, Two Pointers
  • Asked at: Amazon, Adobe, TCS
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Find Indices With Index and Value Difference I

  1. Hint 1

    At this size the double loop over i <= j is exhaustive and cheap.

  2. Hint 2

    Scanning i outer and j inner in increasing order naturally yields the lexicographically smallest pair first.

  3. Hint 3

    The linear version keeps the running minimum and maximum among indices at least indexDifference behind j.

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]

Java

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

C++

vector<int> findIndices(vector<int>& nums, int indexDifference, int valueDifference) {
    int n = (int) nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (j - i >= indexDifference && 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique