Last Updated: 24 Feb, 2021

Sparse Search

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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’.

Solve now

02 Approach

The idea is to binary search on ‘ARR’ as ‘ARR’ is sorted. However, it would have been much easier to implement a binary search if we were not given empty strings in ‘ARR’. But still, we can use the binary search with some modification. So on encountering an empty string while performing binary search we will simply move to the closest non-empty string.

Initialize two integer variables ‘START’ = 0 and ‘END’ = ‘N’ - 1.
Keep on iterating while ‘START’ <= ‘END’ and do:
- Initialize an integer variable ‘MID’ = (‘START’ + ’END’) / 2.
- If ‘ARR[MID]’ is an empty string then do:
  - Find the closest non-empty string :
    - Let’s ‘LEFT’ = ‘MID’ - 1 and ‘RIGHT’ = ‘MID’ + 1.
    - Iterate while ‘LEFT’ >= ‘START’ or ‘RIGHT’ <= ‘END’ and do:
      - Check if ‘ARR’ on the ‘LEFT’ index or ‘RIGHT’ index has a non-empty string and assign that index to ‘MID’.
      - Decrease ‘LEFT’ by 1 if ‘LEFT’ > 0.
      - Increase ‘RIGHT’ by 1 if ‘RIGHT’ < ’N’.
- If the string on ‘MID’ is equal to ‘K’ then do:
  - Return 'MID'
- If the string on 'MID' is less than ‘K’ then do:
  - ‘START' = 'MID'+1
- If the string on 'MID' is greater than ‘K’ then do:
  - 'END' = 'MID'-1.
Return -1 if we can not find ‘K’.

Solve now