Question

2905. Find Indices With Index and Value Difference II

中文文档

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

Solutions

Solution 1

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]

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};
  }
}

class Solution {
public:
  vector<int> findIndices(vector<int>& nums, int indexDifference, int valueDifference) {
    int mi = 0, mx = 0;
    for (int i = indexDifference; i < nums.size(); ++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 {mi, i};
      }
      if (nums[mx] - nums[i] >= valueDifference) {
        return {mx, i};
      }
    }
    return {-1, -1};
  }
};

func findIndices(nums []int, indexDifference int, valueDifference int) []int {
  mi, mx := 0, 0
  for i := indexDifference; i < len(nums); i++ {
    j := i - indexDifference
    if nums[j] < nums[mi] {
      mi = j
    }
    if nums[j] > nums[mx] {
      mx = j
    }
    if nums[i]-nums[mi] >= valueDifference {
      return []int{mi, i}
    }
    if nums[mx]-nums[i] >= valueDifference {
      return []int{mx, i}
    }
  }
  return []int{-1, -1}
}

function findIndices(nums: number[], indexDifference: number, valueDifference: number): number[] {
  let [mi, mx] = [0, 0];
  for (let i = indexDifference; i < nums.length; ++i) {
    const 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];
}

impl Solution {
  pub fn find_indices(nums: Vec<i32>, index_difference: i32, value_difference: i32) -> Vec<i32> {
    let index_difference = index_difference as usize;
    let mut mi = 0;
    let mut mx = 0;

    for i in index_difference..nums.len() {
      let j = i - index_difference;

      if nums[j] < nums[mi] {
        mi = j;
      }

      if nums[j] > nums[mx] {
        mx = j;
      }

      if nums[i] - nums[mi] >= value_difference {
        return vec![mi as i32, i as i32];
      }

      if nums[mx] - nums[i] >= value_difference {
        return vec![mx as i32, i as i32];
      }
    }

    vec![-1, -1]
  }
}