Find minimum difference between index of two given elements present in the array

Given two integers, find minimum difference between their index in a given array in linear time and single traversal of the array.


 

For example,


Input:
arr = { 1, 3, 5, 4, 8, 2, 4, 3, 6, 5 }
x = 3, y = 2

Output: Minimum difference between index is 2
 

Input:
arr = { 1, 3, 5, 4, 8, 2, 4, 3, 6, 5 }
x = 2, y = 5

Output: Minimum difference between index is 3

 
The idea is to traverse the array and keep track of last occurrence of x and y.

  1. If element x is encountered, we find the absolute difference between current index of x and index of last occurrence of y and update the result if required.
  2.  

  3. If element y is encountered, we find the absolute difference between current index of y and index of last occurrence of x and update the result if required.

 

C

Download   Run Code

Output:

Minimum difference is 3

Java

Download   Run Code

Output:

Minimum difference is 3

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of