Problem
Given an unsorted array and two elements, find the minimum distance between the elements in the array. The array may have duplicates.
Examples
Example 1:
Input: arr = [2, 5, 3, 5, 4, 4, 2, 3], x = 3, y = 2
Output: 4
Explanation: The minimum distance between the element 3 and 2 is found between the positions 6 and 7.
Solution
Method 1 - Brute force
Use two loops: The outer loop iterates through each element of arr[]
one at a time. The inner loop iterates over each element after the one selected by the outer loop. If the elements chosen by the outer and inner loops match the values of x
or y
, update the minimum distance if necessary.
Code
Java
public class Solution {
public int minDistance(int[] arr, int x, int y) {
int n = arr.length; // Get the length of the array
int minDist =
Integer.MAX_VALUE; // Initialize minimum distance with a large value
// Outer loop to pick every element one by one
for (int i = 0; i < n; i++) {
// Inner loop to pick every element after element picked by outer
// loop
for (int j = i + 1; j < n; j++) {
// Check if the pair (arr[i], arr[j]) is what we want
if ((arr[i] == x && arr[j] == y)
|| (arr[i] == y && arr[j] == x)) {
// Calculate the distance between the current pair
int dist = Math.abs(i - j);
// Update minDist if the current distance is smaller
if (dist < minDist) {
minDist = dist;
}
}
}
}
// If no valid distance is found, return -1
if (minDist == Integer.MAX_VALUE) {
return -1;
}
return minDist; // Return the minimum distance
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr = {3, 5, 4, 2, 6, 5, 6, 8, 3};
int x = 3;
int y = 6;
int result = solution.minDistance(arr, x, y);
System.out.println(
"The minimum distance is: " + result); // Output should be 4
}
}
Python
class Solution:
def minDistance(self, arr: List[int], x: int, y: int) -> int:
n = len(arr)
min_distance = float("inf")
last_pos_x = -1
last_pos_y = -1
# Traverse the array
for i in range(n):
if arr[i] == x:
last_pos_x = i
# If y has been seen, update the minimum distance
if last_pos_y != -1:
min_distance = min(
min_distance, abs(last_pos_x - last_pos_y)
)
if arr[i] == y:
last_pos_y = i
# If x has been seen, update the minimum distance
if last_pos_x != -1:
min_distance = min(
min_distance, abs(last_pos_y - last_pos_x)
)
# If no valid distance is found, return -1
return min_distance if min_distance != float("inf") else -1
# Example usage
sol = Solution()
arr = [3, 5, 4, 2, 6, 5, 6, 8, 3]
x = 3
y = 6
result = sol.minDistance(arr, x, y)
print("The minimum distance is:", result) # Output should be 4
Complexity
- ⏰ Time complexity:
O(n^2)
, wheren
is the length of the input arrayarr
. - 🧺 Space complexity:
O(1)
Method 2 - Keeping the indices of the element occurences
The algorithm iterates through the array to track the positions of the given elements x
and y
. It continually updates the minimum distance when both elements have been seen.
Here is the approach:
- Initialize Variables: Use variables to keep track of the latest positions of
x
andy
in the array. - Iterate through the Array: Traverse the array to find the positions of the elements
x
andy
. - Update Positions and Minimum Distance: Each time you encounter
x
ory
, update their latest positions and calculate the distance if both elements have been seen. - Return Minimum Distance: Return the minimum distance found between the two elements.
Code
Java
public class Solution {
public int minDistance(int[] arr, int x, int y) {
int n = arr.length;
int minDistance = Integer.MAX_VALUE;
int lastPosX = -1;
int lastPosY = -1;
// Traverse the array
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
lastPosX = i;
// If y has been seen, update the minimum distance
if (lastPosY != -1) {
minDistance =
Math.min(minDistance, Math.abs(lastPosX - lastPosY));
}
}
if (arr[i] == y) {
lastPosY = i;
// If x has been seen, update the minimum distance
if (lastPosX != -1) {
minDistance =
Math.min(minDistance, Math.abs(lastPosY - lastPosX));
}
}
}
// If no valid distance is found, return -1
if (minDistance == Integer.MAX_VALUE) {
return -1;
}
return minDistance;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr = {3, 5, 4, 2, 6, 5, 6, 8, 3};
int x = 3;
int y = 6;
int result = solution.minDistance(arr, x, y);
System.out.println(
"The minimum distance is: " + result); // Output should be 4
}
}
Python
class Solution:
def minDistance(self, arr: List[int], x: int, y: int) -> int:
n = len(arr)
min_distance = float("inf")
last_pos_x = -1
last_pos_y = -1
# Traverse the array
for i in range(n):
if arr[i] == x:
last_pos_x = i
# If y has been seen, update the minimum distance
if last_pos_y != -1:
min_distance = min(
min_distance, abs(last_pos_x - last_pos_y)
)
if arr[i] == y:
last_pos_y = i
# If x has been seen, update the minimum distance
if last_pos_x != -1:
min_distance = min(
min_distance, abs(last_pos_y - last_pos_x)
)
# If no valid distance is found, return -1
return min_distance if min_distance != float("inf") else -1
# Example usage
sol = Solution()
arr = [3, 5, 4, 2, 6, 5, 6, 8, 3]
x = 3
y = 6
result = sol.minDistance(arr, x, y)
print("The minimum distance is:", result) # Output should be 4
Complexity
- ⏰ Time complexity:
O(n)
- 🧺 Space complexity:
O(1)