Minimum Absolute Difference Queries Interview Question for Google

The minimum absolute difference of an array a is defined as the minimum value of |a[i] - a[j]|, where 0 <= i < j < a.length and a[i] != a[j]. If all elements of a are the same, the minimum absolute difference is -1.

For example, the minimum absolute difference of the array [5,2,3,7,2] is |2 - 3| = 1. Note that it is not 0 because a[i] and a[j] must be different.

You are given an integer array nums and the array queries where queries[i] = [l_i, r_i]. For each query i, compute the minimum absolute difference of the subarray nums[l_i...r_i] containing the elements of nums between the 0-based indices l_i and r_i (inclusive).

Return an array ans where ans[i] is the answer to the i^th query.

A subarray is a contiguous sequence of elements in an array.

The value of |x| is defined as:

x if x >= 0.
-x if x < 0.

Example 1:

Input: nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
Output: [2,1,4,1]
Explanation: The queries are processed as follows:
- queries[0] = [0,1]: The subarray is [1,3] and the minimum absolute difference is |1-3| = 2.
- queries[1] = [1,2]: The subarray is [3,4] and the minimum absolute difference is |3-4| = 1.
- queries[2] = [2,3]: The subarray is [4,8] and the minimum absolute difference is |4-8| = 4.
- queries[3] = [0,3]: The subarray is [1,3,4,8] and the minimum absolute difference is |3-4| = 1.

Example 2:

Input: nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
Output: [-1,1,1,3]
Explanation: The queries are processed as follows:
- queries[0] = [2,3]: The subarray is [2,2] and the minimum absolute difference is -1 because all the
  elements are the same.
- queries[1] = [0,2]: The subarray is [4,5,2] and the minimum absolute difference is |4-5| = 1.
- queries[2] = [0,5]: The subarray is [4,5,2,2,7,10] and the minimum absolute difference is |4-5| = 1.
- queries[3] = [3,5]: The subarray is [2,7,10] and the minimum absolute difference is |7-10| = 3.

Constraints:

2 <= nums.length <= 10⁵
1 <= nums[i] <= 100
1 <= queries.length <= 2 * 10⁴
0 <= l_i < r_i < nums.length

def min_abs_difference(nums, queries):
    """
    Calculates the minimum absolute difference for subarrays of nums based on queries.

    Args:
        nums (list[int]): The input array of integers.
        queries (list[list[int]]): A list of queries, where each query is a list [l, r]
                                 representing the start and end indices (inclusive) of a subarray.

    Returns:
        list[int]: A list containing the minimum absolute difference for each query. Returns -1 if all elements in subarray are same.
    """
    results = []
    for l, r in queries:
        sub_array = nums[l:r+1]
        results.append(min_abs_diff_subarray(sub_array))
    return results


def min_abs_diff_subarray(sub_array):
    """
    Calculates the minimum absolute difference within a given subarray.

    Args:
        sub_array (list[int]): The subarray to process.

    Returns:
        int: The minimum absolute difference. Returns -1 if all elements are same.
    """
    unique_nums = sorted(list(set(sub_array)))
    if len(unique_nums) < 2:
        return -1

    min_diff = float('inf')
    for i in range(1, len(unique_nums)):
        min_diff = min(min_diff, unique_nums[i] - unique_nums[i-1])
    return min_diff

# Example Usage and Tests
nums1 = [1, 3, 4, 8]
queries1 = [[0, 1], [1, 2], [2, 3], [0, 3]]
print(f"Input: nums = {nums1}, queries = {queries1}\nOutput: {min_abs_difference(nums1, queries1)}")

nums2 = [4, 5, 2, 2, 7, 10]
queries2 = [[2, 3], [0, 2], [0, 5], [3, 5]]
print(f"\nInput: nums = {nums2}, queries = {queries2}\nOutput: {min_abs_difference(nums2, queries2)}")

Code Description:

The code defines two functions:

