Word Distance

Easy
0/40
Average time to solve is 15m
profile
Contributed by
11 upvotes
Asked in companies
AmazonSalesforceLinkedIn

Problem statement

You are given a document as an Array/List 'ARR' of words of length ‘N’. You have to perform Q queries. In each query, you are given two words. Your task is to find the smallest distance between these two words in a document and return it.

Distance between words is defined as the difference between their indexes.

For example:

ARR=[‘hot’, ‘a’, ‘b’, ‘dog’] and query = (‘hot’, ‘dog’) 

The answer, in this case, is 3 as the minimum distance between ‘hot’ and ‘dog’ in the given document is 3.

Note:

If any one of the words is not present in the document then your program must return ‘N’ which is the length of the document.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains two space-separated integers, ‘N’ and ‘Q’ respectively.

The second line of each test case contains all the space-separated words in the document ARR.

The next ‘Q’ lines of each test case contain ‘Q’ queries, as two, space-separated words.
Output Format: 
For each test case print ‘Q’ lines, i’th of which is the answer to i’th query.

Answer to each query is printed on a new line.
Note: 
You don’t need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N <= 10^4
1 <= Q <=100

Where, ‘N’ and ‘Q’, are the length of the ARR, number of queries, respectively. 

All the strings in ARR contain only lowercase English letters. 

Time Limit: 1 sec
Sample Input 1:
2
5 2
a b c d a   
a d
a z
4 1
cat rat hat bat
cat bat
Sample Output 1:
1
5
3
Explanation of Sample Input 1:
For the first test case, the minimum distance between “a” and “d” is 1, 
ARR[5] = “a”, ARR[4]= “d” , 5-4 = 1

For the second query answer is 5 as “z” is not present in the ARR.

For the only query of the second test, the case answer is 3 as the minimum distance between “cat” and “bat” is 3.
Sample Input 2:
2
2 3
a b
a b
a b
a b 
6 1
ab bb cd ra wf bb 
bb ra
Sample Output 2:
1
1
1
2
Hint

Can we iterate over the array for each query and keep a pointer at the last index of two words?

Approaches (2)
Brute Force

For each query, we will iterate over the entire document and keep two-pointer ‘PT1’ and ‘PT2’ for two words. If the current word of the document is equal to any of these two words we will update the answer and pointers.

 

The algorithm will be:

 

  • For each query:
    1. Create two pointers ‘PT1’, ‘PT2’ initialize to -1 create ‘ANS’ and initialize to ‘N’.
    2. For each word in ‘ARR’:
      • If the word is equal to the first word in the query:
        • Set ‘PT1’ to the current index.
      • If word equal to the second word in the query:
        • Set ‘PT2’ to the current index
      • If ‘PT1’ != -1 and ‘PT2’ !=-1
        • Set ANS to min( ‘ANS’, abs(‘PT2-PT1’) ).
    3. Print ‘ANS’
Time Complexity

O(N * Q), Where N, Q denotes the length of the array ARR and the number of queries.

 

We are iterating through each word for each query. Hence overall time complexity will be O(N*Q).

Space Complexity

O(1)

 

Constant space is used. 

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