Problem statement

https://leetcode.com/problems/minimum-absolute-difference-queries/

Solution 1

To solve this problem efficiently, we need to read problem constraints carefully and what we can notice, that all numbers are not so big, that is in range 1, N, where N <= 100. Let us consider cumulative sums, or you can call it cumulative counters of our numbers. Let us consider example nums = [4, 5, 2, 2, 7, 10], then we have:

dp[0] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

dp[1] = [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]

dp[2] = [0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0]

dp[3] = [0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0]

dp[4] = [0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 0]

dp[5] = [0, 0, 2, 0, 1, 1, 0, 1, 0, 0, 0]

dp[6] = [0, 0, 2, 0, 1, 1, 0, 1, 0, 0, 1]

On the first step we have no elements, so frequencies of every element is equal to zero. Then we added 4, and we increase 4-th place by one and so on. Why we need these dp table? Of course for fast evaluation of queries. How we can evaluate query now? For example to evaluate query for interval [1, 5] what we need to do is look at dp[6] and dp[1] and choose only indexes of those elements which have different frequencies. For given example we have

dp[6] = [0, 0, 2, 0, 1, 1, 0, 1, 0, 0, 1]

dp[1] = [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]

So, we look at indexes 2, 5, 7, 10 and then choose minimum among gaps, which is equal to 2.

Complexity

Time complexity of evaluation of cumulative sums is O(N*n), where N is the biggest number among nums and n is length of nums. Then we have Q queries, each of which can be evaluated in O(N). So, total time complexity is O(N*(n+Q), which is no more than 10^7 given problem constraints. Also simple list operations work quite fast in python, but we can make it faster, if we use numpy (TBD). Space complexity is O(N*n).

Code

class Solution:
    def minDifference(self, nums, queries):
        N, ans, dp = max(nums), [], [[0]*(max(nums)+1)]
        
        for num in nums:
            t = dp[-1][:]
            t[num] += 1
            dp.append(t)

        for a, b in queries:
            diff = [i for x, y, i in zip(dp[b+1], dp[a], range(N+1)) if y != x]
            ans.append(min([b-a for a,b in zip(diff, diff[1:])] or [-1]))
        
        return ans

Solution 2

Here we use exaclty the same logic, but use numpy functionality. I was hoping that it will work much faster, but in fact it is not much faster due to implicit use of loops. Here I use couple of tricks: first one when we evaluate dp, I do it with cumulative function and with unity matrix trick. Then we use nonzero and diff functions.

Complexity

It is the same we have as in the first solution 1. Potentially it can work faster due to optimized numpy library, but the problem here that np.nonzero() will give different length answer for each row and I do not know how to avoid implicit loops here and go fully numpy. If you know, plese let me know in comments.

import numpy as np

class Solution:
    def minDifference(self, nums, Q):
        dp = np.cumsum(np.eye(max(nums)+1)[[0] + nums], axis = 0)
        return [min(np.diff((dp[x] - dp[y+1]).nonzero()[0]), default=-1) for x, y in Q]