Scale Engineer

Find Indices With Index and Value Difference I

Easy
#2584Time: O(n^2), where `n` is the number of elements in `nums`. This is because we have two nested loops, each iterating up to `n` times.Space: O(1), as we only use a constant amount of extra space for loop variables.1 company
Patterns
Two Pointers
Data structures
Array
Companies
Paytm

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to check every possible pair of indices (i, j) in the array. We can use nested loops to iterate through all pairs and verify if they satisfy both the index difference and value difference conditions.

Algorithm

  • Iterate through each index i from 0 to n-1, where n is the length of the array.
  • For each i, start a nested loop for index j from 0 to n-1.
  • Inside the inner loop, check if the two conditions are met:
    1. The absolute difference of indices is sufficient: abs(i - j) >= indexDifference.
    2. The absolute difference of values is sufficient: abs(nums[i] - nums[j]) >= valueDifference.
  • If both conditions are true, a valid pair (i, j) has been found. Return [i, j] immediately.
  • If the loops complete without finding any such pair, it means no solution exists. Return [-1, -1].

Walkthrough

This method involves iterating through each element of the array with an outer loop (let's say with index i) and then, for each i, iterating through all elements again with an inner loop (with index j). For every pair of indices (i, j), we perform two checks:

  1. abs(i - j) >= indexDifference
  2. abs(nums[i] - nums[j]) >= valueDifference

If both conditions are true, we have found a valid pair, and we can immediately return [i, j]. If the loops complete without finding any such pair, it means no solution exists, and we return [-1, -1]. Given the small constraints of the problem (n <= 100), this approach is feasible and will pass.

Algorithm:

  • Iterate through each index i from 0 to n-1, where n is the length of the array.
  • For each i, start a nested loop for index j from 0 to n-1.
  • Inside the inner loop, check if the two conditions are met:
    1. The absolute difference of indices is sufficient: abs(i - j) >= indexDifference.
    2. The absolute difference of values is sufficient: abs(nums[i] - nums[j]) >= valueDifference.
  • If both conditions are true, a valid pair (i, j) has been found. Return [i, j] immediately.
  • If the loops complete without finding any such pair, it means no solution exists. Return [-1, -1].
class Solution {    public 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};    }}

Complexity

Time

O(n^2), where `n` is the number of elements in `nums`. This is because we have two nested loops, each iterating up to `n` times.

Space

O(1), as we only use a constant amount of extra space for loop variables.

Trade-offs

Pros

  • Simple to understand and implement.

  • Guaranteed to find a solution if one exists.

  • Acceptable for the given small constraints.

Cons

  • Inefficient for large input arrays due to its quadratic time complexity.

  • Performs many redundant checks.

Solutions

class Solution { public int [] findIndices ( int [] nums , int indexDifference , int valueDifference ) { int mi = 0 ; int mx = 0 ; for ( int i = indexDifference ; i < nums . length ; ++ i ) { int j = i - indexDifference ; if ( nums [ j ] < nums [ mi ]) { mi = j ; } if ( nums [ j ] > nums [ mx ]) { mx = j ; } if ( nums [ i ] - nums [ mi ] >= valueDifference ) { return new int [] { mi , i }; } if ( nums [ mx ] - nums [ i ] >= valueDifference ) { return new int [] { mx , i }; } } return new int [] {- 1 , - 1 }; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem