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:

1
2
3

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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), where n is the length of the input array arr.
  • 🧺 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:

  1. Initialize Variables: Use variables to keep track of the latest positions of x and y in the array.
  2. Iterate through the Array: Traverse the array to find the positions of the elements x and y.
  3. Update Positions and Minimum Distance: Each time you encounter x or y, update their latest positions and calculate the distance if both elements have been seen.
  4. Return Minimum Distance: Return the minimum distance found between the two elements.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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)