Katkat
Back

Count Pairs with the Minimum Absolute Difference

Shield AiSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to efficiently find the minimum absolute difference between elements in an array and count the number of pairs that achieve this difference using combinatorial counting.

Problem Statement

Given an array of integers nums, find the number of unordered pairs (i, j) such that i int.

Constraints

  • 2 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Examples

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

Example 2: Input: nums = [1, 1, 1, 2] Output: 3 Explanation: The minimum difference is 0. Pairs are (nums[0], nums[1]), (nums[0], nums[2]), and (nums[1], nums[2]) (indices 0, 1, 2 all have value 1).

Edge Cases

  • Arrays with many duplicate values (min difference = 0).
  • Arrays with already sorted or reverse-sorted elements.
  • Large range of values requiring O(n log n) complexity.

Hints

Hint 1

Sorting the array allows you to find the minimum difference by checking only adjacent elements.

Hint 2

If the minimum difference is greater than 0, iterate through the sorted array and count how many adjacent pairs result in that difference.

Hint 3

If the minimum difference is 0, the number of pairs for a specific value that appears 'k' times is given by the combination formula 'k * (k - 1) / 2'.

Follow-up questions

  • How would you modify your solution if you were asked to return the actual pairs rather than just the count?
  • Can you solve this problem in O(n) time if the range of the numbers in the input array is small (e.g., within a fixed range of 10^5)?
  • What would be the impact on space complexity if we used a hash map to store frequencies of each number versus sorting the array?