How do you solve Minimum Absolute Difference on LeetCode?

Minimum Absolute Difference (LeetCode #1200) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Sorting the array allows us to find the minimum difference between consecutive elements.

What is the time complexity of Minimum Absolute Difference?

The optimal solution for Minimum Absolute Difference runs in O(n log n) time and uses O(n) space. The time complexity is O(n log n) due to the sorting step. The space complexity is O(n) because we store the pairs in a list.

What is the brute force solution for Minimum Absolute Difference?

The brute force approach for Minimum Absolute Difference is Brute Force, with O(n²) time complexity and O(1) space complexity. We can find the minimum absolute difference by checking every possible pair of elements in the array. This approach is straightforward but inefficient for large arrays. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Minimum Absolute Difference?

Minimum Absolute Difference uses the following concepts: Array, Sorting. The recommended patterns to study are: Sorting, Array.

What are the interview tips for Minimum Absolute Difference?

Always consider sorting as a first step when dealing with differences. Be clear about how you handle pairs and their order. Practice explaining your thought process as you code.

What are common mistakes when solving Minimum Absolute Difference?

Not sorting the array before finding pairs. Overlooking the requirement to return pairs in ascending order.

#1200

Minimum Absolute Difference

Easy

ArraySortingSortingArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

By sorting the array first, we can ensure that the minimum absolute difference will always be between consecutive elements. This allows us to reduce the number of comparisons significantly.

⚙️

Algorithm

5 steps

1Step 1: Sort the array.
2Step 2: Initialize a variable to store the minimum difference as infinity.
3Step 3: Iterate through the sorted array and calculate the absolute difference between each consecutive pair.
4Step 4: Update the minimum difference and store pairs that match this minimum difference.
5Step 5: Return the list of pairs.

solution.py17 lines

1# Full working Python code
2
3def minimumAbsDifference(arr):
4    arr.sort()
5    min_diff = float('inf')
6    pairs = []
7    for i in range(len(arr) - 1):
8        diff = arr[i + 1] - arr[i]
9        if diff < min_diff:
10            min_diff = diff
11            pairs = [[arr[i], arr[i + 1]]]
12        elif diff == min_diff:
13            pairs.append([arr[i], arr[i + 1]])
14    return pairs
15
16# Example usage
17print(minimumAbsDifference([4,2,1,3]))

ℹ

Complexity note: The time complexity is O(n log n) due to the sorting step. The space complexity is O(n) because we store the pairs in a list.

1Sorting the array allows us to find the minimum difference between consecutive elements.
2Pairs must be stored in ascending order, which is naturally handled by the sorting step.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.