Minimum Absolute Difference

📋

Problem

Imagine you have a list of prices for similar products and want to find two products priced closest to each other to decide on a fair deal.

Given an array of distinct integers arr, find and return the minimum absolute difference between any two elements in the array.

2 ≤ n ≤ 10^5-10^6 ≤ arr[i] ≤ 10^6All elements in arr are distinct

Edge cases: Array with only two elements → output is absolute difference of those twoArray with negative and positive numbers → ensure absolute difference calculation is correctArray sorted in descending order → sorting step must handle this

</>

IDE

def minimum_abs_difference(arr: list[int]) -> int:public int minimumAbsDifference(int[] arr)int minimumAbsDifference(vector<int> &arr)function minimumAbsDifference(arr)

def minimum_abs_difference(arr):
    # Write your solution here
    pass

class Solution {
    public int minimumAbsDifference(int[] arr) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int minimumAbsDifference(vector<int> &arr) {
    // Write your solution here
    return 0;
}

function minimumAbsDifference(arr) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Incorrectly returning zero for distinct elements due to not handling distinctness or misreading input.✅ Ensure input is distinct as per problem statement; if duplicates appear, handle accordingly or validate input.

Wrong: 999999Using greedy approach without sorting, picking first pair difference only.✅ Sort the array first and scan all adjacent pairs to find minimum difference.

Wrong: 2Off-by-one error skipping last adjacent pair in scanning loop.✅ Loop through indices from 0 to n-2 to compare all adjacent pairs.

Wrong: TLEUsing nested loops (O(n^2)) brute force approach on large input.✅ Implement sorting + single pass adjacent difference scan for O(n log n) time.

✓

Test Cases

Try testing your solution on edge cases like smallest arrays and negative values.

Consider tricky inputs that might break greedy or off-by-one logic.

Prepare for large inputs; brute force will time out, optimize with sorting.

t1_01basic

Input{"arr":[4,2,1,3]}

Expected1

⏱ Performance - must finish in 2000ms

After sorting, the array becomes [1,2,3,4]. The minimum absolute difference is 1 between adjacent elements.

💡 Sort the array first to bring close elements together.

💡 Check differences only between adjacent elements after sorting.

💡 Return the smallest difference found between any two adjacent elements.

Why it failed: Incorrect output likely due to missing sorting step or checking all pairs instead of adjacent pairs. Fix by sorting arr and scanning adjacent differences only.

✓ Correct minimum absolute difference found using sorting and adjacent scan.

t1_02basic

Input{"arr":[10,20,15,12]}

Expected2

⏱ Performance - must finish in 2000ms

Sorted array is [10,12,15,20]. Minimum difference is 2 between 10 and 12.

💡 Sorting arr places elements in ascending order.

💡 Minimum difference is among adjacent pairs after sorting.

💡 Check differences: 12-10=2, 15-12=3, 20-15=5; minimum is 2.

Why it failed: Wrong output caused by not sorting or comparing non-adjacent pairs unnecessarily. Fix by sorting and scanning adjacent pairs only.

✓ Correctly computed minimum absolute difference after sorting.

t2_01edge

Input{"arr":[1000000,-1000000]}

Expected2000000

⏱ Performance - must finish in 2000ms

Only two elements, difference is abs(1000000 - (-1000000)) = 2000000.

💡 With only two elements, the answer is their absolute difference.

💡 Check absolute difference calculation handles negative values correctly.

💡 Return abs(arr[0] - arr[1]) directly for two-element arrays.

Why it failed: Incorrect result due to wrong absolute difference calculation or sign errors. Fix by using abs() function correctly.

✓ Correctly handled two-element array with large values and negative number.

t2_02edge

Input{"arr":[5,4]}

Expected1

⏱ Performance - must finish in 2000ms

Array sorted is [4,5]. Minimum difference is 1 between 4 and 5.

💡 Sorting must handle descending order input correctly.

💡 Minimum difference is between adjacent elements after sorting.

💡 Sort arr before scanning differences.

Why it failed: Wrong output caused by assuming input is sorted or not sorting descending input. Fix by sorting input array first.

✓ Correctly handled descending order input by sorting first.

t2_03edge

Input{"arr":[1,1000000,500000,-500000]}

Expected499999

⏱ Performance - must finish in 2000ms

Sorted array is [-500000,1,500000,1000000]. Differences: 500001, 499999, 500000; minimum is 499999 between 1 and 500000.

💡 Sort array with mixed negative and positive values.

💡 Check all adjacent differences carefully.

💡 Minimum difference is min of abs differences between adjacent sorted elements.

Why it failed: Incorrect minimum difference due to off-by-one or sign errors in difference calculation. Fix by careful absolute difference between adjacent sorted elements.

✓ Correctly computed minimum difference with mixed sign values.

t3_01corner

Input{"arr":[1,10,3,20,2]}

Expected1

⏱ Performance - must finish in 2000ms

Sorted: [1,2,3,10,20]. Minimum difference is 1 between 1 and 2 or 2 and 3.

💡 Beware of greedy approach picking only first pairs without sorting.

💡 Sorting ensures closest elements are adjacent.

💡 Sort arr and scan adjacent pairs for minimum difference.

Why it failed: Failing due to greedy approach without sorting, missing smaller differences. Fix by sorting before scanning.

✓ Correctly avoided greedy trap by sorting first.

t3_02corner

Input{"arr":[100,50,25,12,6,3]}

Expected3

⏱ Performance - must finish in 2000ms

Sorted: [3,6,12,25,50,100]. Differences: 3,6,13,25,50; minimum is 3.

💡 Check for off-by-one errors in adjacent difference scanning.

💡 Ensure loop runs from 0 to n-2 to compare pairs.

💡 Return minimum of all adjacent differences after sorting.

Why it failed: Off-by-one error causing missed last pair difference. Fix by iterating to n-2 index for adjacent pairs.

✓ Correctly handled all adjacent pairs without off-by-one errors.

t3_03corner

Input{"arr":[1,3,3,7]}

Expected0

⏱ Performance - must finish in 2000ms

Sorted: [1,3,3,7]. Minimum difference is 0 between duplicate 3s.

💡 Check if input can have duplicates; problem states distinct elements, so this tests robustness.

💡 If duplicates present, minimum difference can be zero.

💡 Handle duplicates by sorting and scanning adjacent pairs.

Why it failed: Incorrect output due to assumption of distinct elements; duplicates cause zero difference. Fix by handling duplicates or validating input.

✓ Correctly handled duplicates if present, returning zero difference.

t4_01performance

Input{"arr":[1000000,999999,999998,999997,999996,999995,999994,999993,999992,999991,999990,999989,999988,999987,999986,999985,999984,999983,999982,999981,999980,999979,999978,999977,999976,999975,999974,999973,999972,999971,999970,999969,999968,999967,999966,999965,999964,999963,999962,999961,999960,999959,999958,999957,999956,999955,999954,999953,999952,999951,999950,999949,999948,999947,999946,999945,999944,999943,999942,999941,999940,999939,999938,999937,999936,999935,999934,999933,999932,999931,999930,999929,999928,999927,999926,999925,999924,999923,999922,999921,999920,999919,999918,999917,999916,999915,999914,999913,999912,999911,999910,999909,999908,999907,999906,999905,999904,999903,999902,999901]}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100, sorted descending. Algorithm must run in O(n log n) time within 2 seconds.

💡 Sorting large input efficiently is key to performance.

💡 Avoid nested loops; use sorting + single pass.

💡 O(n log n) sorting plus O(n) scan is optimal.

Why it failed: TLE due to O(n^2) brute force approach. Fix by implementing sorting + adjacent scan approach.

✓ Algorithm runs within time limit using O(n log n) sorting and O(n) scanning.

Practice

1. Given the following code for computing the h-index, what is the returned value when the input is [4, 1, 0, 5, 6]?

easy

A. 3

B. 4

C. 5

D. 2

Solution

1. Step 1: Sort citations descending

   Sorted list: [6,5,4,1,0]

2. Step 2: Binary search on h from 0 to 5

   Check mid=2: count papers >=2 is 3 (6,5,4) ≥2 -> low=3; mid=4: count ≥4 is 3 -> low=5; mid=5: count ≥5 is 2 -> high=4; loop ends with high=4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Final h-index is 4 for this input [OK]

Hint: Count papers ≥ mid after sorting [OK]

Common Mistakes:

• Off-by-one in binary search boundaries
• Not breaking early in count loop
• Returning low instead of high

2. You are given an array of integers and need to rearrange it so that no two adjacent elements are the same. Which approach guarantees an optimal solution for this problem?

easy

A. Count frequencies, then use a max heap to greedily place the most frequent elements first, ensuring spacing.

B. Use backtracking to generate all permutations and check for valid arrangements.

C. Sort the array and then swap adjacent elements to avoid duplicates.

D. Use dynamic programming to track valid sequences avoiding adjacent duplicates.

Solution

1. Step 1: Understand problem constraints

   The problem requires rearranging elements so no two adjacent are equal, which demands careful placement of frequent elements.

2. Step 2: Identify approach that handles frequency and spacing

   Using a max heap to always pick the most frequent element available and placing it ensures no two identical elements are adjacent, which brute force or simple sorting cannot guarantee efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max heap approach handles frequency and spacing correctly [OK]

Hint: Max heap ensures spacing of frequent elements [OK]

Common Mistakes:

• Thinking sorting alone avoids adjacent duplicates
• Assuming DP solves this without frequency tracking

3. You are given an unsorted array of integers and need to reorder it so that nums[0] < nums[1] > nums[2] < nums[3] > nums[4] and so on, ensuring a "wiggle" pattern. Which approach guarantees an optimal solution that runs in O(n log n) time and uses O(1) extra space?

easy

A. Use a greedy approach by swapping adjacent elements whenever the wiggle property is violated.

B. Sort the array, find the median, then rearrange elements in-place using virtual indexing and three-way partitioning.

C. Use dynamic programming to find the longest wiggle subsequence and reconstruct the array accordingly.

D. Sort the array and then alternate picking elements from the start and end into a new array.

Solution

1. Step 1: Understand the wiggle property requirements

