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 ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

avatar
  Subscribe  
Notify of