Find the minimum difference between the index of two given elements present in an array
Given an integer array nums and two integers x and y present in it, find the minimum absolute difference between indices of x and y in a single traversal of the array.
For example,
Input:
arr = { 1, 3, 5, 4, 8, 2, 4, 3, 6, 5 }
x = 3, y = 2
Output: 2
Explanation: Element 3 is present at index 1 and 7, and element 2 is present at index 5. Their minimum absolute difference is min(abs(1-5), abs(7-5)) = 2
Input:
arr = { 1, 3, 5, 4, 8, 2, 4, 3, 6, 5 }
x = 2, y = 5
Output: 3
Explanation: Element 2 is present at index 5, and element 5 is present at index 2 and 9. Their minimum absolute difference is min(abs(5-2), abs(5-9)) = 3
arr = { 1, 3, 5, 4, 8, 2, 4, 3, 6, 5 }
x = 3, y = 2
Output: 2
Explanation: Element 3 is present at index 1 and 7, and element 2 is present at index 5. Their minimum absolute difference is min(abs(1-5), abs(7-5)) = 2
Input:
arr = { 1, 3, 5, 4, 8, 2, 4, 3, 6, 5 }
x = 2, y = 5
Output: 3
Explanation: Element 2 is present at index 5, and element 5 is present at index 2 and 9. Their minimum absolute difference is min(abs(5-2), abs(5-9)) = 3
The idea is to traverse the array and keep track of the last occurrence of x and y.
- If the current element is
x, find the absolute difference between the current index ofxand the index of the last occurrence ofyand update the result if required. - If the current element is
y, find the absolute difference between the current index ofyand the index of the last occurrence ofxand update the result if required.
The algorithm can be implemented as follows in C, Java, and Python:
C
|
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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <stdio.h> #include <limits.h> #include <math.h> // Utility function to find a minimum of two integers int min (int x, int y) { return (x < y) ? x : y; } // Function to find the minimum difference between the index of two // elements `x` and `y` present in an array int findMinDifference(int arr[], int n, int x, int y) { // base case if (n <= 1) { return 0; } int x_index = n, y_index = n; int min_diff = INT_MAX; // traverse the given array for (int i = 0; i < n; i++) { // if the current element is `x` if (arr[i] == x) { // set `x_index` to the current index x_index = i; // if `y` is seen before, update the result if required if (y_index != n) { min_diff = min(min_diff, abs(x_index - y_index)); } } // if the current element is `y` if (arr[i] == y) { // set `y_index` to the current index y_index = i; // if `x` is seen before, update the result if required if (x_index != n) { min_diff = min(min_diff, abs(x_index - y_index)); } } } return min_diff; } int main(void) { int arr[] = { 1, 3, 5, 4, 8, 2, 4, 3, 6, 5 }; int x = 2, y = 5; int n = sizeof(arr) / sizeof(arr[0]); int diff = findMinDifference(arr, n, x, y); if (diff != INT_MAX) { printf("The minimum difference is %d", diff); } else { printf("Invalid input"); } return 0; } |
Output:
The minimum difference is 3
Java
|
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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
class Main { // Function to find the minimum difference between the index of two // elements `x` and `y` present in the array public static int findMinDifference(int[] A, int x, int y) { int n = A.length; // base case if (n <= 1) { return 0; } int x_index = n, y_index = n; int min_diff = Integer.MAX_VALUE; // traverse the given array for (int i = 0; i < n; i++) { // if the current element is `x` if (A[i] == x) { // set `x_index` to the current index x_index = i; // if `y` is seen before, update the result if required if (y_index != n) { min_diff = Integer.min(min_diff, Math.abs(x_index - y_index)); } } // if the current element is `y` if (A[i] == y) { // set `y_index` to the current index y_index = i; // if `x` is seen before, update the result if required if (x_index != n) { min_diff = Integer.min(min_diff, Math.abs(x_index - y_index)); } } } return min_diff; } public static void main(String[] args) { int[] A = { 1, 3, 5, 4, 8, 2, 4, 3, 6, 5 }; int x = 2, y = 5; int diff = findMinDifference(A, x, y); if (diff != Integer.MAX_VALUE) { System.out.print("The minimum difference is " + diff); } else { System.out.print("Invalid input"); } } } |
Output:
The minimum difference is 3
Python
|
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 46 47 48 49 50 51 |
import sys # Function to find the minimum difference between the index of two # elements `x` and `y` present in a list def findMinDifference(A, x, y): # base case if len(A) <= 1: return 0 x_index = y_index = len(A) min_diff = sys.maxsize # traverse the given list for i in range(len(A)): # if the current element is `x` if A[i] == x: # set `x_index` to the current index x_index = i # if `y` is seen before, update the result if required if y_index != len(A): min_diff = min(min_diff, abs(x_index - y_index)) # if the current element is `y` if A[i] == y: # set `y_index` to the current index y_index = i # if `x` is seen before, update the result if required if x_index != len(A): min_diff = min(min_diff, abs(x_index - y_index)) return min_diff if __name__ == '__main__': A = [1, 3, 5, 4, 8, 2, 4, 3, 6, 5] x = 2 y = 5 diff = findMinDifference(A, x, y) if diff != sys.maxsize: print("The minimum difference is", diff) else: print("Invalid input") |
Output:
The minimum difference is 3
The time complexity of the above solution is O(n) and doesn’t require any extra space, where n is the size of the input.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)