algoadvance

Leetcode 1848. Minimum Distance to the Target Element

Problem Statement

You are given an integer array nums (0-indexed) and two integers target and start. The array contains positive integers only. Your task is to find the minimum distance between the start index and any index i such that nums[i] == target.

The distance between two indices i and j is abs(i - j) (the absolute difference).

Example

Input: nums = [1,2,3,4,5], target = 5, start = 3
Output: 1
Explanation: The target is at index 4. The distance between 3 and 4 is 1.

Clarifying Questions

1. Can start be out of bounds?
   • No, start is always a valid index within nums.
2. Can there be multiple targets in the array?
   • Yes, your goal is to find the minimum distance to any occurrence of the target.
3. What should be returned if target is not present in the array?
   • The problem guarantees that the target will be in the array at least once.

Strategy

We iterate through the array, checking each element. If the element matches the target, we calculate the distance from the start index and keep track of the minimum distance encountered. This ensures we only go through the array once, achieving an efficient solution.

Code

#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>

int getMinDistance(std::vector<int>& nums, int target, int start) {
    int minDistance = INT_MAX; // Use a large number to initialize minimum distance
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] == target) {
            minDistance = std::min(minDistance, std::abs(i - start));
        }
    }
    return minDistance;
}

Time Complexity

• The time complexity of this solution is O(n), where n is the number of elements in the array nums. We need to iterate through the entire array in the worst case.
• The space complexity is O(1), as we are using a constant amount of extra space regardless of the input size.

This approach ensures that we efficiently find the minimum distance to the target element in a single pass through the array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?