HackerRank Sparse Arrays Solution

There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results.

Example

strings = [‘ab’, ‘ab’, ‘abc’]
queries = [‘ab’, ‘abc’, ‘bc’]

There are 2 instances of ‘ab, 1 of ‘abc’ and 0 of ‘bc’. For each query, add an element to the return array, .

Function Description

Complete the function matchingStrings in the editor below. The function must return an array of integers representing the frequency of occurrence of each query string in strings.

matchingStrings has the following parameters:

string strings[n] – an array of strings to search
string queries[q] – an array of query strings

Returns

int[q]: an array of results for each query

Input Format

The first line contains and integer , the size of .
Each of the next lines contains a string .
The next line contains , the size of .
Each of the next lines contains a string .

Solution

This is a classic “occurrences” problem where it’s good to use a helper data structure, such as a hash table.

For this challenge, I used Javascript.

One possible solution was to compare each query item in the strings array, and increments each repetition, but that whould take O(n²) since we would had to iterate through the entire strings array for each query item.

So, we need to find an faster alternative, although we still need to check every item in each array. So the simplest solution was to iterate only once over each array.

function matchingStrings(strings, queries) {
    const occurrences = {}
    const result = Array(queries.length)
    strings.forEach(str => {
        if (occurrences[str]) {
            occurrences[str]++;
        } else {
            occurrences[str] = 1;
        }
    })
    queries.forEach((q, index) => {
        if (occurrences[q]) {
            result[index] = occurrences[q]
        } else {
            result[index] = 0
        }
        
    });
    return result
}Lenguaje del código: JavaScript (javascript)

Explanation

First, we set our result array of the same size of queries. and our occurrences helper, that, in the case os JS, we can use an object since it acts like a hash table:

const occurrences = {}
const result = Array(queries.length)Lenguaje del código: JavaScript (javascript)

Next, we iterate over every item on strings array, and increments its repetition on our occurrences table. At this point, we don’t care if any of these strings is in our queries list:

strings.forEach(str => {
    if (occurrences[str]) {
        occurrences[str]++;
    } else {
        occurrences[str] = 1;
    }
 })Lenguaje del código: JavaScript (javascript)

Finally, we just need to iterate over the queries array, and add the number of repetitions to our result array for each item. We do this by simply checking their values in our occurrences table. The only trick here, is to check if the query item actually exists in our occurrences table, otherwise, the query string wouldn’t be added to our result, and we need to add it even with 0 repetitions. And then just return the results array:

queries.forEach((q, index) => {
    if (occurrences[q]) {
        result[index] = occurrences[q]
    } else {
        result[index] = 0
    }        
});
return result;Lenguaje del código: JavaScript (javascript)