LeetCode 2817.Minimum Absolute Difference...

Intuition

start from x and add element to sorted list into a sorted order using binary search.

Insert the old number that is in valid range and check for insertion position using the current element.

When the position for insertion is found, it is safe to assume that the element that is immediate left and immediate right are closest neighbors that are valid and closest to the current element looked at in a loop.

Update the minimum value accordingly after checking the left and right

use SortedList() in python to automatically maintain order of elements in sorted order

S = SortedList()
S.add()

Optimal Solution

class Solution:
	def minAbsoluteDifference(self, nums: List[int], x:int)-> int:
		res = float('inf')
		S = SortedList()
		
		for i in range(x,len(nums)):
			S.add(nums[i-x])
			j = S.bisect_left(nums[i])
			
			if j < len(s):
				res = min(res, abs(S[j]-nums[i]))
			if j > 0: 
				res = min(res, abs(S[j-1]-nums[i]))
				
		return res

Time Complexity

O(N(Log(N))) -> N loop x (LogN + LogN) Time Complexity

O(N) Space Complexity