LeetCode 1848 - Minimum Distance to the Target Element

LeetCode Problem 1848

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem gives us an integer array nums, a value called target, and an index called start. We need to find an index i where nums[i] == target and the distance between i and start is as small as possible.

The distance is measured using the absolute difference:

$|i-start|$

This means we only care about how far apart the indices are, regardless of direction. For example, if start = 3, then indices 2 and 4 are both distance 1 away.

The input array is 0-indexed, which means the first element is at index 0, the second at index 1, and so on.

The task is not asking us to return the index itself. Instead, we return the minimum distance between start and any occurrence of target.

The constraints are small:

• 1 <= nums.length <= 1000
• target is guaranteed to exist in the array

Because the array size is at most 1000, even a straightforward scan through the array is efficient enough. We do not need advanced data structures or optimization techniques.

Several edge cases are important:

• The target may appear exactly at start, which means the answer is 0.
• The target may appear multiple times, so we must choose the closest occurrence.
• The array may contain only one element.
• The closest target may appear either before or after start.
• Since the problem guarantees that target exists, we never need to handle the case where no valid answer exists.

Approaches

Brute Force Approach

The most direct solution is to examine every element in the array.

For each index i:

1. Check whether nums[i] == target.
2. If it does, compute the distance abs(i - start).
3. Keep track of the minimum distance seen so far.

At the end of the scan, the stored minimum distance is the answer.

This approach is correct because it evaluates every possible valid index where the target appears. Since we compare all candidate distances, the smallest one found must be the true minimum.

Although this is called a brute-force solution, it is completely acceptable here because the array size is small. The algorithm only performs a single linear scan.

Key Insight for the Optimal Approach

The important observation is that we do not need to search for combinations, paths, or complex relationships. The problem only asks for the minimum distance to a matching value.

Because every valid candidate can be evaluated independently, a single pass through the array is enough. While scanning:

• Every time we encounter target, we compute its distance from start.
• We continuously update the minimum distance.

No additional data structures are necessary because we only need one running minimum.

In practice, the brute-force and optimal approaches are essentially the same here, because a linear scan is already optimal for this problem.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Checks every element and computes distances
Optimal	O(n)	O(1)	Single-pass linear scan with running minimum

Algorithm Walkthrough

1. Initialize a variable called minimum_distance with a very large value.

This variable stores the smallest distance found so far. We start with a large number so that the first valid target occurrence will replace it. 2. Iterate through the array using both index and value.

We need the index because distance depends on positions, not values. 3. For each element, check whether it equals target.

Only indices containing the target are relevant. 4. If the current element equals target, compute the absolute distance from start.

$|i-start|$

This gives the distance between the current target index and the starting index. 5. Compare the computed distance with minimum_distance.

If the new distance is smaller, update minimum_distance. 6. Continue scanning until the end of the array.

This guarantees that every possible target occurrence has been considered. 7. Return minimum_distance.

After processing all elements, it contains the smallest possible distance.

Why it works

The algorithm works because it examines every index where nums[i] == target. For each valid index, it computes the exact distance from start. Since the algorithm keeps the smallest distance encountered during the scan, the final result must be the minimum possible distance among all valid target positions.

Python Solution

from typing import List

class Solution:
    def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
        minimum_distance = float("inf")

        for index, value in enumerate(nums):
            if value == target:
                distance = abs(index - start)
                minimum_distance = min(minimum_distance, distance)

        return minimum_distance

The implementation begins by initializing minimum_distance to infinity. This ensures that any real distance found in the array will be smaller.

The enumerate function is used so we can access both the index and value during iteration. Whenever the current value equals target, the algorithm computes the absolute distance between the current index and start.

The built-in min function updates the running minimum efficiently.

Finally, after the loop completes, the function returns the smallest distance discovered during the scan.

Go Solution

import "math"

func getMinDistance(nums []int, target int, start int) int {
    minimumDistance := math.MaxInt32

    for index, value := range nums {
        if value == target {
            distance := index - start

            if distance < 0 {
                distance = -distance
            }

            if distance < minimumDistance {
                minimumDistance = distance
            }
        }
    }

    return minimumDistance
}

