3170. Find Indices With Index And Value Difference Ii¶

Difficulty: Medium

3170. Find Indices With Index and Value Difference II

Medium

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 <= 10⁵
0 <= nums[i] <= 10⁹
0 <= indexDifference <= 10⁵
0 <= valueDifference <= 10⁹

Solution¶

class Solution {
    static class Pair {
        int node, idx;
        public Pair(int node, int idx) {
            this.node = node;
            this.idx = idx;
        }
        @Override
        public String toString() {
            return "(" + node + " " + idx + ")";
        }
    }
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        int n = nums.length;
        Pair maxSuff[] = new Pair[n];
        Pair minSuff[] = new Pair[n];
        maxSuff[n - 1] = new Pair(nums[n - 1], n - 1); minSuff[n - 1] = new Pair(nums[n - 1], n - 1);
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] > maxSuff[i + 1].node) {
                maxSuff[i] = new Pair(nums[i], i);
            }
            else 
                maxSuff[i] = new Pair(maxSuff[i + 1].node, maxSuff[i + 1].idx);
            if (nums[i] < minSuff[i + 1].node) {
                minSuff[i] = new Pair(nums[i], i);
            }
            else 
                minSuff[i] = new Pair(minSuff[i + 1].node, minSuff[i + 1].idx);
        } 
        for (int i = 0; i < n; i++) {
            int nextIdx = indexDifference + i;
            if (nextIdx < n) {
                int maxi = maxSuff[nextIdx].node;
                int mini = minSuff[nextIdx].node;
                if (Math.abs(nums[i] - maxi) >= valueDifference) {
                    return new int[]{i, maxSuff[nextIdx].idx};
                }
                if (Math.abs(nums[i] - mini) >= valueDifference) {
                    return new int[]{i, minSuff[nextIdx].idx};
                } 
            }
        }
        return new int[]{-1, -1};
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here