Minimum Absolute Difference Between Elements With Constraint — LeetCode 2817 Python Solution

MediumArrayBinary SearchOrdered Set

Problem: #2817
Pattern: Monotonic Stack
Reading time: 2 min
Source: leetcode.com

The problem

You are given a 0-indexed integer array nums and an integer x. Find the minimum absolute difference between two elements in the array that are at least x indices apart.

Example

Input: nums = [4,3,2,4], x = 2
Output: 0
Explanation: We can select nums[0] = 4 and nums[3] = 4.

Python solution

Python

class Solution:
    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        sl = SortedList()
        ans = inf
        for i in range(x, len(nums)):
            sl.add(nums[i - x])
            j = bisect_left(sl, nums[i])
            if j < len(sl):
                ans = min(ans, sl[j] - nums[i])
            if j:
                ans = min(ans, nums[i] - sl[j - 1])
        return ans

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 2817. Minimum Absolute Difference Between Elements With Constraint is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2817. Minimum Absolute Difference Between Elements With Constraint?: LeetCode 2817. Minimum Absolute Difference Between Elements With Constraint is rated Medium on LeetCode.
What is the time complexity of LeetCode 2817. Minimum Absolute Difference Between Elements With Constraint?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 2817. Minimum Absolute Difference Between Elements With Constraint?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2817. Minimum Absolute Difference Between Elements With Constraint cover?: LeetCode 2817. Minimum Absolute Difference Between Elements With Constraint is tagged Array, Binary Search and Ordered Set on LeetCode.