1. Find Indices With Index and Value Difference I (LeetCode)
Model answer
The task
Find two indices whose distance is at least indexDifference and whose values differ by at least valueDifference. Return the indices if such a pair exists, or [-1, -1] otherwise.
Key idea
Sweep the array from left to right. For each current index, keep track of the smallest and largest values among earlier indices that are far enough away; either extreme gives the greatest possible value difference from the current value.
Approach
- Visit each index
jas the later index of a potential pair. - Add index
j - indexDifferenceto the eligible earlier indices, if it exists. - Track the eligible indices with the minimum and maximum values.
- Compare
nums[j]with both extremes. Return a qualifying pair, or[-1, -1]if the sweep finds none.
from typing import List
class Solution:
def findIndices(
self, nums: List[int], indexDifference: int, valueDifference: int
) -> List[int]:
min_index = max_index = -1
for j, value in enumerate(nums):
# This index is now far enough from j to be considered.
candidate = j - indexDifference
if candidate >= 0:
if min_index == -1 or nums[candidate] < nums[min_index]:
min_index = candidate
if max_index == -1 or nums[candidate] > nums[max_index]:
max_index = candidate
# An eligible value extreme gives the largest difference.
if min_index != -1 and value - nums[min_index] >= valueDifference:
return [min_index, j]
if max_index != -1 and nums[max_index] - value >= valueDifference:
return [max_index, j]
return [-1, -1]
Complexity:
- Time: O(n), where
nis the array length; each index is processed once. - Space: O(1), using only a few indices.
Common follow-ups
- What if the indices must have an exact distance? Check only the index exactly
indexDifferencepositions away. - Can the method return every qualifying pair? Keep a list of results, though the output can require O(n²) space.
- What if the value difference is zero? The same sweep works; when the index difference is zero, an index may pair with itself.