The Go implementation follows the same logic as the Python version.

One small difference is that Go does not provide a built-in generic abs function for integers, so we manually convert negative distances into positive values.

The solution uses math.MaxInt32 as the initial large value for minimumDistance.

Since the problem constraints are small, integer overflow is not a concern here.

Worked Examples

Example 1

Input: nums = [1,2,3,4,5], target = 5, start = 3

We scan through the array looking for 5.

Index	Value	Is Target?	Distance abs(index - start)	Minimum Distance
0	1	No	-	inf
1	2	No	-	inf
2	3	No	-	inf
3	4	No	-	inf
4	5	Yes	1	1

Final answer:

1

Example 2

Input: nums = [1], target = 1, start = 0

Index	Value	Is Target?	Distance	Minimum Distance
0	1	Yes	0	0

Final answer:

0

Example 3

Input: nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0

Index	Value	Distance	Minimum Distance
0	1	0	0
1	1	1	0
2	1	2	0
3	1	3	0
4	1	4	0
5	1	5	0
6	1	6	0
7	1	7	0
8	1	8	0
9	1	9	0

The minimum distance remains 0 because the target already exists at the starting index.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The array is scanned once
Space	O(1)	Only a few variables are used

The algorithm performs a single pass through the array. Each element is processed exactly once, so the running time grows linearly with the size of the array.

The solution uses constant extra memory because it only stores a few integer variables regardless of input size.

Test Cases

from typing import List

class Solution:
    def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
        minimum_distance = float("inf")

        for index, value in enumerate(nums):
            if value == target:
                minimum_distance = min(minimum_distance, abs(index - start))

        return minimum_distance

solution = Solution()

assert solution.getMinDistance([1, 2, 3, 4, 5], 5, 3) == 1  # target after start
assert solution.getMinDistance([1], 1, 0) == 0  # single element array
assert solution.getMinDistance([1,1,1,1,1,1,1,1,1,1], 1, 0) == 0  # many targets

assert solution.getMinDistance([5, 2, 3, 4], 5, 3) == 3  # target before start
assert solution.getMinDistance([1, 2, 3, 2, 1], 2, 2) == 1  # multiple target occurrences
assert solution.getMinDistance([7, 7, 7], 7, 1) == 0  # target exactly at start
assert solution.getMinDistance([4, 5, 6, 5, 4], 5, 0) == 1  # closest target near beginning
assert solution.getMinDistance([4, 5, 6, 5, 4], 5, 4) == 1  # closest target near end
assert solution.getMinDistance([8, 9, 10, 11, 8], 8, 2) == 2  # equal distance candidates
assert solution.getMinDistance([3, 2, 1], 1, 2) == 0  # target at last index and start

Test	Why
[1,2,3,4,5], target=5, start=3	Standard example with target after start
[1], target=1, start=0	Smallest valid input
All elements equal to target	Ensures minimum remains zero
Target before start	Verifies left-side distance handling
Multiple target occurrences	Ensures closest occurrence is chosen
Target exactly at start	Validates zero-distance case
Closest target near beginning	Tests lower indices
Closest target near end	Tests higher indices
Equal distance candidates	Ensures minimum logic works correctly
Target at last index	Boundary index validation

Edge Cases

One important edge case occurs when the target is already at the starting index. In this situation, the correct answer is immediately 0 because the distance between an index and itself is zero. A buggy implementation might continue searching unnecessarily or fail to recognize that zero is already the smallest possible answer. This implementation handles the case naturally because abs(start - start) evaluates to 0, and the running minimum becomes 0.

Another important case is when the target appears multiple times throughout the array. A naive implementation might incorrectly return the first occurrence instead of the closest occurrence. The solution avoids this issue by scanning the entire array and updating the minimum distance every time a target is found.

A third edge case involves very small arrays, especially arrays of length 1. In such cases, the only element must also be the target because the problem guarantees the target exists. The implementation works correctly because the loop still processes the single element normally and computes a distance of 0.

A final edge case is when the closest target appears before the starting index instead of after it. Without absolute value handling, the distance could become negative and produce incorrect results. The use of abs(index - start) guarantees that distances are always treated correctly regardless of direction.