Minimum Distance to the Target Element
EasyPrompt
Given an integer array nums (0-indexed) and two integers target and start, find an index i such that nums[i] == target and abs(i - start) is minimized. Note that abs(x) is the absolute value of x.
Return abs(i - start).
It is guaranteed that target exists in nums.
Example 1:
Input: nums = [1,2,3,4,5], target = 5, start = 3
Output: 1
Explanation: nums[4] = 5 is the only value equal to target, so the answer is abs(4 - 3) = 1.Example 2:
Input: nums = [1], target = 1, start = 0
Output: 0
Explanation: nums[0] = 1 is the only value equal to target, so the answer is abs(0 - 0) = 0.Example 3:
Input: nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0
Output: 0
Explanation: Every value of nums is 1, but nums[0] minimizes abs(i - start), which is abs(0 - 0) = 0.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 1040 <= start < nums.lengthtargetis innums.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves a straightforward linear scan of the entire array. We iterate through each element from the beginning to the end. For every element that matches the target, we calculate its absolute distance from the start index. We maintain a variable to keep track of the minimum distance found so far, updating it whenever a smaller distance is calculated.
Algorithm
- Initialize a variable
minDistanceto a very large value, such asInteger.MAX_VALUE. - Iterate through the
numsarray with an indexifrom0tonums.length - 1. - Inside the loop, check if
nums[i]is equal totarget. - If it is, calculate the distance
d = abs(i - start). - Update
minDistanceby taking the minimum of the currentminDistanceandd. - After the loop completes, return
minDistance.
Walkthrough
We begin by initializing a variable, minDistance, to a value larger than any possible distance, for instance, Integer.MAX_VALUE. We then loop through the nums array from index 0 to nums.length - 1. In each iteration, we compare the current element nums[i] with the target. If they match, we compute the absolute difference Math.abs(i - start). This calculated distance is then compared with minDistance, and minDistance is updated to the smaller of the two values. Since the problem guarantees that the target exists in the array, after checking all elements, minDistance will hold the required minimum distance.
class Solution { public int getMinDistance(int[] nums, int target, int start) { int minDistance = Integer.MAX_VALUE; for (int i = 0; i < nums.length; i++) { if (nums[i] == target) { minDistance = Math.min(minDistance, Math.abs(i - start)); } } return minDistance; }}Complexity
Time
O(N), where N is the number of elements in the `nums` array. In the worst-case scenario, we have to iterate through the entire array to find the target or to confirm we have found the minimum distance.
Space
O(1), as we only use a constant amount of extra memory for variables like `minDistance` and the loop index.
Trade-offs
Pros
The logic is very simple to understand and implement.
It is guaranteed to find the correct answer because it checks every possibility.
Cons
It is inefficient because it always scans the entire array, even if the target element is at the
startindex itself.It does not leverage the problem's structure, which is to find the minimum distance from a specific point.
Instead of scanning the entire array, a more optimized approach is to search outwards from the start index. We can think of this as an expanding search window. We first check the start index itself (distance 0), then the indices at distance 1 (start-1, start+1), then distance 2 (start-2, start+2), and so on. The very first time we find the target, we can be certain that we have found the minimum distance, because we are exploring indices in increasing order of their distance from start.
Algorithm
- Start a loop with a search
offsetfrom0up tonums.length - 1. - In each iteration, check two indices:
start - offset(left) andstart + offset(right). - First, check the right index:
right = start + offset. Ifrightis within the array bounds (< nums.length) andnums[right]equalstarget, returnoffset. - Next, check the left index:
left = start - offset. Ifleftis within the array bounds (>= 0) andnums[left]equalstarget, returnoffset. - Since the target is guaranteed to exist, the loop will find a match and return the
offset, which represents the minimum distance.
Walkthrough
This method starts the search from the start index and expands in both directions simultaneously. We can use a loop that increments an offset variable, starting from 0. In each iteration of the loop, we check the elements at start - offset and start + offset. We must be careful to perform boundary checks to ensure these indices are valid before accessing the array. If the element at either of these indices matches the target, we have found the closest occurrence. The minimum distance is simply the current offset, and we can return it immediately. This avoids unnecessary checks of elements that are further away. Since the problem guarantees the target exists, this search is guaranteed to terminate.
class Solution { public int getMinDistance(int[] nums, int target, int start) { // The problem guarantees target exists, so we don't need an infinite loop. // A loop up to nums.length is sufficient. for (int offset = 0; offset < nums.length; offset++) { int rightIndex = start + offset; if (rightIndex < nums.length && nums[rightIndex] == target) { return offset; } // We don't need to check left for offset 0, as it's the same as right. int leftIndex = start - offset; if (offset != 0 && leftIndex >= 0 && nums[leftIndex] == target) { return offset; } } return -1; // This line is unreachable given the problem constraints. }}Complexity
Time
O(k), where `k` is the minimum distance `abs(i - start)`. In the best case, `k=0` and the complexity is O(1). In the worst case, the closest target is at one of the array's ends while `start` is at the other, making `k` proportional to `N`, so the worst-case complexity is O(N).
Space
O(1), as only a few variables are needed to keep track of the offset and indices, requiring constant extra space.
Trade-offs
Pros
Significantly more efficient on average than a full scan, especially when the target is close to the
startindex.It stops as soon as the first and closest match is found.
The best-case time complexity is O(1), which occurs when
nums[start] == target.
Cons
The worst-case time complexity is still O(N), which is the same as the brute-force approach.
The implementation is slightly more complex due to the need for boundary checks on both sides of the
startindex.
Solutions
Solution
class Solution {public int getMinDistance(int[] nums, int target, int start) { int n = nums.length; int ans = n; for (int i = 0; i < n; ++i) { if (nums[i] == target) { ans = Math.min(ans, Math.abs(i - start)); } } return ans; }}class Solution {public: int getMinDistance(vector<int> &nums, int target, int start) { int n = nums.size(); int ans = n; for (int i = 0; i < n; ++i) { if (nums[i] == target) { ans = min(ans, abs(i - start)); } } return ans; }};class Solution : def getMinDistance ( self , nums : List [ int ], target : int , start : int ) -> int : return min ( abs ( i - start ) for i , x in enumerate ( nums ) if x == target )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.