Shortest Word Distance II

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
12 upvotes
Asked in companies
AmazonFlipkart limited

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
8
coding ninjas help to crack product based companies
coding product
8
eat code sleep repeat eat code sleep repeat 
eat repeat
Sample Output 1:
5
1
Explanation for Sample Input 1:
In the first test case, there are 8 books on the bookshelf.
book1 = “coding”, book2 = “product”. The distance between book1 and book2 is 5. So, the answer is 5.
In the second test case, there are 8 books on the bookshelf. and there are 2 occurrences in every book.
book1 = “eat”, book2 = “repeat”.  book1 is present at indices 0 and 4. book2 is present at indices 3 and 7. The distances are 3, 7, 1, 4. The minimum of these is 1. So, the answer is 1.
Sample Input 2:
2
5
alpha beta gamma theta beta
theta beta
6
be cool whatever the situation is
situation cool
Sample Output 2:
1
3
Hint

Can you use two nested loops to find the minimum distance?

Approaches (2)
Brute Force

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.
Time Complexity

O((N^2)*M), where N is the number of books on the bookshelf, and M is the maximum length of a book present on the bookshelf.

 

As we are having two nested loops, each traversing the whole array and in each iteration, we are comparing the current book name with ‘book1’ or ‘book2’. Hence the time complexity is O((N^2)*M).


 

Space Complexity

O(1), as we are using constant extra space.

 

Code Solution
(100% EXP penalty)
Shortest Word Distance II
Full screen
Console