Minimum Distance to the Target Element

EASY

Description

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] <= 10⁴
0 <= start < nums.length
target is in nums.

Approaches

Checkout 2 different approaches to solve Minimum Distance to the Target Element. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 Analysis

Time Complexity: 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 Complexity: O(1), as we only use a constant amount of extra memory for variables like `minDistance` and the loop index.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Minimum Distance to the Target Element. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Minimum Distance to the Target Element

Data Structures:

Array

Companies:

Honeywell |