Katkat
Back

Find the Minimum Absolute Difference

UpstartSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to efficiently find the minimum absolute difference between any two elements in an array, requiring an understanding of sorting and linear scans.

Problem Statement

Given an array of integers nums, find the minimum absolute difference between any two distinct elements at different indices. Your solution must not modify the original input array and should handle duplicates, negative numbers, and large integer values.

Return a list of all pairs [a, b] that achieve this minimum difference. The pairs should be returned as sorted sub-lists, and the overall list of pairs should be sorted by the first element of each pair.

Function Signature

def find_min_diff_pairs(nums: List[int]) -> List[List[int]]:

Constraints

  • 2 <= len(nums) <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • The time complexity should be O(n log n).

Examples

Example 1: Input: nums = [4, 2, 1, 3] Output: [[1, 2], [2, 3], [3, 4]] Explanation: The minimum absolute difference is 1. The pairs are (1,2), (2,3), and (3,4).

Example 2: Input: nums = [1, 5, 3, 19, 18, 25] Output: [[18, 19]] Explanation: The minimum absolute difference is 1. The pair is (18, 19).

Edge Cases

  • Arrays containing duplicates (e.g., [1, 1, 5]) should return a minimum difference of 0 (e.g., [[1, 1]]).
  • Arrays with only two elements.
  • Arrays with all identical elements.

Hints

Hint 1

Consider how sorting the array affects the distance between adjacent elements.

Hint 2

Once sorted, the minimum absolute difference must exist between at least one pair of adjacent elements.

Hint 3

Perform a single pass through the sorted array to find the global minimum difference, then a second pass to collect all pairs matching that value.

Follow-up questions

  • How would you optimize the solution if you knew the range of the input numbers was very small (e.g., all numbers are between 0 and 1,000)?
  • If the array is updated dynamically (i.e., new numbers are added), how could you maintain the minimum absolute difference without re-sorting the entire array?
  • How would you modify your algorithm to find the *maximum* absolute difference between any two elements?