Minimum Distance to the Target Element

Difficulty: Easy | Acceptance: 64.60% | Paid: No Topics: Array

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).

• Examples
• Constraints
• Linear Scan
• Bidirectional Scan

Examples

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 <= 10^5
-1000 <= nums[i] <= 1000
0 <= start < nums.length
-1000 <= target <= 1000

Linear Scan

Intuition The simplest way to find the minimum distance is to iterate through the entire array. For every element that matches the target, we calculate its distance from the start index and keep track of the minimum value found so far.

Steps

• Initialize a variable min_dist to a large value (e.g., the length of the array).
• Iterate through the array using a loop index i.
• If nums[i] equals target, calculate the absolute difference abs(i - start).
• Update min_dist if the current difference is smaller.
• Return min_dist after the loop completes.

class Solution:
    def getMinDistance(self, nums: list[int], target: int, start: int) -> int:
        min_dist = len(nums)
        for i, num in enumerate(nums):
            if num == target:
                min_dist = min(min_dist, abs(i - start))
        return min_dist

Complexity

• Time: O(n) - We traverse the array once.
• Space: O(1) - We only use a few variables for storage.
• Notes: This approach is straightforward and efficient enough given the constraints (n ≤ 10⁵).

Bidirectional Scan

Intuition Since we are looking for the index closest to start, we can expand outwards from start instead of scanning from the beginning. We check start, then start-1 and start+1, then start-2 and start+2, and so on. The first match we find is guaranteed to be the closest.

Steps

• Initialize two pointers, left = start and right = start.
• Loop while left is within bounds or right is within bounds.
• Check if left is valid and nums[left] == target. If so, return start - left.
• Check if right is valid and nums[right] == target. If so, return right - start.
• Decrement left and increment right to expand the search radius.

class Solution:
    def getMinDistance(self, nums: list[int], target: int, start: int) -> int:
        n = len(nums)
        left, right = start, start
        while left >= 0 or right < n:
            if left >= 0 and nums[left] == target:
                return start - left
            if right < n and nums[right] == target:
                return right - start
            left -= 1
            right += 1
        return -1 # Should not be reached per problem constraints

Complexity

• Time: O(n) - In the worst case (target at one end, start at the other), we visit all elements.
• Space: O(1) - Constant extra space used.
• Notes: This approach can be faster on average if the target is near the start index, as it terminates early without scanning the whole array.