Find Indices With Index and Value Difference II

Find Indices With Index and Value Difference II

What is this problem about?

This is the "Medium" version of the previous problem. In the Find Indices With Index and Value Difference II coding problem, the array length $n$ can be up to $10^5$. You still need to find indices $(i, j)$ such that $|i-j| \ge indexDifference$ and $|nums[i]-nums[j]| \ge valueDifference$. Because the constraints are large, an $O(n^2)$ brute-force solution will time out. You need a linear $O(n)$ approach.

Why is this asked in interviews?

Companies like Paytm use this to evaluate if a candidate can optimize a search by using Two Pointers or Precomputation patterns. It tests your ability to maintain a "window of potential candidates" and identify that you only need to compare the current element with the minimum or maximum elements seen so far that are far enough away.

Algorithmic pattern used

This problem uses Tracking Min/Max with a Fixed Offset.

1. Iterate through the array from $i = indexDifference$ to $n-1$.
2. As you move, maintain the index of the minimum (minIndex) and maximum (maxIndex) values encountered so far in the range [0, i - indexDifference].
3. Check if $|nums[i] - nums[minIndex]| \ge valueDifference$ or $|nums[i] - nums[maxIndex]| \ge valueDifference$.
4. If either is true, you've found a valid pair.

Example explanation

nums = [5, 1, 4, 8, 1], idxDiff = 2, valDiff = 4.

1. At i = 2: Valid previous index is 0. minIndex = 0 (val 5), maxIndex = 0 (val 5).
   • $|nums[2] - nums[0]| = |4 - 5| = 1$. (Fail).
2. At i = 3: Valid previous indices are 0 and 1.
   • Update minIndex to 1 (val 1) and maxIndex to 0 (val 5).
   • Check Max: $|nums[3] - nums[0]| = |8 - 5| = 3$.
   • Check Min: $|nums[3] - nums[1]| = |8 - 1| = 7 \ge 4$. Success! Result: [3, 1].

Common mistakes candidates make

• Inefficient Search: Trying to use a Segment Tree or Binary Search, which are $O(n \log n)$ and more complex than the $O(n)$ min/max tracking.
• Updating Min/Max incorrectly: Not ensuring the min/max indices are at least indexDifference away from the current index $i$.
• Off-by-one: Mistakes in the range of valid "previous" indices.

Interview preparation tip

When you need to satisfy a condition like $|A - B| \ge K$, you usually only care about the most extreme candidates for $B$ (the smallest and largest). This "extremum tracking" is a powerful way to reduce $O(n^2)$ problems to $O(n)$.