# Minimum Distance to the Target Element
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-distance-to-the-target-element)
Canonical: https://scaleengineer.com/dsa/problems/minimum-distance-to-the-target-element
**Data structures:** Array
**Companies:** [Honeywell](https://scaleengineer.com/companies/honeywell)
---
## Problem
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 <= 1000`
* `1 <= nums[i] <= 104`
* `0 <= start < nums.length`
* `target` is in `nums`.

# Approaches
## Brute Force: Full Scan
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.
**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.
**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 `start` index itself.; It does not leverage the problem's structure, which is to find the minimum distance from a specific point.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize a variable `minDistance` to a very large value, such as `Integer.MAX_VALUE`.
- Iterate through the `nums` array with an index `i` from `0` to `nums.length - 1`.
- Inside the loop, check if `nums[i]` is equal to `target`.
- If it is, calculate the distance `d = abs(i - start)`.
- Update `minDistance` by taking the minimum of the current `minDistance` and `d`.
- After the loop completes, return `minDistance`.

## Optimized Search: Expanding from Start
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`.
**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.
**Pros:** Significantly more efficient on average than a full scan, especially when the target is close to the `start` index.; 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 `start` index.
### Explanation
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.

```java
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.
    }
}
```
### Algorithm
- Start a loop with a search `offset` from `0` up to `nums.length - 1`.
- In each iteration, check two indices: `start - offset` (left) and `start + offset` (right).
- First, check the right index: `right = start + offset`. If `right` is within the array bounds (`< nums.length`) and `nums[right]` equals `target`, return `offset`.
- Next, check the left index: `left = start - offset`. If `left` is within the array bounds (`>= 0`) and `nums[left]` equals `target`, return `offset`.
- Since the target is guaranteed to exist, the loop will find a match and return the `offset`, which represents the minimum distance.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 )
```