Minimum Absolute Difference

To solve this problem, we can start by sorting the array. This allows us to iterate through the array just once, comparing adjacent elements to find the minimum difference. We will store this minimum difference and create an output list of pairs with that difference.

Python solution:

1
2
3
4
5

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        min_diff = min(b - a for a, b in zip(arr, arr[1:]))
        return [[a, b] for a, b in zip(arr, arr[1:]) if b - a == min_diff]

We first sort the array. Then we use a generator expression with the zip function to iterate over pairs of adjacent elements in the sorted array, and find the minimum difference between such pairs.

Finally, we use a list comprehension to create a list of all pairs that have this minimum difference. The zip function is used again to iterate over pairs of adjacent elements.

When is the best case to use counting sort? In fact, the range of numbers are much greater than the total amount of numbers. So, K would be dominate in O(N + K), which is the time complexity for counting sort. Is it right to use counting sort here? Any advices would be really helpful!

Counting sort is an efficient algorithm for sorting an array of elements that are known to fall within a certain range. This range of possible item values is what’s referred to when we talk about ‘k’ in the time complexity of counting sort, O(n+k).

However, counting sort is not a comparison-based sort and has linear time complexity which makes it faster compared to comparison-based sorts like quicksort or mergesort for certain cases.

The best case to use counting sort is when:

  1. The range of input elements (k) is not significantly greater than the number of elements to be sorted (n). Counting sort can become inefficient if k is much larger than n because it initializes a list of size k+1.

  2. The values to be sorted are integers or can be mapped to integers. Counting sort operates by counting the occurrence of each unique element in the input, and then cumulatively summing these counts to determine the correct position of each element in the output. This process only works directly with integer values.

  3. The input elements are non-negative. Since counting sort uses the input values as indexes into an array, it cannot handle negative values without modification.

Since the range of numbers is much greater than the total amount of numbers, it might not be the best choice to use counting sort because the space complexity will be high and you would be initializing a large array where a lot of values might be unused.

If your data contains floating point numbers, or a mix of negative and positive numbers, or non-integer values, then a comparison sort like quicksort or mergesort might be a better option. If the range of input (k) is much larger than the number of elements (n), a comparison-based sort might be more efficient.