We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Indices With Index and Value Difference II

Number: 3170

Difficulty: Medium

Paid? No

Companies: Paytm

Problem Description

Given a 0-indexed integer array nums of length n, an integer indexDifference, and an integer valueDifference, find two indices i and j (where 0 ≤ i, j < n) that satisfy both:

  1. |i - j| ≥ indexDifference
  2. |nums[i] - nums[j]| ≥ valueDifference

If there exists such a pair, return any one pair [i, j]. Otherwise, return [-1, -1]. (Note: i and j are allowed to be equal.)

Key Insights

  • The two conditions are independent and symmetric. Without loss of generality, you can look for a pair with i < j.
  • When indexDifference > 0 (or when valueDifference > 0), i and j must be distinct; however, if both are 0 then even [0,0] is a valid answer.
  • A brute force check over all pairs would be too slow for n up to 10⁵, so we need an O(n) or O(n log n) solution.
  • For each index i, consider the range [i + offset, n - 1] (where offset is indexDifference if indexDifference > 0, and when indexDifference is 0 and valueDifference > 0, offset is taken as 1 because i by itself cannot provide a nonzero value difference).
  • Precompute suffix arrays that store the minimum and maximum numbers (along with their indices) from a given position to the end. Then for each index i, one can check in O(1) time whether there exists a later index that satisfies the value difference condition.

Space and Time Complexity

Time Complexity: O(n) – we preprocess suffix arrays in one pass and then iterate through indices once. Space Complexity: O(n) – additional arrays are used to store suffix minimums and maximums and their corresponding indices.

Solution

We first handle the special case: if indexDifference == 0 and valueDifference == 0, then [0, 0] is immediately valid. Otherwise, we define an offset: if indexDifference > 0 then offset = indexDifference; if indexDifference == 0 but valueDifference > 0 then we set offset = 1 because we need two distinct indices to have a nonzero difference in value.

We build two suffix arrays:

  • suffixMin: at each index i, it stores the minimum value in nums from index i to the end, along with the index where this minimum occurred.
  • suffixMax: similarly, it stores the maximum value and the corresponding index.

For each index i from 0 to n - offset:

  • We look into the range starting at index (i + offset) (which represents all indices j where j - i is enough).
  • We check if the absolute difference between nums[i] and the minimum or maximum value in that suffix range is at least valueDifference.
  • If so, we return the pair [i, j] (using j as the index where that min or max occurred).

If no valid pair is found after scanning, we return [-1, -1].

Code Solutions

Below are the solutions in Python, JavaScript, C++, and Java with detailed line-by-line comments.

# Python solution

def findIndices(nums, indexDifference, valueDifference):
    n = len(nums)
    # Special case: if both indexDifference and valueDifference are 0, [0,0] is valid.
    if indexDifference == 0 and valueDifference == 0:
        return [0, 0]
    # Determine offset: if indexDifference > 0, use indexDifference, else if valueDifference > 0 use 1.
    offset = indexDifference if indexDifference > 0 else 1

    # Precompute suffix minimum values and corresponding indices.
    suffixMin = [0] * n       # suffixMin[i] will hold the minimum value from nums[i] to nums[n-1]
    suffixMinIdx = [0] * n    # suffixMinIdx[i] will hold the index of that minimum value

    # Precompute suffix maximum values and corresponding indices.
    suffixMax = [0] * n       # suffixMax[i] will hold the maximum value from nums[i] to nums[n-1]
    suffixMaxIdx = [0] * n    # suffixMaxIdx[i] will hold the index of that maximum value

    # Initialize the last element for both suffix arrays.
    suffixMin[n - 1] = nums[n - 1]
    suffixMinIdx[n - 1] = n - 1
    suffixMax[n - 1] = nums[n - 1]
    suffixMaxIdx[n - 1] = n - 1

    # Fill suffix arrays from n-2 down to 0.
    for i in range(n - 2, -1, -1):
        # For minimum
        if nums[i] < suffixMin[i + 1]:
            suffixMin[i] = nums[i]
            suffixMinIdx[i] = i
        else:
            suffixMin[i] = suffixMin[i + 1]
            suffixMinIdx[i] = suffixMinIdx[i + 1]
        # For maximum
        if nums[i] > suffixMax[i + 1]:
            suffixMax[i] = nums[i]
            suffixMaxIdx[i] = i
        else:
            suffixMax[i] = suffixMax[i + 1]
            suffixMaxIdx[i] = suffixMaxIdx[i + 1]

    # Iterate over each index and check the candidate suffix range.
    for i in range(0, n - offset):
        jStart = i + offset
        # Check using the minimum value from the suffix range.
        if abs(nums[i] - suffixMin[jStart]) >= valueDifference:
            return [i, suffixMinIdx[jStart]]
        # Check using the maximum value from the suffix range.
        if abs(nums[i] - suffixMax[jStart]) >= valueDifference:
            return [i, suffixMaxIdx[jStart]]
    return [-1, -1]

# Example usage:
#print(findIndices([5,1,4,1], 2, 4))  # Expected output: [0,3] or similar valid answer.
← Back to All Questions