min_abs_difference(nums, queries): This function takes the input array nums and a list of queries as input. For each query [l, r], it extracts the subarray nums[l:r+1] and calls the min_abs_diff_subarray function to calculate the minimum absolute difference for that subarray. The results are collected and returned as a list.
min_abs_diff_subarray(sub_array): This function calculates the minimum absolute difference within a given sub_array. It first finds the unique numbers in the subarray using set() and sorts them. If the number of unique elements is less than 2, it means all elements are the same, so it returns -1. Otherwise, it iterates through the sorted unique numbers, calculating the difference between consecutive numbers and keeping track of the minimum difference found. This minimum difference is then returned.

Explanation:

The min_abs_difference function iterates through the queries, extracting the corresponding subarrays. For each subarray, min_abs_diff_subarray is called.

The min_abs_diff_subarray function first identifies unique elements in the subarray to avoid considering the difference between identical elements. Then, it sorts these unique elements to easily find the minimum difference between adjacent elements.

If all elements in the subarray are identical, the function returns -1 as specified in the problem description.

Brute Force Solution:

A brute-force approach would involve iterating through all possible pairs of elements in each subarray and calculating the absolute difference between them. The minimum of these differences would be the result. However, this approach has a time complexity of O(n^2) for each subarray, where n is the length of the subarray, making it less efficient than the provided solution.

Optimal Solution:

The provided solution is more optimal because it reduces the time complexity by using a set to find unique elements and sorting them. This allows for a linear scan to find the minimum difference between adjacent elements. Although the time complexity includes the sorting operation, it generally performs better than the brute-force approach, especially for larger subarrays.

Big(O) Run-time Analysis:

min_abs_difference(nums, queries):
- Iterates through each query in queries: O(q), where q is the number of queries.
- For each query, extracts a subarray: O(r - l + 1), where r and l are the query indices.
- Calls min_abs_diff_subarray on the subarray.
min_abs_diff_subarray(sub_array):
- set(sub_array): O(n), where n is the length of the subarray.
- sorted(list(set(sub_array))): O(k log k), where k is the number of unique elements in the subarray. In the problem constraints, the value of elements are between 1 and 100, therefore k <= 100.
- Iterating through the sorted unique elements: O(k), where k is the number of unique elements.

Overall:

The dominant factor is the sorting operation O(k log k) inside min_abs_diff_subarray. Because k <= 100, we can consider it to be O(1). Thus, the complexity for min_abs_diff_subarray is O(n) for converting the subarray to a set and O(1) for sorting the unique elements. The overall time complexity becomes O(q * n) where q is the number of queries, and n is the maximum length of subarray processed for each query. Because the upper bound of an element is 100, the efficient implementation reduces the complexity greatly.

Big(O) Space Usage Analysis:

min_abs_difference(nums, queries):
- results: O(q), where q is the number of queries.
- sub_array: O(n), where n is the length of the subarray (in the worst case, the entire nums array).
min_abs_diff_subarray(sub_array):
- unique_nums: O(k), where k is the number of unique elements in the subarray. Since the elements are between 1 and 100, k can be at most 100.

Overall:

The space complexity is dominated by the results list (which stores the result for each query) and the unique_nums list (which stores the unique values for each subarray). Therefore, the overall space complexity is O(q + k). Since k is bounded by 100, this can be considered O(q).

Edge Cases:

Empty input array: The code gracefully handles an empty input array by implicitly returning an empty result list if nums is empty.
Empty subarray (l == r): If l and r are equal, the subarray contains only one element. In this case, the min_abs_diff_subarray function will return -1, as there are no two different elements to compare.
Subarray with all same elements: If the subarray contains only the same elements, the min_abs_diff_subarray function correctly returns -1.
Large input array: The code is designed to handle large input arrays efficiently by using a set to find unique elements and avoiding redundant calculations.
Queries with invalid indices: The code assumes that the query indices l and r are valid and within the bounds of the input array nums. It might be beneficial to add a check for invalid indices to handle such cases gracefully (e.g., raising an exception or returning an error message).

Additional Considerations:

To further optimize the code, especially for a very large number of queries, consider precomputing the minimum absolute differences for all possible subarrays of nums. This can be done using dynamic programming. However, this would increase the space complexity. The trade-off between time and space complexity depends on the specific requirements of the application.