Minimum Absolute Difference Queries - Leetcode Solution

Problem statement:

Given an array of integers a and multiple queries consisting of indices l and r, find the minimum absolute difference between any two elements in the subarray a[l...r].

Example: Input: a = [1,3,4,8,10] queries = [(0,2),(1,4),(2,2)] Output: [1,1,0]

Explanation:

• For the first query (0,2), the subarray is [1,3,4] and the minimum absolute difference is 1 (between 1 and 3).
• For the second query (1,4), the subarray is [3,4,8,10] and the minimum absolute difference is also 1 (between 3 and 4).
• For the third query (2,2), the subarray is [4] and there is only one element, so the minimum absolute difference is 0.

Solution:

We need to process multiple queries on the given array. To solve this problem efficiently, we can precompute the minimum absolute difference between any two adjacent elements and store it in a separate array. Let's call this array diff.

We can calculate the diff array by iterating over the input array a and calculating the absolute difference between a[i] and a[i+1], for i from 0 to n-2 (where n is the length of a). We can save each value of diff[i] in the ith index of the diff array.

For example, for the input array [1,3,4,8,10], the diff array would be [2,1,4,2].

Once we have the diff array, we can answer each query by finding the minimum value of diff within the specified subarray. We can do this efficiently using Min Segment Tree data structure.

We can implement a Min Segment Tree by creating a binary tree where each node represents a range of indices in the input array. The root node represents the entire array, and each leaf node represents a single element. Each internal node represents the minimum value of its child nodes. We can build this tree recursively.

To answer a query (l,r), we can traverse the tree and find the minimum value of the diff array within the range [l,r] represented by the current node. This can be done using the following algorithm:

1. If the range represented by the current node is completely contained within the query range [l,r], return the minimum value of the diff array within this range.
2. If the range represented by the current node is disjoint from the query range [l,r], return infinity (or some large number that is greater than any value in the diff array).
3. Otherwise, recursively compute the minimum value of the diff array within the left child node (which represents the left half of the current range) and the right child node (which represents the right half of the current range). Return the minimum of these two values.

We can do a pre-order traversal of the tree to process each query efficiently. The total time complexity of this approach is O(nlog(n) + qlog(n)), where n is the length of the input array and q is the number of queries.

Code:

Here's the Python code for the solution:

class SegTree: # Initialize the segment tree with diff array and build the tree recursively def init(self, a): self.tree = [0] * (4*len(a)) self.build(a, 0, 0, len(a)-1)

def build(self, a, node, start, end):
    if start == end:
        self.tree[node] = a[start]
    else:
        mid = (start + end) // 2
        self.build(a, 2*node+1, start, mid)
        self.build(a, 2*node+2, mid+1, end)
        self.tree[node] = min(self.tree[2*node+1], self.tree[2*node+2])

# Query the minimum diff for the range [l,r]
def query(self, node, start, end, l, r):
    if l <= start and end <= r:
        return self.tree[node]
    if end < l or r < start:
        return float('inf')
    mid = (start + end) // 2
    left = self.query(2*node+1, start, mid, l, r)
    right = self.query(2*node+2, mid+1, end, l, r)
    return min(left, right)
        

class Solution: def minDifference(self, a: List[int], queries: List[Tuple[int, int]]) -> List[int]: # Calculate the diff array n = len(a) diff = [] for i in range(n-1): diff.append(abs(a[i+1]-a[i]))

    # Build the segment tree
    tree = SegTree(diff)
    
    # Process the queries
    ans = []
    for l, r in queries:
        d = tree.query(0, 0, n-2, l, r-1)
        ans.append(d if d != float('inf') else 0)
    
    return ans

The code consists of two classes. The SegTree class represents the Min Segment Tree, and the Solution class represents the entire solution to the problem. The main steps of the algorithm are implemented in the Solution class.

1