Problem Description

You are given an integer array arr, an integer target, and an integer start representing an index in arr.
Your task is to find the minimum distance from start to any index i such that arr[i] == target. The distance between two indices i and j is defined as |i - j| (the absolute difference).
It is guaranteed that target exists in arr.
Key constraints:

• There is at least one occurrence of target in arr.
• You may not need to check every element, but you must find the minimum distance.
• Each index can be used only once; do not reuse elements.

Thought Process

To solve this problem, the first idea that comes to mind is to check every index in arr to see if it matches the target. For each match, calculate the distance from start and keep track of the smallest distance found.
This is a straightforward brute-force approach, but for small arrays or a single occurrence of target, it is efficient enough. However, for larger arrays, we might look for optimizations.
Since the array is not sorted and the only way to know where target occurs is to check each element, there is no way to avoid scanning the array. However, as soon as we find a target at a certain distance, we can compare it to our current minimum and update if necessary.
The problem is simple enough that the brute-force approach is actually optimal, as we have to check all potential candidates to ensure the minimum is found.

Solution Approach

Let's break down the steps to solve the problem:

1. Initialize a variable min_distance to a large value (e.g., the length of the array).
2. Iterate through each index i in arr:
   • If arr[i] equals target:
     • Compute the distance as abs(i - start).
     • If this distance is less than min_distance, update min_distance.
3. After checking all indices, return min_distance.

Design Justification:

• We use a simple loop and a variable to keep track of the minimum, which is both easy to understand and efficient.
• Since we must check all occurrences of target, this is the best possible approach given the constraints.

Example Walkthrough

Sample Input:
arr = [4, 2, 3, 4, 5, 4], target = 4, start = 2
Step-by-step:

• Initialize min_distance = 6 (length of arr).
• Check index 0: arr[0] = 4 (matches target)
  • Distance: |0 - 2| = 2
  • Update min_distance = 2
• Check index 1: arr[1] = 2 (not target)
• Check index 2: arr[2] = 3 (not target)
• Check index 3: arr[3] = 4 (matches target)
  • Distance: |3 - 2| = 1
  • Update min_distance = 1
• Check index 4: arr[4] = 5 (not target)
• Check index 5: arr[5] = 4 (matches target)
  • Distance: |5 - 2| = 3
  • min_distance remains 1

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O(n), where n is the length of arr. We must check each element once.
• Space Complexity: O(1), as we only use a variable to store the minimum distance.

• There is no faster approach possible, since we do not know where target values are located without scanning the array.
• Thus, the brute-force approach is already optimal.

Summary

The problem asks us to find the minimum distance from a given start index to any occurrence of a target value in an array. By iterating through the array and tracking the smallest distance found, we arrive at the answer efficiently. The approach is straightforward, leverages only basic looping and comparison, and is optimal for this scenario. This makes the solution both elegant and easy to understand for programmers at any level.

Code Implementation

class Solution:
    def getMinDistance(self, arr, target, start):
        min_distance = len(arr)
        for i, val in enumerate(arr):
            if val == target:
                dist = abs(i - start)
                if dist < min_distance:
                    min_distance = dist
        return min_distance
      

class Solution {
public:
    int getMinDistance(vector<int>& arr, int target, int start) {
        int min_distance = arr.size();
        for (int i = 0; i < arr.size(); ++i) {
            if (arr[i] == target) {
                int dist = abs(i - start);
                if (dist < min_distance) {
                    min_distance = dist;
                }
            }
        }
        return min_distance;
    }
};
      

class Solution {
    public int getMinDistance(int[] arr, int target, int start) {
        int min_distance = arr.length;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                int dist = Math.abs(i - start);
                if (dist < min_distance) {
                    min_distance = dist;
                }
            }
        }
        return min_distance;
    }
}
      

var getMinDistance = function(arr, target, start) {
    let min_distance = arr.length;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            let dist = Math.abs(i - start);
            if (dist < min_distance) {
                min_distance = dist;
            }
        }
    }
    return min_distance;
};