Is Minimum Absolute Difference easy or hard?

Minimum Absolute Difference is classified as an Easy problem on LeetCode. The main insight is recognizing that sorting allows you to check only adjacent elements instead of all pairs. Once that idea is clear, the implementation is straightforward.

Minimum Absolute Difference Python/Java solution

In Python or Java, sort the array using the built-in sort function and iterate once to track the smallest difference. Whenever a smaller difference is found, reset the result list; if the difference matches the current minimum, append the pair. This implementation runs in O(n log n) time.

How to solve Minimum Absolute Difference in O(n)?

An O(n) solution is generally not possible for arbitrary unsorted input because identifying closest values requires ordering information. Sorting provides that ordering and costs O(n log n). After sorting, the remaining scan step runs in linear time.

What is the best approach for Minimum Absolute Difference?

The optimal approach sorts the array first and then scans adjacent elements to compute differences. Because the closest numbers must appear next to each other in sorted order, only neighboring pairs need to be checked. This runs in O(n log n) time due to sorting and O(1) extra space.

Is Minimum Absolute Difference asked at Google/Amazon/Meta?

Problems based on finding minimum differences and leveraging sorting patterns appear frequently in interviews at large tech companies. Variations of this problem are common in Amazon and Google interview preparation sets because they test understanding of sorting and pair comparisons.

What data structure is used in Minimum Absolute Difference?

The primary structure is a simple array. The algorithm relies on sorting the array and then iterating sequentially to compare adjacent elements. No additional complex data structures are required.

What is the time complexity of Minimum Absolute Difference?

The optimal solution runs in O(n log n) time because the array must be sorted before scanning. After sorting, a single pass through the array calculates differences between adjacent elements in O(n). The brute force method takes O(n²) time since it compares every pair.

Description Hints 2 Solution Video 5:21

1200. Minimum Absolute Difference

Easy75.1% acceptance16 companies

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

a, b are from arr
a < b
b - a equals to the minimum absolute difference of any two elements in arr

Example 1:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Example 2:

Input: arr = [1,3,6,10,15]
Output: [[1,3]]

Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]

Constraints:

2 <= arr.length <= 10⁵
-10⁶ <= arr[i] <= 10⁶

Asked at 16 companies

Walmart Labs PayPal Agoda Audible Paycom

IBM NVIDIA Oracle Salesforce JPMorgan Chase Cognizant Microsoft

+4 more

Bloomberg

Google Amazon Meta

Topics

Array Sorting

Hints open one at a time

Hint 1

Find the minimum absolute difference between two elements in the array.

Hint 2

The minimum absolute difference must be a difference between two consecutive elements in the sorted array.

5:21

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution