/**
* Find distances between values in collections.
*/
object ArrayDistance {
/**
* Finds the minimum distance between two target values in an array.
*
* @param numbers The array to search.
* @param target1 The first target value.
* @param target2 The second target value.
*
* @return The minimum distance between the target values,
* or null if no valid pair exists.
*
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
fun findMinimumDistance(
numbers: IntArray,
target1: Int,
target2: Int
): Int? {
// Special case: both targets are the same value.
if (target1 == target2) {
return findMinimumDistanceBetweenDuplicates(
numbers,
target1
)
}
var lastSeenIndex: Int? = null
var minimumDistance: Int? = null
for ((currentIndex, currentValue) in numbers.withIndex()) {
// Ignore values that are not targets.
if (currentValue != target1 &&
currentValue != target2
) {
continue
}
/*
* If we previously saw one target value and
* the current value is the other target value,
* update the minimum distance.
*/
lastSeenIndex?.let { previousIndex ->
if (currentValue != numbers[previousIndex]) {
val distance = currentIndex - previousIndex
minimumDistance =
minimumDistance?.coerceAtMost(distance)
?: distance
}
}
// Remember the most recent occurrence.
lastSeenIndex = currentIndex
}
return minimumDistance
}
/**
* Finds the minimum distance between consecutive occurrences
* of the same value.
*/
private fun findMinimumDistanceBetweenDuplicates(
numbers: IntArray,
target: Int
): Int? {
var previousIndex: Int? = null
var minimumDistance: Int? = null
for ((currentIndex, currentValue) in numbers.withIndex()) {
if (currentValue != target) {
continue
}
previousIndex?.let { previous ->
val distance = currentIndex - previous
minimumDistance =
minimumDistance?.coerceAtMost(distance)
?: distance
}
previousIndex = currentIndex
}
return minimumDistance
}
}
fun main() {
val numbers = intArrayOf(2, 3, 7, 3, 3, 4, 8, 8, 8, 11, 9, 1, 3)
when (
val distance =
ArrayDistance.findMinimumDistance(
numbers,
3,
8
)
) {
null -> println("No valid pair found.")
else -> println("Minimum distance between 3 and 8: $distance")
}
}
/*
run:
Minimum distance between 3 and 8: 2
*/
