Find Indices With Index and Value Difference I

EASY

Description

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

Checkout 2 different approaches to solve Find Indices With Index and Value Difference I. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Nested Loops

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

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:

abs(i - j) >= indexDifference
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 Analysis

Time Complexity: 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 Complexity: O(1), as we only use a constant amount of extra space for loop variables.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find Indices With Index and Value Difference I. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Find Indices With Index and Value Difference I

Patterns:

Two Pointers

Data Structures:

Array

Companies:

Paytm |