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.lengthtarget is in nums.Problem Overview: You are given an integer array nums, a target value, and a start index. The task is to return the minimum absolute distance between start and any index i where nums[i] == target. The array may contain multiple occurrences of the target, so you must check all candidates and choose the smallest distance.
Approach 1: Linear Search from Start (Time: O(n), Space: O(1))
The simplest solution is a full scan of the array. Iterate through every index i from 0 to n-1. Whenever nums[i] equals the target, compute the distance using abs(i - start) and keep track of the minimum value seen so far. This approach relies on a straightforward traversal of the array and constant-time comparisons. Since every element is visited once, the time complexity is O(n), while memory usage stays O(1) because only a few variables are stored. This method is reliable and easy to implement in any language.
Approach 2: Bi-directional Search (Time: O(n) worst case, Space: O(1))
A more intuitive strategy is to start from the start index and expand outward in both directions. Check positions start, start-1, start+1, start-2, start+2, and so on until the target is found. The first match encountered automatically gives the minimum distance because the search expands in increasing distance order. This pattern resembles a two-sided pointer expansion similar to techniques used in two pointer problems. In the best case, the target is adjacent to start and the algorithm returns immediately. In the worst case, the scan reaches the ends of the array, resulting in O(n) time and O(1) space.
The bidirectional technique reduces unnecessary checks when the closest target lies near the starting position. However, its worst-case performance is still linear because the algorithm may need to inspect every element.
Recommended for interviews: The linear scan is usually the expected baseline solution. It clearly demonstrates understanding of array traversal and absolute distance calculation. The bi-directional expansion is a nice optimization idea and shows problem-solving intuition. In interviews, start with the linear approach, explain its O(n) complexity, then mention the bidirectional strategy as an improvement that can terminate earlier when the closest target is near the starting index.
The simplest approach is to iterate through the entire array and check for each target occurrence. Calculate the absolute difference between the current index and the start index. Keep track of the minimum difference encountered and return that value.
This C program defines a function minDistance that iterates through the array, checking each element against the target. For each match, it calculates the absolute distance and updates the minimum distance accordingly.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), as we are using a constant amount of space.
This approach leverages the possibility of starting two pointers, one from the start index moving forward and the other moving backward, thereby potentially reducing the number of elements to check before finding the target. The method stops early if a zero-distance index is found, as it represents the minimum possible distance.
The C implementation uses two pointers, left and right, starting from the start index. They move towards the left and right ends of the array, respectively, seeking the target.
Time Complexity: O(n/2) on average, though still O(n) in the worst-case scenario.
Space Complexity: O(1)
Traverse the array, find all indices equal to target, then calculate |i - start|, and take the minimum value.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Linear Search from Start | Time Complexity: O(n), where n is the length of the array. |
| Bi-directional Search | Time Complexity: O(n/2) on average, though still O(n) in the worst-case scenario. |
| Single Pass | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Search from Start | O(n) | O(1) | General solution for any array; simplest and most common interview approach |
| Bi-directional Search | O(n) worst case | O(1) | Useful when the closest target is expected near the start index, allowing early termination |
1848. Minimum Distance to the Target Element | Leetcode weekly problem | Ayushi Rawat • Ayushi Rawat • 840 views views
Watch 9 more video solutions →Practice Minimum Distance to the Target Element with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor