Minimum Distance to the Target Element solution and explanation
Google
9 more videos on this problem
Minimum Distance to the Target Element | Simple Explanation | Early Break | Leetcode 1848 | MIKcodestorywithMIK · 6:49 · 2K views
1848. Minimum Distance to the Target Element | Leetcode weekly problem | Ayushi RawatAyushi Rawat · 4:47 · 896 views
1848. Minimum Distance to the Target Element (Leetcode Easy)Programming Live with Larry · 2:20 · 347 views
1848. Minimum Distance to the Target Element | Leetcode Daily - PythonLeetcode Daily · 5:08 · 267 views
leetcode 1848 | Minimum Distance to the Target Element | Leetcode POTD | Easy explanation | DSACode With Vick · 7:10 · 175 views
Minimum Distance to the target element | leetcode solution of problem 1848TechFeline · 6:19 · 142 views
Minimum Distance to the Target Element | LeetCode 1848 - Pythonimpoldev · 3:19 · 104 views
LeetCode 1848 | Minimum Distance to the Target Element | C++ Solution ExplainedAtomicDevv · 3:43 · 95 views
Leetcode solving: 1848 Minimum Distance to the Target ElementMath Geeks · 3:38 · 87 views
LeetCode Daily 1848 | Minimum Distance to the Target Element | Easy SolutionThinkBeforeCode · 2:19 · 49 views
The problem
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 1:
Input: nums = [1,2,3,4,5], target = 5, start = 3 Output: 1 Explanation: nums[4] = 5 is the only value equal to target, so the answer is abs(4 - 3) = 1.
Example 2:
Input: nums = [1], target = 1, start = 0 Output: 0 Explanation: nums[0] = 1 is the only value equal to target, so the answer is abs(0 - 0) = 0.
Example 3:
Input: nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0 Output: 0 Explanation: Every value of nums is 1, but nums[0] minimizes abs(i - start), which is abs(0 - 0) = 0.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 1040 <= start < nums.lengthtargetis innums.
Approach overview
Problem Overview: You are given an integer array nums, a target value, and a start index. The task is to return the minimum absolute distance between start and any index i where nums[i] == target. The array may contain multiple occurrences of the target, so you must check all candidates and choose the smallest distance.
Approach 1: Linear Search from Start (Time: O(n), Space: O(1))
The simplest solution is a full scan of the array. Iterate through every index i from 0 to n-1. Whenever nums[i] equals the target, compute the distance using abs(i - start) and keep track of the minimum value seen so far. This approach relies on a straightforward traversal of the array and constant-time comparisons. Since every element is visited once, the time complexity is O(n), while memory usage stays O(1) because only a few variables are stored. This method is reliable and easy to implement in any language.
Approach 2: Bi-directional Search (Time: O(n) worst case, Space: O(1))
A more intuitive strategy is to start from the start index and expand outward in both directions. Check positions start, start-1, start+1, start-2, start+2, and so on until the target is found. The first match encountered automatically gives the minimum distance because the search expands in increasing distance order. This pattern resembles a two-sided pointer expansion similar to techniques used in two pointer problems. In the best case, the target is adjacent to start and the algorithm returns immediately. In the worst case, the scan reaches the ends of the array, resulting in O(n) time and O(1) space.
The bidirectional technique reduces unnecessary checks when the closest target lies near the starting position. However, its worst-case performance is still linear because the algorithm may need to inspect every element.
Recommended for interviews: The linear scan is usually the expected baseline solution. It clearly demonstrates understanding of array traversal and absolute distance calculation. The bi-directional expansion is a nice optimization idea and shows problem-solving intuition. In interviews, start with the linear approach, explain its O(n) complexity, then mention the bidirectional strategy as an improvement that can terminate earlier when the closest target is near the starting index.
Approach 1: Linear Search from Start
The simplest approach is to iterate through the entire array and check for each target occurrence. Calculate the absolute difference between the current index and the start index. Keep track of the minimum difference encountered and return that value.
def min_distance(nums, target, start):
min_distance = len(nums)
for i in range(len(nums)):
if nums[i] == target:
distance = abs(i - start)
min_distance = min(min_distance, distance)
return min_distance
nums = [1, 2, 3, 4, 5]
target = 5
start = 3
print(min_distance(nums, target, start))public class Main {
public static int minDistance(int[] nums, int target, int start) {
int minDistance = nums.length;
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;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
int target = 5, start = 3;
System.out.println(minDistance(nums, target, start));
}
}#include <iostream>
#include <vector>
#include <cmath>
int minDistance(const std::vector<int>& nums, int target, int start) {
int minDistance = nums.size();
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] == target) {
int distance = std::abs(i - start);
minDistance = std::min(minDistance, distance);
}
}
return minDistance;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5};
int target = 5, start = 3;
std::cout << minDistance(nums, target, start) << std::endl;
return 0;
}function minDistance(nums, target, start) {
let minDistance = nums.length;
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) {
let distance = Math.abs(i - start);
minDistance = Math.min(minDistance, distance);
}
}
return minDistance;
}
const nums = [1, 2, 3, 4, 5];
const target = 5;
const start = 3;
console.log(minDistance(nums, target, start));#include <stdio.h>
#include <stdlib.h>
int minDistance(int* nums, int numsSize, int target, int start) {
int minDistance = numsSize;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == target) {
int distance = abs(i - start);
if (distance < minDistance) {
minDistance = distance;
}
}
}
return minDistance;
}
int main() {
int nums[] = {1, 2, 3, 4, 5};
int target = 5, start = 3;
int result = minDistance(nums, 5, target, start);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public static int MinDistance(int[] nums, int target, int start) {
int minDistance = nums.Length;
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;
}
public static void Main() {
int[] nums = {1, 2, 3, 4, 5};
int target = 5, start = 3;
Console.WriteLine(MinDistance(nums, target, start));
}
}In this Python solution, we iterate over the list, and whenever we find the target, we compute its distance to the start index. The minimum of these distances is returned.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Bi-directional Search
This approach leverages the possibility of starting two pointers, one from the start index moving forward and the other moving backward, thereby potentially reducing the number of elements to check before finding the target. The method stops early if a zero-distance index is found, as it represents the minimum possible distance.
def min_distance(nums, target, start):
left = start
right = start
while left >= 0 or right < len(nums):
if left >= 0 and nums[left] == target:
return abs(left - start)
if right < len(nums) and nums[right] == target:
return abs(right - start)
left -= 1
right += 1
return -1 # Should not reach here
nums = [1, 2, 3, 4, 5]
target = 5
start = 3
print(min_distance(nums, target, start))public class Main {
public static int minDistance(int[] nums, int target, int start) {
int left = start;
int right = start;
while (left >= 0 || right < nums.length) {
if (left >= 0 && nums[left] == target) {
return Math.abs(left - start);
}
if (right < nums.length && nums[right] == target) {
return Math.abs(right - start);
}
left--;
right++;
}
return -1; // Should not reach here
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
int target = 5, start = 3;
System.out.println(minDistance(nums, target, start));
}
}#include <iostream>
#include <vector>
#include <cmath>
int minDistance(const std::vector<int>& nums, int target, int start) {
int left = start;
int right = start;
while (left >= 0 || right < nums.size()) {
if (left >= 0 && nums[left] == target) {
return std::abs(left - start);
}
if (right < nums.size() && nums[right] == target) {
return std::abs(right - start);
}
left--;
right++;
}
return -1; // Should not reach here
}
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5};
int target = 5, start = 3;
std::cout << minDistance(nums, target, start) << std::endl;
return 0;
}function minDistance(nums, target, start) {
let left = start;
let right = start;
while (left >= 0 || right < nums.length) {
if (left >= 0 && nums[left] === target) {
return Math.abs(left - start);
}
if (right < nums.length && nums[right] === target) {
return Math.abs(right - start);
}
left--;
right++;
}
return -1; // Should not reach here
}
const nums = [1, 2, 3, 4, 5];
const target = 5;
const start = 3;
console.log(minDistance(nums, target, start));#include <stdio.h>
#include <stdlib.h>
int minDistance(int* nums, int numsSize, int target, int start) {
int left = start;
int right = start;
while (left >= 0 || right < numsSize) {
if (left >= 0 && nums[left] == target) {
return abs(left - start);
}
if (right < numsSize && nums[right] == target) {
return abs(right - start);
}
left--;
right++;
}
return -1; // Should not reach here
}
int main() {
int nums[] = {1, 2, 3, 4, 5};
int target = 5, start = 3;
int result = minDistance(nums, 5, target, start);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public static int MinDistance(int[] nums, int target, int start) {
int left = start;
int right = start;
while (left >= 0 || right < nums.Length) {
if (left >= 0 && nums[left] == target) {
return Math.Abs(left - start);
}
if (right < nums.Length && nums[right] == target) {
return Math.Abs(right - start);
}
left--;
right++;
}
return -1;
}
public static void Main() {
int[] nums = {1, 2, 3, 4, 5};
int target = 5, start = 3;
Console.WriteLine(MinDistance(nums, target, start));
}
}In Python, the function iterates with two pointers from the start index, enabling a potentially earlier match find by examining elements on both sides.
Time Complexity: O(n/2) average, attempts to minimize checks compared to linear iteration.
Space Complexity: O(1)
Approach 3: Single Pass
Traverse the array, find all indices equal to target, then calculate |i - start|, and take the minimum value.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function getMinDistance(nums: number[], target: number, start: number): number {
let ans = Infinity;
for (let i = 0; i < nums.length; ++i) {
if (nums[i] === target) {
ans = Math.min(ans, Math.abs(i - start));
}
}
return ans;
}func getMinDistance(nums []int, target int, start int) int {
ans := 1 << 30
for i, x := range nums {
if t := abs(i - start); x == target && t < ans {
ans = t
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}impl Solution {
pub fn get_min_distance(nums: Vec<i32>, target: i32, start: i32) -> i32 {
nums.iter()
.enumerate()
.filter(|&(_, &x)| x == target)
.map(|(i, _)| ((i as i32) - start).abs())
.min()
.unwrap_or_default()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Linear Search from Start | Time Complexity: O(n) |
| Bi-directional Search | Time Complexity: O(n/2) average, attempts to minimize checks compared to linear iteration. |
| Single Pass | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Search from Start | O(n) | O(1) | General solution for any array; simplest and most common interview approach |
| Bi-directional Search | O(n) worst case | O(1) | Useful when the closest target is expected near the start index, allowing early termination |
Frequently asked questions
Is Minimum Distance to the Target Element easy or hard?
Minimum Distance to the Target Element is categorized as an Easy problem. It focuses on basic array traversal, condition checks, and computing absolute differences without requiring complex algorithms.
Minimum Distance to the Target Element Python/Java solution
Both Python and Java implementations follow the same logic: loop through the array, check if nums[i] equals the target, and track the minimum absolute difference from the start index. The algorithm runs in O(n) time and uses constant space.
How to solve Minimum Distance to the Target Element in O(n)?
Iterate through the array from index 0 to n-1. Whenever nums[i] equals the target, compute the distance using abs(i - start) and update the minimum value. After scanning all elements, return the smallest distance found.
What is the best approach for Minimum Distance to the Target Element?
The most common approach is a linear scan of the array. Iterate through all indices, check where nums[i] equals the target, and compute abs(i - start) to track the minimum distance. This runs in O(n) time and O(1) space and is typically the expected interview solution.
Is Minimum Distance to the Target Element asked at Google/Amazon/Meta?
This problem represents a common array traversal pattern often used in coding interviews. Variations that require computing minimum distance, scanning arrays, or expanding from a starting index frequently appear in interviews at large tech companies.
What data structure is used in Minimum Distance to the Target Element?
The problem primarily uses an array with simple iteration. No advanced data structures are required; the solution relies on sequential traversal and basic arithmetic operations.
What is the time complexity of Minimum Distance to the Target Element?
The standard solution runs in O(n) time because the algorithm may need to inspect every element in the array once. Space complexity is O(1) since only a few variables are used to track the current minimum distance.