Minimum Distance to the Target Element — Problem & Solution
Minimum Distance to the Target Element solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Minimum Distance to the Target Element is an easy coding problem on arrays, asked in Amazon and Infosys interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums, an integer target and an integer start, find the index i such that nums[i] == target and |i - start| is as small as possible.
Return that minimum |i - start|. At least one occurrence of target is guaranteed.
Example 1
Input: nums = [1,2,3,4,5], target = 5, start = 3
Output: 1
Explanation: 5 sits at index 4, and |4 - 3| = 1.
Example 2
Input: nums = [1], target = 1, start = 0
Output: 0
Example 3
Input: nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0
Output: 0
Explanation: Index 0 already holds the target.
Constraints
1 <= nums.length <= 10001 <= nums[i] <= 100000 <= start < nums.lengthtarget appears at least once in nums.
Hints for Minimum Distance to the Target Element
Hint 1
The array is not sorted, so binary search does not apply.
Hint 2
A single scan comparing each matching index against
startis enough at these limits.Hint 3
Alternatively expand outward from
startand stop at the first hit.
How to solve Minimum Distance to the Target Element
Every occurrence of target is a candidate; the answer is the smallest absolute index distance among them.
Approach
- Scan the array once.
- Whenever
nums[i] == target, compute|i - start|and keep the minimum seen. - Return that minimum.
Why it works
The problem guarantees at least one occurrence, so the minimum is well defined, and scanning considers every candidate exactly once.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Returning on the first match found while scanning left to right gives the leftmost occurrence, not the nearest one.
- The outward-expansion variant must check both
start - dandstart + dat each step and guard both against going out of bounds.
Reference solution
Python
from typing import List
def getMinDistance(nums: List[int], target: int, start: int) -> int:
best = -1
for i, x in enumerate(nums):
if x == target:
d = abs(i - start)
if best == -1 or d < best:
best = d
return bestJava
public static int getMinDistance(int[] nums, int target, int start) {
int best = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
int d = Math.abs(i - start);
if (best == -1 || d < best) best = d;
}
}
return best;
}C++
int getMinDistance(vector<int>& nums, int target, int start) {
int best = -1;
for (int i = 0; i < (int) nums.size(); i++) {
if (nums[i] == target) {
int d = abs(i - start);
if (best == -1 || d < best) best = d;
}
}
return best;
}JavaScript
var getMinDistance = function(nums, target, start) {
let best = -1;
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) {
const d = Math.abs(i - start);
if (best === -1 || d < best) best = d;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays