[Solved]  Find Indices With Index and Value Difference II C++,Python, Java

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 <= 105
• 0 <= nums[i] <= 109
• 0 <= indexDifference <= 105
• 0 <= valueDifference <= 109

Solution

C++

class Solution {
public:
    vector<int> findIndices(vector<int>& nums, int idx, int v) {
        set<pair<int,int>>st;
        for(int i=0;i<nums.size();i++)
        {
            if(i-idx<0)continue;
            st.insert({nums[i-idx],i-idx});
            
            auto val1=*st.begin();
            auto val2=*st.rbegin();
            
            if(abs(nums[i]-val1.first)>=v)
            {
                return {val1.second,i};
            }
            if(abs(nums[i]-val2.first)>=v)return {val2.second,i};
        }
        return {-1,-1};
    }
};

Java

import java.util.TreeSet;
import java.util.Arrays;

public class Solution {
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        int n = nums.length;
        TreeSet<Pair> S = new TreeSet<>();
        int[] result = new int[2];
        
        for (int i = 0; i < n; i++) {
            if (i >= indexDifference) {
                int x = i - indexDifference;
                int y = nums[x];
                S.add(new Pair(y, x));
            }
            
            Pair upperBound = S.ceiling(new Pair(nums[i] + valueDifference, 0));
            if (upperBound != null) {
                result[0] = upperBound.index;
                result[1] = i;
                return result;
            }
            
            Pair lowerBound = S.floor(new Pair(nums[i] - valueDifference + 1, 0));
            if (lowerBound != null) {
                result[0] = lowerBound.index;
                result[1] = i;
                return result;
            }
        }
        
        result[0] = -1;
        result[1] = -1;
        return result;
    }

    class Pair implements Comparable<Pair> {
        int value;
        int index;
        
        public Pair(int value, int index) {
            this.value = value;
            this.index = index;
        }
        
        @Override
        public int compareTo(Pair other) {
            return Integer.compare(this.value, other.value);
        }
    }
}

Python

class Solution(object):
    def findIndices(self, nums, indexDifference, valueDifference):
        min_index = 0
        max_index = 0

        for i in range(indexDifference, len(nums)):
            if nums[i - indexDifference] < nums[min_index]:
                min_index = i - indexDifference
            if nums[i - indexDifference] > nums[max_index]:
                max_index = i - indexDifference
            
            if abs(nums[i] - nums[min_index]) >= valueDifference:
                return [min_index, i]
            if abs(nums[i] - nums[max_index]) >= valueDifference:
                return [max_index, i]
        
        return [-1, -1]

Happy Learning – If you require any further information, feel free to contact me.