Leetcode – Minimum Distance to the Target Element Solution

Spread the love

The “Minimum Distance to the Target Element” problem on Leetcode offers a dive into the realm of array manipulation and search algorithms. The problem may initially seem simple but presents opportunities to optimize solutions and appreciate algorithmic design’s nuances. In this article, we’ll explore the problem, its constraints, and multiple Python-based solutions, analyzing the trade-offs between them.

Problem Statement

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

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

Output: 1

Approach 1: Linear Search

The most straightforward approach is to scan through the array and keep track of the minimum distance to the target element.

Here’s the Python implementation:

def getMinDistance(nums, target, start):
    min_distance = float('inf')
    for i in range(len(nums)):
        if nums[i] == target:
            min_distance = min(min_distance, abs(i - start))
    return min_distance

Time Complexity

The time complexity for this approach is O(n), where n is the length of the array nums.

Space Complexity

The space complexity is O(1) as we are using only a constant amount of extra space.

Approach 2: Early Break

We can optimize the solution by breaking the loop as soon as we find the minimum distance to the target.

def getMinDistance(nums, target, start):
    for d in range(len(nums)):
        if start - d >= 0 and nums[start - d] == target:
            return d
        if start + d < len(nums) and nums[start + d] == target:
            return d

Time Complexity

The time complexity is potentially better than O(n) if the target element is close to the start index. However, in the worst-case scenario, it will still be O(n).

Space Complexity

The space complexity remains O(1).

Approach 3: Using Python’s Built-in index Function

Python offers a built-in index function to find an element’s index in a list. Although not recommended for this particular problem due to its linear time complexity, it can still provide a solution.

def getMinDistance(nums, target, start):
    indices = [i for i, x in enumerate(nums) if x == target]
    return min([abs(i - start) for i in indices])

Time Complexity

The time complexity for using Python’s index is O(n).

Space Complexity

The space complexity is O(k), where k is the number of occurrences of the target in nums.

Unit Testing

Whatever approach you choose, unit testing is essential. Here is how you could write tests for this function.

def test_getMinDistance():
    assert getMinDistance([1, 2, 3, 4, 5], 5, 3) == 1
    assert getMinDistance([1, 1], 1, 0) == 0
    assert getMinDistance([1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 1, 0) == 0
    print("All test cases pass")

test_getMinDistance()

Conclusion

The “Minimum Distance to the Target Element” problem serves as a good exercise for understanding basic array manipulation and algorithm optimization. Despite its apparent simplicity, the problem gives us an opportunity to explore various approaches, each with its own set of trade-offs. The key takeaway is that there’s always room for optimization, even in problems that initially seem straightforward.

Leave a Reply