Problem Description

You are given an integer array nums (0-indexed), a target value, and a start index. Your task is to find an index i in the array where nums[i] equals target, and the distance between i and start is as small as possible.

The distance is calculated as the absolute difference: abs(i - start), where abs(x) represents the absolute value of x.

Return the minimum distance abs(i - start).

The problem guarantees that the target value exists at least once in the array nums.

For example, if nums = [1, 2, 3, 4, 5], target = 3, and start = 4, the target value 3 appears at index 2. The distance would be abs(2 - 4) = 2.

The solution approach iterates through the array once, identifies all indices where the value equals target, calculates the distance from each of these indices to start, and returns the minimum distance found.

Intuition

Since we need to find the minimum distance between the start index and any index containing the target value, the straightforward approach is to check all possible positions where target appears in the array.

The key insight is that we don't need any complex algorithm or data structure - we simply need to examine every occurrence of target and keep track of which one is closest to start.

Think of it like finding the nearest gas station from your current location. You would check the distance to each gas station and pick the closest one. Similarly, we check the distance from start to each index where target appears.

The distance calculation abs(i - start) handles both cases automatically:

• When the target is to the left of start (i < start), the distance is start - i
• When the target is to the right of start (i > start), the distance is i - start

By using the absolute value function, we don't need to worry about the direction - we just care about the magnitude of the distance.

Since we're guaranteed that target exists in the array, we can confidently iterate through all elements, filter for those equal to target, calculate their distances from start, and return the minimum value found. This gives us an optimal solution in a single pass through the array with O(n) time complexity.

Solution Approach

The solution uses a single pass approach with Python's built-in functions to achieve a concise implementation.

The implementation breaks down into these steps:

1. Enumerate the array: Using enumerate(nums), we get both the index i and the value x for each element in the array.

2. Filter for target values: The condition if x == target filters the enumeration to only include indices where the value equals our target.

3. Calculate distances: For each matching index i, we compute abs(i - start) to get the distance from the start position.

4. Find minimum: The min() function takes all these calculated distances and returns the smallest one.

The entire solution is implemented as a generator expression inside the min() function:

min(abs(i - start) for i, x in enumerate(nums) if x == target)

This approach leverages Python's generator expression, which is memory-efficient as it doesn't create an intermediate list of all distances. Instead, it calculates distances on-the-fly and passes them to the min() function.

Time Complexity: O(n) where n is the length of the array, as we traverse the entire array once.

Space Complexity: O(1) as we only use a constant amount of extra space - the generator doesn't store all distances simultaneously, it produces them one at a time for the min() function to process.

The elegance of this solution lies in its simplicity - rather than using explicit loops and variables to track the minimum distance, it combines Python's functional programming features to solve the problem in a single, readable line of code.

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Example: nums = [1, 2, 3, 4, 3], target = 3, start = 0

Step 1: Enumerate the array We go through each element with its index:

• Index 0: value = 1
• Index 1: value = 2
• Index 2: value = 3 ✓ (matches target)
• Index 3: value = 4
• Index 4: value = 3 ✓ (matches target)

Step 2: Filter for target values We identify that the target value 3 appears at indices 2 and 4.

Step 3: Calculate distances from start For each matching index, calculate the distance from start = 0:

• Index 2: abs(2 - 0) = 2
• Index 4: abs(4 - 0) = 4

Step 4: Find the minimum distance Among the distances [2, 4], the minimum is 2.

Result: The minimum distance is 2.

Let's trace through one more example where the target appears on both sides of start:

Example: nums = [5, 3, 6, 3, 3], target = 3, start = 2

• Target 3 appears at indices: 1, 3, and 4
• Distances from start (index 2):
  • Index 1: abs(1 - 2) = 1 (target is to the left)
  • Index 3: abs(3 - 2) = 1 (target is to the right)
  • Index 4: abs(4 - 2) = 2 (target is further right)
• Minimum distance: 1

Notice how there's a tie (both indices 1 and 3 have distance 1). The solution correctly returns 1 as the minimum distance, regardless of which specific index achieves it.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums.

The code uses a generator expression with enumerate(nums) which iterates through all elements in the array once. For each element, it checks if the value equals the target (constant time operation) and if so, calculates the absolute difference abs(i - start) (also constant time). The min() function then finds the minimum value from all calculated distances. In the worst case, all elements could equal the target, requiring us to compute distances for all n elements. Therefore, the overall time complexity is O(n).

Space Complexity: O(1).

The generator expression (abs(i - start) for i, x in enumerate(nums) if x == target) does not create a list to store all distances at once. Instead, it generates values one at a time as needed by the min() function. The min() function only needs to keep track of the current minimum value as it iterates through the generator, using constant extra space. No additional data structures proportional to the input size are created, resulting in O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Empty Generator with min()

The most critical pitfall in this solution is assuming the generator expression will always produce at least one value. While the problem statement guarantees that the target exists in the array, if someone reuses this code without that guarantee, calling min() on an empty generator will raise a ValueError.

Problem Example:

nums = [1, 2, 3, 4, 5]
target = 6  # doesn't exist
start = 2
# This will raise: ValueError: min() arg is an empty sequence

Solution: Add a default value or handle the edge case explicitly:

def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
    distances = [abs(i - start) for i, x in enumerate(nums) if x == target]
    return min(distances) if distances else -1  # or float('inf') or None

2. Misunderstanding Distance Calculation

Developers might incorrectly calculate the distance without using absolute value, leading to negative distances being considered "minimum."

Problem Example:

# Incorrect: using (i - start) instead of abs(i - start)
return min(i - start for i, x in enumerate(nums) if x == target)
# If target is before start, this gives negative values

Solution: Always use abs(i - start) to ensure distances are positive.

3. Early Termination Optimization Missed

The current solution always scans the entire array. When the start index is near the beginning or end, we could optimize by expanding our search outward from the start position.

Problem Example:

nums = [1, 2, 3, 4, 5, 3, 7, 8, 9, 10, 11, 12, 13, 14, 15]
target = 3
start = 0  # We'll scan all 15 elements even though answer is at index 2

Optimized Solution:

def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
    n = len(nums)
    for distance in range(n):
        # Check position to the left
        if start - distance >= 0 and nums[start - distance] == target:
            return distance
        # Check position to the right
        if start + distance < n and nums[start + distance] == target:
            return distance
    return -1  # Should never reach here given the guarantee

This optimization stops as soon as it finds the first occurrence of the target, which is guaranteed to be at minimum distance due to the expanding search pattern.