object ArrayDistance:
/**
* Finds the minimum distance between two target values in a sequence.
*
* @param numbers the input sequence
* @param target1 the first target value
* @param target2 the second target value
* @return the minimum distance between the targets,
* or None if no valid pair exists
*
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
def findMinimumDistance(
numbers: Seq[Int],
target1: Int,
target2: Int
): Option[Int] =
// Special case: both targets are the same value.
if target1 == target2 then
return findMinimumDistanceBetweenDuplicates(
numbers,
target1
)
var lastSeenIndex: Option[Int] = None
var minimumDistance: Option[Int] = None
for ((value, index) <- numbers.zipWithIndex) do
// Ignore values that are not targets.
if value == target1 || value == target2 then
/*
* If we previously saw one target value and
* the current value is the other target value,
* update the minimum distance.
*/
lastSeenIndex.foreach { previousIndex =>
if value != numbers(previousIndex) then
val distance = index - previousIndex
minimumDistance = Some(
minimumDistance.fold(distance)(
_.min(distance)
)
)
}
// Remember the most recent occurrence.
lastSeenIndex = Some(index)
minimumDistance
/**
* Finds the minimum distance between consecutive
* occurrences of the same value.
*
* @param numbers the input sequence
* @param target the value to search for
* @return the minimum distance between occurrences,
* or None if fewer than two occurrences exist
*/
private def findMinimumDistanceBetweenDuplicates(
numbers: Seq[Int],
target: Int
): Option[Int] =
var previousIndex: Option[Int] = None
var minimumDistance: Option[Int] = None
for ((value, index) <- numbers.zipWithIndex) do
if value == target then
previousIndex.foreach { previous =>
val distance = index - previous
minimumDistance = Some(
minimumDistance.fold(distance)(
_.min(distance)
)
)
}
previousIndex = Some(index)
minimumDistance
@main
def runDemo(): Unit =
val numbers = Seq(2, 3, 7, 3, 3, 4, 8, 8, 8, 11, 9, 1, 3)
ArrayDistance
.findMinimumDistance(numbers, 3, 8) match
case Some(distance) =>
println(
s"Minimum distance between 3 and 8: $distance"
)
case None =>
println("No valid pair found.")
/*
run:
Minimum distance between 3 and 8: 2
*/
