Abstract / Summary

Find the shortest distance from a starting index to the first occurrence of a target value in a list.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 64% (200k+ submissions).

Typical patterns to solve this problem:

• Array

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a method that determines the smallest number of steps required to reach an element equal to a given target value starting from a specified index start within a list nums. The algorithm walks through the list once, tracks the position of the closest matching element, and finally computes the absolute distance between that position and the starting index.

Initialization

The method begins by creating a variable pos and assigning it the value +inf. This sentinel value represents an undefined position and ensures that any legitimate index encountered later will be considered closer.

pos = +inf

Single-Pass Scan

A for loop enumerates the list, yielding both the current index i and the element n. Enumerating eliminates the need for a separate counter and keeps the code concise.

for i, n in enumerate(nums):

Inside the loop, the code checks whether the current element matches the target. This conditional gate isolates the logic to only those indices that are relevant for distance calculation.

if n == target:

Distance Comparison

When a matching element is found, the algorithm computes two distances:

• old - the distance from the previously recorded position pos to start.
• new - the distance from the current index i to start.

Both distances are obtained using the built-in abs function, which yields a non-negative integer representing the number of steps.

old = abs(pos - start)
new = abs(i - start)

The next step is a direct comparison between new and old. If the newly discovered distance is smaller, the algorithm updates pos to the current index i. This conditional replacement guarantees that pos always holds the index of the closest matching element seen so far.

if new < old:
    pos = i

Final Result

After the loop finishes, the method returns the absolute difference between the stored position pos and the starting index start. Because pos holds the index of the nearest target occurrence, this final expression yields the minimal distance required to reach a target element.

return abs(pos - start)

Edge Cases Handled

The code implicitly addresses several boundary conditions:

• When the target appears at the start index, the distance calculation yields zero, and the method returns 0.
• If the list contains multiple occurrences of target, the comparison logic ensures that only the index with the smallest absolute distance to start is retained.
• In the scenario where target does not exist in nums, the sentinel value +inf remains unchanged. The final abs(pos - start) then evaluates to an infinite distance, signaling the absence of a reachable target.

Performance Optimizations

The implementation achieves efficiency through a few deliberate choices:

• A single traversal of nums avoids the overhead of multiple passes or auxiliary data structures.
• Using enumerate eliminates the need for manual index management, reducing the amount of code executed per iteration.
• The distance comparison updates pos only when a strictly better candidate is found, preventing unnecessary assignments.
• The reliance on the built-in abs function leverages highly optimized native operations for absolute value computation.

These characteristics collectively produce a lean solution that scales linearly with the size of the input list while maintaining minimal memory usage.

Imagine there is a long row of numbered toy boxes lined up on the floor. Each box has a number written on it. You are standing at one of these boxes, which is your starting spot. There is a special treasure hidden inside some of these boxes, and that treasure is the target number.

The goal is to find the treasure box that is closest to where you are standing. You start by looking at every single box in the line, one by one, from the very beginning to the very end. Whenever you find a box that has the treasure inside, you stop and think. You check how far away that treasure box is from where you are standing.

If you have already found a different treasure box earlier, you compare the distance of the new one to the distance of the one you found before. If the new one is closer to your feet, you decide that this new box is the best one to remember for now. You keep doing this for every treasure box until you run out of boxes to check. After you have looked at all of them, the box you remembered is the one that is the shortest distance away from your starting spot.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java				Go	Rust	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim							C
	everthis			JS
	fartem					Ruby
	fsq	C++
	haoel	C++
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM						C#
	trung-hn		Python
	varunu28				Java
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality