Find the Smallest Difference Between Any Two Values
Solve this ProblemEasy15 min
Topics
BasicsComplexityArraysSorting
Companies
TCSInfosysWipro
Given an array
nums with at least two values, return the smallest absolute difference between any two of them.
Sorting is the classic O(n log n)Linearithmic Time O(n log n)The cost of efficient sorting: a little more than linear, far less than quadratic. operation, and it often turns a hard question into an easy one. Checking every pair is O(n²); after sorting, only neighbours can be closest, so a single O(n) scan finishes the job. The sort's O(n log n) dominates the total.
Test Case 1:
Input:nums = [30, 5, 20, 9]
Output:4
Explanation:5 and 9 are the closest pair, 4 apart.
Test Case 2:
Input:nums = [8, 3, 8]
Output:0
Explanation:Two equal values have a difference of 0.
Constraints
- ◆
2 ≤ nums.length ≤ 1000 - ◆
-1000000 ≤ nums[i] ≤ 1000000
Try the Dry Run
Approach & Solutions
Compare Every PairBrute
Check every pair (i, j) with i < j, compute the absolute difference and keep the smallest. There are n(n − 1) / 2 pairs, so the work grows with the square of n.
Time
O(n²)Space
O(1)Java
class Solution {
public int minDifference(int[] nums) {
int best = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
int diff = Math.abs(nums[i] - nums[j]);
if (diff < best) {
best = diff;
}
}
}
return best;
}
}Sort, Then Check NeighboursOptimal
After sorting, the closest pair must be two neighbours: anything further apart in sorted order has a value in between, so it can only be further apart. Sort a copy (O(n log n)) and scan adjacent pairs once (O(n)). The sort dominates, giving O(n log n) overall.
Time
O(n log n)Space
O(n)Java
class Solution {
public int minDifference(int[] nums) {
int[] values = nums.clone();
Arrays.sort(values);
int best = Integer.MAX_VALUE;
for (int i = 1; i < values.length; i++) {
best = Math.min(best, values[i] - values[i - 1]);
}
return best;
}
}