I'm trying to find the minimum distance between 2 given elements of an array. for example, in the following array {1,2,3,4,5,6,7} the distance between elements 3,7 is 4. I've written a code that successfully calculates that distance, but if there are duplicates, it doesn't work. Below is what I've written so far. What am I missing? should I add any conditions? Also, it should be done at a complexity no greater than O(n).

public static int findMinDiff(int [] a, int x, int y) {
             
    //previous index and min distance
    int next = 0,curr = 0, min_dist = Integer.MAX_VALUE;
         
    for(int i=0 ; i<a.length ; i  )
    {
        if(a[i]==x)
        {
            curr = i; 
        }
        else if(a[i] == y){
            next = i;
        }
            
    }
    
    min_dist = Math.abs(curr - next);
    if(min_dist==Integer.MAX_VALUE)
        return -1;
     
    return min_dist;
}

CodePudding user response：

public static int findMinDiff(int [] a, int x, int y) {
    //previous index and min distance
    int next = -1,curr = -1, min_dist = Integer.MAX_VALUE;

    for(int i=0 ; i<a.length ; i  )
    {
        if(a[i]==x)
        {
            curr = i;
            if(next != -1) {
                min_dist = Math.min(min_dist, Math.abs(curr-next));
            }
        }
        else if(a[i] == y){
            next = i;
            if(curr != -1){
                min_dist = Math.min(min_dist, Math.abs(curr-next));
            }
        }

    }

    if(min_dist==Integer.MAX_VALUE)
        return -1;

    return min_dist;
}

This might help.

CodePudding user response：

If there are duplicate values in the array your algorithm does not work because it always remembers only the right-most x and y values that it encounters in the array and only calculates the distance between them in the end.

Even if the array is not sorted, you can still meet the O(n) requirement, by tracking 3 variables as you traverse the array:

1. the last encountered x index,
2. the last encountered y index
3. the shortest distance so far

Every time you encounter either an x value or and y value, update all 3 variables that you are tracking. Which means that you would calculate the distance of the newly found pair and compare it to the current shortest distance. If it is shorter, save it, otherwise ignore it.

Since the distance calculation and updating the values takes constant time, you still end with a O(n) time complexity when the end of the array is reached and the shortest distance variable will contain the shortest distance.

The key place in you algorithm would be here

        if(a[i]==x)
        {
            curr = i;
            // here if you found a complete pair, calculate the
            // distance and, if it is less than the current shortest
            // distance, update the shortest distance variable
        }
        else if(a[i] == y){
            next = i;
            // here if you found a complete pair, calculate the
            // distance and, if it is less than the current shortest
            // distance, update the shortest distance variable
        }

Also remove the old distance calculation min_dist = Math.abs(curr - next);