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

Minimum Absolute Difference Between Elements With Constraint

Number: 3000

Difficulty: Medium

Paid? No

Companies: Uber, Databricks, Roblox, Microsoft, Google

Problem Description

Given a 0-indexed integer array nums and an integer x, find the minimum absolute difference between two elements in nums whose indices are at least x apart. In other words, choose two indices i and j such that |i - j| >= x and minimize |nums[i] - nums[j]|. Return that minimum absolute difference.

Key Insights

  • When x > 0, only pairs where the two indices are sufficiently separated are allowed.
  • A balanced search structure (ordered set / balanced BST) can be used to maintain valid candidates from earlier indices.
  • As we iterate through the array, we add elements that become eligible (i.e. whose index is at least x positions before the current index) into the data structure.
  • For the current element, we perform a binary search in the structure to find the candidate(s) closest in value.
  • Handle the special case when x == 0: the condition becomes nonrestrictive (aside from requiring distinct indices) so you can use all previous elements.

Space and Time Complexity

Time Complexity: O(n log n) – each iteration performs a binary search and insertion into the sorted container. Space Complexity: O(n) – in the worst-case, we store almost n elements in the data structure.

Solution

We use a sliding window technique with a balanced search tree (or any sorted data structure that supports binary search) to maintain all numbers from indices that are at least x positions behind the current index. For each new element at index i:

  1. If i >= x, we add nums[i - x] to the sorted container. (For x==0, we start by processing from index 1 so that we never compare an element with itself.)
  2. We search in the container for the number(s) closest to nums[i] – both the smallest number not less than nums[i] and the largest number less than nums[i].
  3. The absolute difference with these closest values is a candidate answer; update the result accordingly.
  4. Continue until the entire array is processed.

This approach guarantees that we only consider pairs of elements whose indices satisfy the constraint and finds the global minimum difference with an overall time complexity of O(n log n).

Code Solutions

import bisect

def minAbsoluteDifference(nums, x):
    # Initialize an empty list to act as a sorted container.
    sorted_container = []
    n = len(nums)
    # If x is 0, start comparison from index 1 (each element gets compared with all earlier ones)
    ans = float('inf')
    if x == 0:
        # add first element
        sorted_container.append(nums[0])
        for i in range(1, n):
            # Find the insertion position for the current element.
            pos = bisect.bisect_left(sorted_container, nums[i])
            # Check the candidate on the right.
            if pos < len(sorted_container):
                ans = min(ans, abs(nums[i] - sorted_container[pos]))
            # Check the candidate on the left.
            if pos > 0:
                ans = min(ans, abs(nums[i] - sorted_container[pos - 1]))
            # Insert the current element into the sorted container
            bisect.insort(sorted_container, nums[i])
    else:
        # For x > 0, we use indices that are at least x apart.
        # The container will hold elements from index range [0, i - x], as i increases.
        for i in range(n):
            # Once we pass index x-1, we add the element that becomes eligible.
            if i >= x:
                bisect.insort(sorted_container, nums[i - x])
            if sorted_container:
                pos = bisect.bisect_left(sorted_container, nums[i])
                if pos < len(sorted_container):
                    ans = min(ans, abs(nums[i] - sorted_container[pos]))
                if pos > 0:
                    ans = min(ans, abs(nums[i] - sorted_container[pos - 1]))
    return ans

# Example usage:
print(minAbsoluteDifference([4,3,2,4], 2))  # Output: 0
print(minAbsoluteDifference([5,3,2,10,15], 1))  # Output: 1
print(minAbsoluteDifference([1,2,3,4], 3))  # Output: 3
← Back to All Questions