Scale Engineer

Minimum Absolute Difference Between Elements With Constraint

Med
#2521Time: O(n^2), where `n` is the number of elements in `nums`. The nested loops lead to a quadratic number of comparisons in the worst case (when `x` is small).Space: O(1), as we only use a constant amount of extra space for variables.3 companies
Algorithms
Binary Search
Data structures
ArrayOrdered Set
Companies
RobloxCapital OneDatabricks

Prompt

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.

 

Example 1:

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.

Example 2:

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.

Example 3:

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 <= 105
  • 1 <= nums[i] <= 109
  • 0 <= x < nums.length

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. We check every possible pair of indices (i, j) that satisfies the condition abs(i - j) >= x. For each valid pair, we calculate the absolute difference of the corresponding elements and keep track of the minimum difference found.

Algorithm

  • Initialize a variable minDifference to Integer.MAX_VALUE.
  • Get the length of the array, n.
  • Loop for i from 0 to n - 1.
  • Inside this loop, start another loop for j from i + x to n - 1.
  • This ensures that for any pair of indices (i, j), the condition j - i >= x is always met.
  • Calculate currentDifference = abs(nums[i] - nums[j]).
  • Update minDifference = min(minDifference, currentDifference).
  • After both loops complete, return minDifference.

Walkthrough

The core idea is to check every pair of indices (i, j) that satisfies the distance constraint abs(i - j) >= x and find the minimum difference abs(nums[i] - nums[j]).

  • Initialize a variable minDifference to a very large value, like Integer.MAX_VALUE.
  • Use two nested loops. The outer loop iterates i from 0 to n-1.
  • The inner loop iterates j from i + x to n-1. This setup ensures that for any pair (i, j), the condition j - i >= x holds, which implies abs(j - i) >= x.
  • Inside the inner loop, calculate the absolute difference between nums.get(i) and nums.get(j).
  • Compare this difference with minDifference and update minDifference if the new difference is smaller.
  • After the loops complete, minDifference will contain the result.

Here is the Java implementation:

import java.util.List; class Solution {    public int minAbsoluteDifference(List<Integer> nums, int x) {        int minDifference = Integer.MAX_VALUE;        int n = nums.size();        for (int i = 0; i < n; i++) {            for (int j = i + x; j < n; j++) {                int diff = Math.abs(nums.get(i) - nums.get(j));                minDifference = Math.min(minDifference, diff);            }        }        return minDifference;    }}

Complexity

Time

O(n^2), where `n` is the number of elements in `nums`. The nested loops lead to a quadratic number of comparisons in the worst case (when `x` is small).

Space

O(1), as we only use a constant amount of extra space for variables.

Trade-offs

Pros

  • Simple to understand and implement.

  • Uses constant extra space.

Cons

  • Highly inefficient for large inputs due to its quadratic time complexity.

  • Will likely result in a 'Time Limit Exceeded' error on platforms with strict time limits for the given constraints.

Solutions

class Solution {public  int minAbsoluteDifference(List<Integer> nums, int x) {    TreeMap<Integer, Integer> tm = new TreeMap<>();    int ans = 1 << 30;    for (int i = x; i < nums.size(); ++i) {      tm.merge(nums.get(i - x), 1, Integer : : sum);      Integer key = tm.ceilingKey(nums.get(i));      if (key != null) {        ans = Math.min(ans, key - nums.get(i));      }      key = tm.floorKey(nums.get(i));      if (key != null) {        ans = Math.min(ans, nums.get(i) - key);      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem