Skip to content

2905. Find Indices With Index and Value Difference II 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  vector<int> findIndices(vector<int>& nums, int indexDifference,
                          int valueDifference) {
    // nums[minIndex] := the minimum number with enough index different from the
    // current number
    int minIndex = 0;
    // nums[maxIndex] := the maximum number with enough index different from the
    // current number
    int maxIndex = 0;

    for (int i = indexDifference; i < nums.size(); ++i) {
      if (nums[i - indexDifference] < nums[minIndex])
        minIndex = i - indexDifference;
      if (nums[i - indexDifference] > nums[maxIndex])
        maxIndex = i - indexDifference;
      if (nums[i] - nums[minIndex] >= valueDifference)
        return {i, minIndex};
      if (nums[maxIndex] - nums[i] >= valueDifference)
        return {i, maxIndex};
    }

    return {-1, -1};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
    // nums[minIndex] := the minimum number with enough index different from the current number
    int minIndex = 0;
    // nums[maxIndex] := the maximum number with enough index different from the current number
    int maxIndex = 0;

    for (int i = indexDifference; i < nums.length; ++i) {
      if (nums[i - indexDifference] < nums[minIndex])
        minIndex = i - indexDifference;
      if (nums[i - indexDifference] > nums[maxIndex])
        maxIndex = i - indexDifference;
      if (nums[i] - nums[minIndex] >= valueDifference)
        return new int[] {i, minIndex};
      if (nums[maxIndex] - nums[i] >= valueDifference)
        return new int[] {i, maxIndex};
    }

    return new int[] {-1, -1};
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def findIndices(
      self,
      nums: list[int],
      indexDifference: int,
      valueDifference: int,
  ) -> list[int]:
    # nums[minIndex] := the minimum number with enough index different from the current number
    minIndex = 0
    # nums[maxIndex] := the maximum number with enough index different from the current number
    maxIndex = 0

    for i in range(indexDifference, len(nums)):
      if nums[i - indexDifference] < nums[minIndex]:
        minIndex = i - indexDifference
      if nums[i - indexDifference] > nums[maxIndex]:
        maxIndex = i - indexDifference
      if nums[i] - nums[minIndex] >= valueDifference:
        return [i, minIndex]
      if nums[maxIndex] - nums[i] >= valueDifference:
        return [i, maxIndex]

    return [-1, -1]