Minimum Distance to the Target Element | Simple Explanation | Early Break | Leetcode 1848 | MIK
Minimum Distance to the Target Element - Video Solution
Watch 10 video solutions for Minimum Distance to the Target Element, a easy level problem involving Array. This walkthrough by codestorywithMIK has 2,614 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
Approach Overview
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.
Complexity Analysis
| 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 |