Minimum Absolute Difference Between Elements with Constraint Solution in C++/Java/Python/JS
Problem Description:
You are given a 0-indexed integer array nums and an integer x.
Find the minimum absolute difference between two elements in the array that are at least x indices apart.
In other words, find two indices i and j such that abs(i - j) >= x and abs(nums[i] - nums[j]) is minimized.
Return an integer denoting the minimum absolute difference between two elements that are at least x indices apart.
Examples:
Input: nums = [4,3,2,4], x = 2
Output: 0
Explanation: We can select nums[0] = 4 and nums[3] = 4.
They are at least 2 indices apart, and their absolute difference is the minimum, 0.
It can be shown that 0 is the optimal answer.
Input: nums = [5,3,2,10,15], x = 1
Output: 1
Explanation: We can select nums[1] = 3 and nums[2] = 2.
They are at least 1 index apart, and their absolute difference is the minimum, 1.
It can be shown that 1 is the optimal answer.
Input: nums = [1,2,3,4], x = 3
Output: 3
Explanation: We can select nums[0] = 1 and nums[3] = 4.
They are at least 3 indices apart, and their absolute difference is the minimum, 3.
It can be shown that 3 is the optimal answer.
Constraints:
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
0 <= x < nums.length
Brute Force Approach
We are given a 0-indexed integer array nums and an integer x. Our task is to find two indices i and j such that:
- They are at least x indices apart → abs(i - j) ≥ x
- The absolute difference between their values is minimized → abs(nums[i] - nums[j]) is the smallest possible
A naïve brute-force solution would be to compare every pair of elements in the array where the indices satisfy abs(i - j) ≥ x. This helps build an understanding of the problem before we try to optimize.
To solve this problem using a straightforward approach:
- Iterate over each element nums[i] in the array.
- For each nums[i], check all elements nums[j] that are at least x indices apart.
- Compute the absolute difference abs(nums[i] - nums[j]).
- Keep track of the minimum absolute difference found.
- This approach guarantees that we check all possible valid pairs and find the optimal answer.
Let's understand with an example:
Minimum Absolute Difference Between Elements With Constraint Example:
Let’s consider an example to see how the brute force approach would work:
Example:
Input: nums = [5, 3, 2, 10, 15], x = 1
We need to find the minimum absolute difference between two numbers that are at least x = 1 indices apart.
- Start with nums[0] = 5:
- Compare with nums[1] = 3 → abs(5 - 3) = 2
- Compare with nums[2] = 2 → abs(5 - 2) = 3
- Compare with nums[3] = 10 → abs(5 - 10) = 5
- Compare with nums[4] = 15 → abs(5 - 15) = 10
- Minimum so far = 2
- Move to nums[1] = 3:
- Compare with nums[2] = 2 → abs(3 - 2) = 1 (new minimum)
- Compare with nums[3] = 10 → abs(3 - 10) = 7
- Compare with nums[4] = 15 → abs(3 - 15) = 12
- Minimum so far = 1
- Move to nums[2] = 2:
- Compare with nums[3] = 10 → abs(2 - 10) = 8
- Compare with nums[4] = 15 → abs(2 - 15) = 13
- Minimum remains = 1
- Move to nums[3] = 10:
- Compare with nums[4] = 15 → abs(10 - 15) = 5
- Final Minimum Absolute Difference = 1
Output: 1
Steps to Implement the Solution:
- Initialize Variables
Get the length of the array (n). - Iterate Over Each Element
Use a loop (i) to traverse the array. - Find Elements at Least x Indices Apart
Use another loop (j = i + x) to check elements that are at least x indices away. - Calculate Absolute Difference
Compute abs(nums[i] - nums[j]).
Update ans if the new difference is smaller. - Return the Minimum Found
After checking all valid pairs, return ans.
Initialize ans to a very large value (e.g., INT_MAX or float('inf')).
Minimum Absolute Difference Between Elements With Constraint leetcode solution
Minimum Absolute Difference Between Elements With Constraint solution / Code Implementation
1. Minimum Absolute Difference Between Elements With Constraint solution in C++ Try on Compiler
class Solution {
public:
int minAbsoluteDifference(vector<int>& nums, int x) {
// Get the size of the array
int n = nums.size();
// Initialize the answer with the maximum possible integer value
int ans = INT_MAX;
// Iterate through each element in the array
for (int i = 0; i < n; i++) {
// Iterate through elements that are at least 'x' indices apart
for (int j = i + x; j < n; j++) {
// Compute the absolute difference and update the minimum answer
ans = min(ans, abs(nums[i] - nums[j]));
}
}
// Return the minimum absolute difference found
return ans;
}
};
2. Minimum Absolute Difference Between Elements With Constraint solution in Java Try on Compiler
import java.util.List;
class Solution {
public int minAbsoluteDifference(List<Integer> nums, int x) {
// Get the size of the array
int n = nums.size();
// Initialize the answer with the maximum possible integer value
int ans = Integer.MAX_VALUE;
// Iterate through each element in the array
for (int i = 0; i < n; i++) {
// Iterate through elements that are at least 'x' indices apart
for (int j = i + x; j < n; j++) {
// Compute the absolute difference and update the minimum answer
ans = Math.min(ans, Math.abs(nums.get(i) - nums.get(j))); // Fix: Use nums.get(index)
}
}
// Return the minimum absolute difference found
return ans;
}
}
3. Minimum Absolute Difference Between Elements With Constraint solution in Python Try on Compiler
class Solution:
def minAbsoluteDifference(self, nums, x):
# Get the size of the array
n = len(nums)
# Initialize the answer with the maximum possible integer value
ans = float('inf')
# Iterate through each element in the array
for i in range(n):
# Iterate through elements that are at least 'x' indices apart
for j in range(i + x, n):
# Compute the absolute difference and update the minimum answer
ans = min(ans, abs(nums[i] - nums[j]))
# Return the minimum absolute difference found
return ans
4. Minimum Absolute Difference Between Elements With Constraint solution in Javascript Try on Compiler
/**
* @param {number[]} nums
* @param {number} x
* @return {number}
*/
var minAbsoluteDifference = function (nums, x) {
// Get the size of the array
let n = nums.length;
// Initialize the answer with the maximum possible integer value
let ans = Number.MAX_SAFE_INTEGER;
// Iterate through each element in the array
for (let i = 0; i < n; i++) {
// Iterate through elements that are at least 'x' indices apart
for (let j = i + x; j < n; j++) {
// Compute the absolute difference and update the minimum answer
ans = Math.min(ans, Math.abs(nums[i] - nums[j]));
}
}
// Return the minimum absolute difference found
return ans;
};Minimum Absolute Difference Between Elements With Constraint Complexity Analysis (brute force)
Time Complexity: O(n²)
The brute force solution consists of two nested loops:
- Outer Loop iterates over all elements in the array (i from 0 to n - 1).
Runs O(n) times. - Inner Loop starts from i + x and iterates to the end of the array (j from i + x to n - 1).
In the worst case, it runs O(n) times.
Overall Complexity
Since both loops run in O(n) and O(n) respectively, the worst-case time complexity is: O(n²)
Space Complexity: O(n)
- Auxiliary Space Complexity: O(1)
The algorithm only uses a few integer variables (n, ans, i, j), all of which take O(1) space.
Therefore, the auxiliary space complexity is O(1). - Total Space Complexity: O(n)
The total space complexity of the approach is O(n), used for input array nums.
Therefore, the total space complexity is O(n).
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n²), where n is the number of elements in the array (nums.length), with an upper limit of 10⁵.
In the worst-case scenario, when n is at its maximum constraint (10⁵), the total number of operations can be as large as (10⁵)² = 10¹⁰.
This time complexity becomes highly inefficient for large values of n, particularly when n = 10⁵, leading to billions of operations. While this may work for small test cases, it could cause Time Limit Exceeded (TLE) errors for large inputs due to excessive computations.
In competitive programming, the typical acceptable time complexity limit is around 10⁶ operations per test case. Since this solution may perform significantly more operations (10¹⁰ in the worst case), it is highly impractical for large inputs and needs optimization.
How to optimize it?
We are given a 0-indexed integer array nums and an integer x. Our task is to find two elements in the array that are at least x indices apart and have the minimum absolute difference.
A brute-force approach would involve checking all possible pairs (i, j) where abs(i - j) >= x and computing abs(nums[i] - nums[j]). This results in an O(n²) complexity, which is too slow for large inputs (up to 10⁵ elements).
Instead of checking every pair one by one, what if we could efficiently store and search for elements that are at least x indices apart?
Each time we move forward, we should keep track of elements that are at least x indices before the current index.
This will allow us to efficiently find the closest number to nums[i] instead of checking all previous numbers.
We need a data structure that allows:
- Insertion of elements (as we move forward in the array).
- Efficient lookup to find the closest element to nums[i] (to minimize absolute difference).
Which Data Structure Can Help?
A set (ordered collection of unique elements) is a perfect choice because:
It stores elements in sorted order, and it allows us to efficiently find the closest number j, such that abs(nums[i] - nums[j]) can be minimized.
Imagine you have a sorted list of numbers, and you want to check whether a particular number exists in the list.
If you use a linear search (checking each number one by one), it would take O(n) time in the worst case.
But wait! Since the list is sorted, can we do better?
Yes! Instead of going step by step, we can jump directly to the middle of the list and decide whether to search in the left half or the right half.
This reduces the number of comparisons significantly, leading to O(log n) time instead of O(n).
Minimum Absolute Difference Between Elements With Constraint Algorithm
We start by iterating through the array while maintaining a set of elements that are at least x indices apart from the current element. This ensures that for every nums[i], we only compare it with valid elements that satisfy the constraint abs(i - j) >= x.
At each step, before processing nums[i], we insert nums[i - x] into the set. This means the set will always contain elements that are exactly x or more indices behind the current position. The reason we insert before searching is that we only want to compare nums[i] with elements that have already been processed and are at least x indices apart.
Once we have inserted nums[i - x], we need to find the element in the set that is closest to nums[i]. To do this efficiently, we use lower_bound, which finds the smallest number in the set that is greater than or equal to nums[i]. This helps in finding one of the closest elements.
However, the closest element might also be just before the found element in the sorted order, so we check prev(it) as well (if it exists). Comparing both options ensures that we truly find the minimum absolute difference.
Consider the array nums = [3, 8, 15, 20, 25] and x = 2.
At some point in our iteration, we reach nums[3] = 20, and our set contains {3, 8, 15} (elements that are at least x = 2 indices apart).
Now, we use lower_bound(20) on this set:
- lower_bound(20) will return the first element in the set that is ≥ 20.
- The set contains {3, 8, 15}, and since no element is ≥ 20, the iterator points to the end of the set (which means there's no valid result from lower_bound).
If we only relied on lower_bound, we wouldn't find any valid element!
However, the previous element in the sorted order is 15, which is the closest valid element to 20.
- abs(20 - 15) = 5, which is the correct minimum absolute difference.
Thus, by checking prev(it) whenever lower_bound doesn't return an exact match, we ensure we always find the closest possible element.
What is lower_bound?
The lower_bound(value) function in C++ finds the first element in a sorted container that is greater than or equal to the given value. It returns an iterator pointing to that element. If no such element exists, it returns an iterator to the end of the container.
- it = st.lower_bound(nums[i]) → Finds the first element in the set that is ≥ nums[i].
- prev(it) → Gives the element just before the found element in sorted order, ensuring we also check the closest smaller value.
By checking both it and prev(it) (if possible), we make sure we find the minimum absolute difference efficiently.
Alternatives of lower_bound(value) in Different Languages
- Java: treeSet.ceiling(value) → Finds the smallest element ≥ value. Use treeSet.floor(value) for the previous element.
- Python: bisect.bisect_left(sorted_list, value) → Returns the index of the first element ≥ value. Use sorted_list[index - 1] if index > 0 for the previous element.
- JavaScript: Use binary search on a sorted array to find the first element ≥ value, and sortedArr[index - 1] for the previous element.
After finding the closest element, we calculate the absolute difference abs(nums[i] - closest_value), and update our ans variable if this difference is smaller than the current minimum. This process is repeated for all elements in the array, ensuring we always maintain the smallest possible absolute difference found so far.
By maintaining a sorted set and using binary search (lower_bound), we efficiently handle each query in O(log n) time, making the entire approach run in O(n log n) complexity. This allows us to solve the problem optimally even for large inputs.
Let us understand this with a video.
minimum-absolute-difference-between-elements-with-constraint-optimal-approach-animation
Let's understand with an example:
Minimum Absolute Difference Between Elements With Constraint Example:
Let's do a concise dry run for nums = [5, 3, 2, 10, 15] with x = 1 using the corrected approach.
Initial State:
- Set (st): Empty {}
- ans: INT_MAX
Iteration 1 (i = 1, nums[i] = 3)
- Insert nums[0] = 5 into st → {5}
- it = lower_bound(3) → {5} (first element greater or equal to 3)
- |3 - 5| = 2 (update ans = 2)
- it is the first element, so prev(it) is not checked
- ans = 2
Iteration 2 (i = 2, nums[i] = 2)
- Insert nums[1] = 3 into st → {3, 5}
- it = lower_bound(2) → {3}
- |2 - 3| = 1 (update ans = 1)
- it is the first element, so prev(it) is not checked
- ans = 1
Iteration 3 (i = 3, nums[i] = 10)
- Insert nums[2] = 2 into st → {2, 3, 5}
- it = lower_bound(10) → Not found (end of set)
- No update from upper bound
- prev(it) = 5 (last element in set)
- |10 - 5| = 5 (no update to ans)
- ans = 1
Iteration 4 (i = 4, nums[i] = 15)
- Insert nums[3] = 10 into st → {2, 3, 5, 10}
- it = lower_bound(15) → Not found (end of set)
- No update from upper bound
- prev(it) = 10
- |15 - 10| = 5 (no update to ans)
- ans = 1
Final Output:
ans = 1, which is the minimum absolute difference for elements at least x = 1 indices apart.
How to code it up:
Here are the concise generic steps to implement the solution:
1. Initialize Data Structures
- Use a sorted set (like TreeSet in Java, set in C++) to maintain elements at least x indices apart.
- Initialize a variable to store the minimum absolute difference.
2. Iterate Through the Array
- Start iterating from index x to ensure valid comparisons.
- Insert the element nums[i - x] into the sorted set.
3. Find the Closest Element
- Use binary search (lower bound) to find the smallest element in the set that is greater than or equal to nums[i].
- Also, check the previous element (if exists) as it might be closer.
4. Update the Minimum Difference
- Compute absolute differences and update the minimum found so far.
5. Return the Result
- After checking all valid elements, return the smallest absolute difference found.
Minimum Absolute Difference Between Elements With Constraint leetcode Solution
Minimum Absolute Difference Between Elements With Constraint solution / Code Implementation
1. Minimum Absolute Difference Between Elements With Constraint solution in C++ Try on Compiler
class Solution {
public:
int minAbsoluteDifference(vector<int>& nums, int x) {
int n = nums.size();
// Initialize answer as the maximum possible integer value
int ans = INT_MAX;
// Set to maintain elements that are at least 'x' indices apart
set<int> st;
// Iterate from index 'x' to the end of the array
for (int i = x; i < n; i++) {
// Insert the element that is 'x' indices behind into the set
st.insert(nums[i - x]);
// Find the smallest element in the set that is >= nums[i]
auto it = st.lower_bound(nums[i]);
// If such an element exists, update the minimum absolute difference
if (it != st.end()) {
ans = min(ans, abs(nums[i] - *it));
}
// If there is a smaller element just before 'it', check that as well
if (it != st.begin()) {
ans = min(ans, abs(nums[i] - *prev(it)));
}
}
// Return the minimum absolute difference found
return ans;
}
};
2. Minimum Absolute Difference Between Elements With Constraint solution in Java Try on Compiler
import java.util.*;
class Solution {
public int minAbsoluteDifference(List<Integer> nums, int x) {
int n = nums.size();
// Initialize answer as the maximum possible integer value
int ans = Integer.MAX_VALUE;
// TreeSet to maintain sorted order and allow binary search operations
TreeSet<Integer> st = new TreeSet<>();
// Iterate from index 'x' to the end of the list
for (int i = x; i < n; i++) {
// Insert the element that is 'x' indices behind into the set
st.add(nums.get(i - x));
// Find the smallest element in the set that is >= nums[i]
Integer it = st.ceiling(nums.get(i));
if (it != null) {
ans = Math.min(ans, Math.abs(nums.get(i) - it));
}
// Find the largest element in the set that is < nums[i]
Integer prevIt = st.lower(nums.get(i));
if (prevIt != null) {
ans = Math.min(ans, Math.abs(nums.get(i) - prevIt));
}
}
// Return the minimum absolute difference found
return ans;
}
}
3. Minimum Absolute Difference Between Elements With Constraint solution in Python Try on Compiler
from sortedcontainers import SortedSet
class Solution:
def minAbsoluteDifference(self, nums, x):
n = len(nums)
# Initialize answer as the maximum possible integer value
ans = float('inf')
# SortedSet to maintain sorted order and allow binary search operations
st = SortedSet()
# Iterate from index 'x' to the end of the array
for i in range(x, n):
# Insert the element that is 'x' indices behind into the set
st.add(nums[i - x])
# Find the smallest element in the set that is >= nums[i]
idx = st.bisect_left(nums[i])
if idx < len(st):
ans = min(ans, abs(nums[i] - st[idx]))
# Find the largest element in the set that is < nums[i]
if idx > 0:
ans = min(ans, abs(nums[i] - st[idx - 1]))
# Return the minimum absolute difference found
return ans
4. Minimum Absolute Difference Between Elements With Constraint solution in Javascript Try on Compiler
/**
* @param {number[]} nums
* @param {number} x
* @return {number}
*/
var minAbsoluteDifference = function (nums, x) {
let n = nums.length;
// Initialize answer as the maximum possible integer value
let ans = Infinity;
// Set to maintain sorted order (using an array with binary search)
let st = [];
// Helper function for binary search insertion point
function lowerBound(arr, target) {
let low = 0, high = arr.length;
while (low < high) {
let mid = Math.floor((low + high) / 2);
if (arr[mid] < target) low = mid + 1;
else high = mid;
}
return low;
}
// Iterate from index 'x' to the end of the array
for (let i = x; i < n; i++) {
// Insert the element that is 'x' indices behind into the sorted array
let insertIdx = lowerBound(st, nums[i - x]);
st.splice(insertIdx, 0, nums[i - x]);
// Find the smallest element in the set that is >= nums[i]
let idx = lowerBound(st, nums[i]);
if (idx < st.length) {
ans = Math.min(ans, Math.abs(nums[i] - st[idx]));
}
// Find the largest element in the set that is < nums[i]
if (idx > 0) {
ans = Math.min(ans, Math.abs(nums[i] - st[idx - 1]));
}
}
// Return the minimum absolute difference found
return ans;
};Minimum Absolute Difference Between Elements With Constraint Complexity Analysis (binary search)
Time Complexity: O(n log n)
Let n be the size of the array nums. The operations performed in the solution include:
- Iterating Through the Array (O(n))
- We traverse the array once from index x to n, so this step takes O(n) time.
- Insertion into a Sorted Set (O(log n))
- At each step, we insert nums[i - x] into the sorted set. Since a balanced binary search tree (BST) backs the set, insertion takes O(log n).
- Finding Lower Bound (O(log n))
- The lower_bound operation in a BST (such as set in C++ or TreeSet in Java) takes O(log n).
- Checking the Previous Element (O(1))
- We check the element before lower_bound(it), which is a constant-time operation O(1).
Overall Complexity
Each iteration performs:
- One insertion (O(log n))
- One lower_bound lookup (O(log n))
- A constant-time check (O(1))
Thus, for n iterations, the total complexity is: O(n log n)
Space Complexity: O(n)
- Auxiliary Space Complexity: O(n)
The set (or TreeSet) stores up to n elements in the worst case, leading to O(n) extra space.
Therefore, the auxiliary space complexity is O(n). - Total Space Complexity: O(n)
The input array nums is already provided, so it does not count as extra space.
Therefore, the total space complexity is O(n).
Similar Problems
When working with array problems that require finding elements with the minimum difference, Binary Search can be an efficient approach, especially when the array is sorted. In the Minimum Difference Element in a Sorted Array problem, we can use Binary Search to quickly locate the closest element to a given target, reducing the need for a linear scan. Similarly, in the Minimum Absolute Difference Between Two Arrays, using an Ordered Set allows efficient insertion and retrieval of elements while maintaining order, helping us quickly determine the closest match from another array. Combining Binary Search with an Ordered Set can significantly optimize such problems, making them more efficient compared to brute-force approaches.
Now that we have successfully tackled this problem let's try similar problems.
Given an array of integers nums and an integer k, return the number of unique k-diff pairs in the array.
A k-diff pair is an integer pair (nums[i], nums[j]), where the following are true:
- 0 <= i, j < nums.length
- i != j
- |nums[i] - nums[j]| == k
Notice that |val| denotes the absolute value of val.
You are given a 0-indexed integer array nums and two integers key and k. A k-distant index is an index i of nums for which there exists at least one index j such that |i - j| <= k and nums[j] == key.
Return a list of all k-distant indices sorted in increasing order.
You are given a 0-indexed integer array nums having length n, an integer indexDifference, and an integer valueDifference.
Your task is to find two indices i and j, both in the range [0, n - 1], that satisfy the following conditions:
- abs(i - j) >= indexDifference, and
- abs(nums[i] - nums[j]) >= valueDifference
Return an integer array answer, where answer = [i, j] if there are two such indices, and answer = [-1, -1] otherwise. If there are multiple choices for the two indices, return any of them.
Note: i and j may be equal.
4. Find Indices With Index and Value Difference II
You are given a 0-indexed integer array nums having length n, an integer indexDifference, and an integer valueDifference.
Your task is to find two indices i and j, both in the range [0, n - 1], that satisfy the following conditions:
- abs(i - j) >= indexDifference, and
- abs(nums[i] - nums[j]) >= valueDifference
Return an integer array answer, where answer = [i, j] if there are two such indices, and answer = [-1, -1] otherwise. If there are multiple choices for the two indices, return any of them.
Note: i and j may be equal.