Sparse Search

Easy

0/40

Average time to solve is 20m

6 upvotes

Asked in companies

Problem statement

You are given a sorted array of strings say ‘ARR’ and provided with another string say ‘K’. Your task is to find the position of ‘K’ in ‘ARR’.

Note :

‘ARR’ can also contain empty strings.
You will return -1 if ‘K’ does not exist in ‘ARR’.

For example :

‘ARR’ = [ “code”, “hi”, “”, “”,  “studio”, “”, “to”, “welcome” ] and ‘K’ = “hi”.
 As we can see ‘K’ is present on index 1 in ‘ARR’.
 So we will return 1.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains a single integer T, representing the number of test cases.
Then the T test cases follow.

The first line of each test case contains an integer ‘N’ representing the size of ‘ARR’ and a string representing ‘K’.

The second line of each test case contains ‘N’ space-separated strings.

Output format :

For every test case, print a single integer representing the location of ‘K’ in ‘ARR’, if ‘K’ is not present in ‘ARR’ then print -1.

The output of each test case is printed in a separate line.

Note :

You don’t have to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1<= T <=100
1<= ‘N’ <=10^4
1<= |‘K’| <= 20

 Time limit: 1 second

Sample input 1 :

1
8 hello
x and i hn jo me remember teach

Sample output 1 :

-1

Explanation For Sample Input 1 :

We can see ’ that “hello” does not exist in the given ‘ARR’ so we will return -1.

Sample input 2 :

2
6 way
failed i my to success way
4 really
qwert qaswe wasder zsxdcf

Sample output 2 :

5
-1

Hint 1

Hint 2

Match each string of ‘ARR’ with ‘K’.

Approaches (2)

Approach 1

Approach 2

Brute Force

The idea is very simple as we just need to find the position of ‘K’ in ‘ARR’. So we will scan ‘ARR’ from left to right and match each string with ‘K’, If we find a match simply return the index else keep on iterating till the end of ‘ARR’.

Iterate over ‘ARR’ for 0 <= i < ‘N’ and do :
- If ‘ARR[i]’ is equal to ‘K’ return i.
Return -1 as we can not find ‘K’.

Time Complexity

O(N), where N is the size of the given list/array ‘ARR’.

In the worst case, we have to iterate over the whole ‘ARR’ to find ‘K’ which results in the time complexity of O(N).

Space Complexity

O(1)

As we are using constant extra memory.

(100% EXP penalty)

Sparse Search

Console