02. Minimum Distance Between Two Numbers

The problem can be found at the following link: Question Link

My Approach

A simple and straightforward question, to find the minimum distance between two numbers, x and y, in an array,

• I traverse the array once. I maintain two variables, lastX and lastY, which represent the most recent positions of x and y in the array.

• I also maintain a variable out to store the minimum distance found so far. As I traverse the array, I update lastX and lastY whenever I encounter x or y. If both lastX and lastY have been updated, I calculate the distance and update out accordingly.

• Finally, I return out, which represents the minimum distance between x and y. If out remains equal to INT_MAX, it means one of the numbers was not found in the array, and I return -1.

Time and Auxiliary Space Complexity

• Time Complexity: O(n), where n is the number of elements in the array.

• Auxiliary Space Complexity: O(1), as we are using a constant amount of additional space.

Code (C++)

class Solution {
public:
    int minDist(int a[], int n, int x, int y) {
        int lastX, lastY, out;
        lastX = lastY = -1;
        out = INT_MAX;
        
        for(int i = 0; i < n; ++i) {
            if(a[i] == x)
                lastX = i;
            if(a[i] == y)
                lastY = i;
            
            if(lastX != -1 && lastY != -1)
                out = min(out, abs(lastX - lastY));
        }
        return out == INT_MAX ? -1 : out;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.