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

Find Indices With Index and Value Difference I

Number: 3165

Difficulty: Easy

Paid? No

Companies: Paytm

Problem Description

Given an integer array nums, and two integers indexDifference and valueDifference, find two indices i and j (they can be the same) such that:

abs(i - j) >= indexDifference
abs(nums[i] - nums[j]) >= valueDifference Return the pair [i, j] if it exists or [-1, -1] otherwise.

Key Insights

The constraints allow a brute-force approach since n is small (n <= 100).
Iterate over all pairs (i, j) and check both conditions.
Since indices can be the same, the check for indexDifference being zero needs to be correctly handled.
Multiple valid pairs may exist; return any that satisfies the conditions.

Space and Time Complexity

Time Complexity: O(n^2) because we are iterating over all pairs in the array.
Space Complexity: O(1) as only constant extra space is used.

Solution

We can solve the problem using a two-loop brute-force approach. For every pair of indices (i, j), we check:

If the absolute difference in indices is greater than or equal to indexDifference.
If the absolute difference in values from the array at these indices is greater than or equal to valueDifference. If both conditions are satisfied, return the pair [i, j]. If the loops finish without finding such a pair, return [-1, -1].

Code Solutions

# Function to find indices with required differences
def find_indices(nums, indexDifference, valueDifference):
    n = len(nums)
    # Iterate through all possible pairs (i, j)
    for i in range(n):
        for j in range(n):
            # Check if the absolute difference of indices is sufficient
            if abs(i - j) >= indexDifference:
                # Check if the absolute difference of values is sufficient
                if abs(nums[i] - nums[j]) >= valueDifference:
                    return [i, j]
    # Return [-1, -1] if no valid pair is found
    return [-1, -1]

# Example usage:
result = find_indices([5, 1, 4, 1], 2, 4)
print(result)  # Expected output: [0, 3] or any valid pair

← Back to All Questions