1848. Minimum Distance to the Target Element

EasyArray
Leetcode Link

Problem Description

You are provided with an array of integers called nums. Your task is to find an index i where the value at that index (nums[i]) is the same as the target value provided. Additionally, you have a starting index start, and you want to find the i that is closest to start. This means you want to minimize the absolute difference between start and i (abs(i - start)). The final output should be the minimized absolute difference. It's important to note that it is confirmed that at least one instance of the target value exists in the nums array.

Intuition

The intuition behind the solution is to iterate over each element in the array and check if it matches the target value. If it matches, we calculate the absolute difference between the current index i and the start index. We are interested in the minimum such difference, so we keep an ongoing record of the minimum difference calculated so far. This process involves a linear scan of the array and comparison of each element against the target. As we are guaranteed that target exists in the array, we do not need to handle cases where the target is absent. The solution approach is straightforward because the problem does not require us to optimize for time complexity beyond the linear scan, given the nature of the problem.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which data structure is used to implement priority queue?

Solution Approach

The provided reference solution approach is a simple and direct method to solve the problem with time complexity O(n) and space complexity O(1), where n is the number of elements in nums.

Here are the steps implemented in the solution:

  1. Initialize a variable ans to hold the minimum distance found so far. It's initialized with inf (infinity), which is a placeholder for the largest possible value. This ensures that the first comparison will always replace inf with a valid distance.

  2. Iterate through the input list nums using a for loop. The enumerate function is used to get both the index i and the value x at each position in the list.

  3. For each element x and its corresponding index i, we check if x matches the target.

  4. If a match is found, calculate the absolute difference between i and the given start index: abs(i - start).

  5. Update ans to be the minimum of the current ans and the newly calculated absolute difference. This step is the heart of the solution, as it maintains the smallest distance encountered as the loop progresses through the array.

  6. After the loop has finished examining all elements, return the value of ans. At this point, ans contains the minimum absolute difference between the start index and an index i where nums[i] == target.

No additional data structures are needed, and pure iteration with basic comparisons are the only patterns used in this solution. This approach is the most optimal for this kind of problem where there isn't a pattern or structure that can be exploited to reduce the time complexity below O(n).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Assume we have the following parameters:

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

We want to find the index i where nums[i] is equal to the target value (3), and which is closest to the start index (5). Following the solution steps:

  1. We initialize ans to inf. At this point, ans would represent infinity and acts as a very high starting point for comparison.

  2. As we iterate over nums, we will compare each element with the target:

    Loop iterationix (value at nums[i])abs(i - start)ans
    1st045inf
    2nd1344 (since 4 < inf)
    3rd2234 (since 3 > 4)
    4th3524 (since 2 > 4)
    5th4311 (since 1 < 4)
    6th5501 (since 0 > 1)
    7th6111 (since 1 >= 1)
    8th7221 (since 2 > 1)

  3. We check each time if x == target. When we find a match, we calculate abs(i - start).

  4. If a match is found:

    • For i = 1, x = 3, which matches the target. We calculate abs(1 - 5) = 4 and update ans to 4.
    • For i = 4, x = 3 again. We calculate abs(4 - 5) = 1 and update ans to 1 since 1 is less than the current ans of 4.

  5. We continue the process until we have iterated through the entire array. The minimum value encountered in ans is the one that will remain.

  6. After the loop has finished, we have found that the closest index with the target value 3 relative to start 5 is index 4 with a minimum absolute difference of 1. Therefore, the final return value (the minimized absolute difference) is 1.

In this example, the closest index to start with the target value 3 was at index 4, which gave us the minimized absolute difference. This exemplifies the linear scan and comparison process, which results in O(n) time complexity and O(1) space complexity since no additional storage beyond a few variables is used.

Solution Implementation

1from typing import List
2
3class Solution:
4    def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
5        # Initialize answer with a large number (infinity)
6        min_distance = float('inf')  
7
8        # Iterate through the list, enumerating it to have index and value
9        for index, value in enumerate(nums):
10            # Check if the current value matches the target value
11            if value == target:
12                # Update min_distance with the smaller value between the current min_distance 
13                # and the absolute difference between current index and start index
14                min_distance = min(min_distance, abs(index - start))
15      
16        # Return the minimum distance found
17        return min_distance
18      
19# Example usage:
20# sol = Solution()
21# result = sol.getMinDistance([1, 2, 3, 4, 5], 5, 3)
22# print(result)  # Output will be 1, since the distance between index 3 and the closest 5 is 1.
23
1class Solution {
2    public int getMinDistance(int[] nums, int target, int start) {
3        // Get the length of the input array
4        int arrayLength = nums.length;
5        // Initialize the answer with the maximum possible value
6        int minimumDistance = arrayLength;
7      
8        // Iterate through the array to find the elements equal to the target
9        for (int i = 0; i < arrayLength; ++i) {
10            // Check if the current element equals the target
11            if (nums[i] == target) {
12                // Update the minimum distance if the current distance is smaller than the previously computed one
13                minimumDistance = Math.min(minimumDistance, Math.abs(i - start));
14            }
15        }
16        // Return the smallest distance found
17        return minimumDistance;
18    }
19}
20
1#include <vector>       // Required for using the vector container
2#include <algorithm>    // Required for 'min' function
3#include <cmath>        // Required for 'abs' function
4
5class Solution {
6public:
7    // Function to find the minimum distance to the target from the start index 
8    int getMinDistance(vector<int>& nums, int target, int start) {
9        int size = nums.size();   // Get the size of the input vector 'nums'
10        int minDistance = size;   // Initialize minimum distance with the maximum possible value (size of the vector)
11
12        // Loop through all elements in the nums vector
13        for (int i = 0; i < size; ++i) {
14            // Check if the current element is equal to the target
15            if (nums[i] == target) {
16                // Update the minimum distance found so far
17                minDistance = min(minDistance, abs(i - start));
18            }
19        }
20
21        // Return the minimum distance to the target from the start index
22        return minDistance;
23    }
24};
25
1import * as util from "util";   // TypeScript doesn't natively import min and abs, so we would typically use a utility library or implement our own.
2
3// Function to find the minimum distance to the target from the start index
4function getMinDistance(nums: number[], target: number, start: number): number {
5  const size: number = nums.length;   // Get the size of the input array 'nums'
6  let minDistance: number = size;     // Initialize minimum distance with the maximum possible value (size of the array)
7
8  // Loop through all elements in the nums array
9  for (let i = 0; i < size; ++i) {
10    // Check if the current element is equal to the target
11    if (nums[i] === target) {
12      // Update the minimum distance found so far using Math.min and Math.abs for minimum and absolute value respectively
13      minDistance = Math.min(minDistance, Math.abs(i - start));
14    }
15  }
16
17  // Return the minimum distance to the target from the start index
18  return minDistance;
19}
20
21// Example usage:
22// Uncomment the line below to test the function with an example input
23// console.log(getMinDistance([1, 2, 3, 4], 3, 2));
24
Not Sure What to Study? Take the 2-min Quiz：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the nums list. This is because the code iterates through each element of nums once to check if it is equal to target and, if so, calculates the distance from the start index. The min function, called for each element of the list, operates in constant time O(1); hence, it does not affect the overall linear complexity.

The space complexity of the code is O(1). This is because the space used does not grow with the size of the input list. The ans variable takes constant space, and there are no additional data structures used that scale with the input size.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