   The problem requires elements to be reordered so that nums[0] < nums[1] > nums[2] < nums[3] > nums[4]..., which is not guaranteed by simple sorting or greedy swaps.

2. Step 2: Identify the approach that ensures correct interleaving

   Sorting and then using the median with virtual indexing and three-way partitioning ensures elements greater than median are placed at odd indices and smaller at even indices, maintaining the wiggle property in O(n log n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Virtual indexing and median partitioning guarantee wiggle order [OK]

Hint: Virtual indexing with median partitioning ensures wiggle order [OK]

Common Mistakes:

• Assuming greedy swaps fix all cases
• Using DP for rearrangement instead of subsequence
• Ignoring in-place rearrangement for space efficiency

4. What is the time complexity of the optimal counting sort based solution for the relative sort array problem, where n = length of arr1 and k = maximum value in arr1?

medium

A. O(n + k) because frequency counting and outputting are linear in n and k

B. O(n log n) due to sorting leftover elements

C. O(n * k) because nested loops iterate over arr1 and frequency array

D. O(k log k) due to sorting the frequency array keys

Solution

1. Step 1: Analyze frequency counting

   Counting frequencies over arr1 is O(n), where n is arr1 length.

2. Step 2: Analyze output construction

   Outputting elements by iterating frequency array of size k is O(k). No sorting is done on leftover elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counting sort runs in linear time relative to n and k [OK]

Hint: Counting sort is linear in input size and max value [OK]

Common Mistakes:

• Assuming leftover elements require sorting (O(n log n))
• Confusing nested loops causing O(n*k)
• Thinking frequency array keys need sorting

5. Suppose the problem is modified so that time points can repeat multiple times and you want to find the minimum difference between any two occurrences, but the input size is very large (up to 10^7). Which approach is best suited to handle this efficiently?

hard

A. Use the brute force nested loops approach to check all pairs for minimum difference.

B. Use the bucket sort approach with a boolean array to detect duplicates and find minimum difference in O(n) time.

C. Use a hash map to count occurrences and then sort unique times to find minimum difference.

D. Use a balanced binary search tree to insert times and find minimum difference on the fly.

Solution

1. Step 1: Consider input size and duplicates

   With up to 10^7 times and possible duplicates, brute force is infeasible.

2. Step 2: Bucket sort with boolean array is optimal

   Using a fixed-size 1440-length boolean array detects duplicates instantly and scans once for minimum difference in O(n) time.

3. Step 3: Other approaches are less efficient

   Sorting or balanced trees add overhead and cannot beat fixed-size bucket scanning for this problem.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Bucket sort approach handles large inputs and duplicates efficiently [OK]

Hint: Fixed 1440 bucket array handles duplicates and large inputs efficiently [OK]

Common Mistakes:

• Trying brute force on large inputs
• Sorting large inputs with duplicates is costly
• Using trees adds unnecessary overhead