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.
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; }}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.