Last Updated: 10 Apr, 2021
Shortest Word Distance II
Moderate
Asked in companies
You have a bookshelf in the form of an array ‘arr’ in which names of the books(single word name) are given. You are also given names of two books, ‘book1’ and ‘book2’. You are supposed to find the minimum distance between ‘book1’ and ‘book2’.
Distance between two books is defined as the absolute difference between the indices of the books i.e for two books at index 'i' and 'j' the distance is equal to |i-j|.
Note:
1. There may be multiple occurrences of any book.
2. book1 and book2 are present on the bookshelf.
3. The name of the books is in lower-case.
4. book1 is not equal to book2.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.
The first line contains integer ‘N’, which denotes the number of books on the bookshelf.
The second line contains the names of N books in order.
The third line contains 2 words, the name of ‘book1’, and ‘book2’.
Output Format:
For each test case, print the minimum distance between ‘book1’, and ‘book2’.
Print the output of each test case in a separate line.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints:
1<= T <= 50
2 <= N <= 10^4
1 <= arr[i].length <= 10^4
All strings consist of lowercase letters only.
Where ’T’ is the number of test cases, and N denotes the number of elements in the array ‘arr’, arr[i] denotes the element at index ‘i’.
Time Limit: 1 sec
Approaches
The idea is to traverse over all the elements in the array ‘arr’ in two nested loops. Whenever we get a ‘book1’ and ‘book2’, take the minimum of answer and the current distance.
Algorithm:
- Initialize two integers ‘answer’ to the maximum integer value, and ‘n’ to the size of the array ‘arr’.
- Iterate from i = 0 to n:
- If arr[i] is not equal to book1 then continue.
- Iterate from j = 0 to n:
- If arr[j] is equal to book2, update ‘answer’ to the minimum of ‘answer’ and the absolute value of (i-j).
- Return ‘answer’ as the final answer.
The idea is to get all the indices where ‘book1’ and ‘book2’ are present and store the indices in an array. Both the arrays will already be sorted as we found the indices by iterating over the array. Then we will use the two-pointer approach to find the minimum distance between ‘book1’ and ‘book2’.
Algorithm:
- Declare two arrays, ‘indicesbook1’ and ‘indicesbook2’ that store the indices in which book1 and book2 are present, respectively.
- Initialize two integers ‘answer’ to the maximum integer value, and ‘n’ to the size of the array ‘arr’.
- Iterate over the array ‘arr’:
- If the name of the current book is the same as ‘book1’, push the current index into the array ‘indicesbook1’.
- If the name of the current book is the same as ‘book2’, push the current index into the array ‘indicesbook2’.
- Initialize two pointers, ‘i’ and ‘j’, which point to the beginning of both the arrays, respectively.
- Execute a while loop with the condition i is less than the size of the array ‘indicesbook1’ and j is less than the size of the array ‘indicesbook2’:
- Update ‘answer’ as the minimum of ‘answer’ and an absolute value of (i-j).
- If j is greater than i, increment i by 1.
- Otherwise, increment j by 1.
- When it comes out of the loop, then return ‘answer’ as the final answer.