Problem
Given an integer array with repeated elements, and 2 numbers num1 and num2, find the shortest distance of the 2 numbers in the array.
Solution
brutal force solution need 2 loops, one loop to find num1's position, another loop to find num2's position. The time cost is O(N^2)
We did lots of wasted traversal, because we should remember the lastPos1 of num1 and lastPos2 of num2, only these 2 numbers will gonna to change the shortest distance.
public class MinDistance {
public static int minDistance(int[] arr, int num1, int num2) {
int lastPos1 = -1;
int lastPos2 = -1;
int minDist = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++) {
if(arr[i] == num1) {
lastPos1 = i;
if(lastPos2 > 0) {
minDist = Math.min(minDist, lastPos1 - lastPos2);
}
}
if(arr[i] == num2) {
lastPos2 = i;
if(lastPos1 > 0) {
minDist = Math.min(minDist, lastPos2 - lastPos1);
}
}
}
return minDist;
}
public static void main(String...args) {
int[] arr = new int[]{1, 3, 5, 6, 4, 2, 1, 5, 6, 7, 2, 5, 6, 2, 1, 4, 7};
System.out.println(minDistance(arr, 1, 7));
}
}
The time complexity is O(N) and space complexity is O(1).
