Find Indices With Index and Value Difference II — LeetCode 2905 Python Solution

The problem

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.

Example

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.

Python solution

class Solution:
    def findIndices(
        self, nums: List[int], indexDifference: int, valueDifference: int
    ) -> List[int]:
        mi = mx = 0
        for i in range(indexDifference, len(nums)):
            j = i - indexDifference
            if nums[j] < nums[mi]:
                mi = j
            if nums[j] > nums[mx]:
                mx = j
            if nums[i] - nums[mi] >= valueDifference:
                return [mi, i]
            if nums[mx] - nums[i] >= valueDifference:
                return [mx, i]
        return [-1, -1]

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 2905. Find Indices With Index and Value Difference II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems