algoadvance

Leetcode 1848. Minimum Distance to the Target Element

Problem Statement

Leetcode problem 1848: “Minimum Distance to the Target Element”

Given an integer array nums and two integers target and start, find the minimum distance between start and any position i such that nums[i] == target.

The distance between two indices i and j is |i - j|, where || represents the absolute value function.

Return the minimum distance. If there is no such i, return -1.

Clarifying Questions

1. Q: What are the constraints for the length of the array nums?
   • A: Typically in Leetcode problems, the length of the array can be up to 10^5.
2. Q: What are the constraints for the values within the array?
   • A: The values in the array and the target can range from -1000 to 1000.
3. Q: What should be the output if no elements match the target?
   • A: In such case, return -1.
4. Q: Can start be out of the bounds of the array?
   • A: No, start is guaranteed to be within the bounds of the array.

Strategy

To solve this problem, we need to iterate through the array and look for all occurrences of target. For each occurrence, we’ll calculate the distance to start and keep track of the minimum distance found.

1. Initialize a variable minDistance to Integer.MAX_VALUE.
2. Loop through the array nums:
   • If nums[i] equals target, calculate the distance |i - start|.
   • Update minDistance if the new calculated distance is smaller.
3. If minDistance remains Integer.MAX_VALUE, return -1 (indicating no target was found).
4. Otherwise, return minDistance.

Code

public class Solution {
    public int getMinDistance(int[] nums, int target, int start) {
        int minDistance = Integer.MAX_VALUE;
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                int distance = Math.abs(i - start);
                minDistance = Math.min(minDistance, distance);
            }
        }
        
        return minDistance == Integer.MAX_VALUE ? -1 : minDistance;
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the array nums, because we are making a single pass over the array.
• Space Complexity: O(1), since we only use a fixed amount of additional space for storing variables like minDistance and distance.

This solution is efficient and conforms to Leetcode’s typical constraints.

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?