hackerrank sparse arrays in javascript

HackerRank – Sparse Arrays Solution in JavaScript – O(n) Time

by

Sparse Arrays is a coding challenge with medium difficulty in the HackerRank data structures category. In this blog post, we’ll discuss how we can solve it in JavaScript in O(n) time.

Problem Statement

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.

Read full details and access the challenge on Sparse Arrays | HackerRank

Intuitive Solution

function matchingStrings(stringList, queries) {
    let res = [];
    for (let i = 0; i < queries.length; i++) {
        res[i] = 0;
        for (let j = 0; j < stringList.length; j++) {
            if (queries[i] === stringList[j]) {
                res[i]++;
            }
        }
    }
    return res;
}

Time Complexity : O(n2)

Space Complexity : O(n)

This is an intuitive solution that hasn’t been optimized yet, so it’s quite slow.

First, we initiate the res variable as the result and a counter for times the queries appear.

We iterate through each of the queries and in the iteration of each queries, we iterate through the string List to check how many times it appears. we do it by comparing if the current value of the query and the current value of the string List is the same. If they match, we’ll add 1 count to that variable.

We’re using a nested loop for this, so we have O(n2) time complexity.

Well, we can further optimize this code into O(n) time.

Optimized Solution

function matchingStrings(stringList, queries) {
    let appearances = {}, res = [];
    for (let i = 0; i < stringList.length; i ++) {
        if (!appearances[stringList[i]]) {
            appearances[stringList[i]] = 1;
        } else {
            appearances[stringList[i]]++;
        }
    }
    for (let i = 0; i < queries.length; i++) {
        if (appearances[queries[i]]) {
            res[i] = appearances[queries[i]];
        } else {
            res[i] = 0;
        }
    }
    return res;
}

Time Complexity : O(n)

Space Complexity : O(n)

In this optimized solution, we add one variable, which is appearances to count how many times each string in the string List appears. We also have the res variable which will be the result.

First, we loop through the string List to check how many times each string appears.

After we get the count of each string, we loop through the queries to check if the query is in the string List. If the query does appear in the string List, we just assign the count from appearance to the res for that query. If it doesn’t appear, we assign 0 to it.

In the end, we return the res variable.

We’re separating the nested loop into two separate loops so that the efficiency increases from O(n2) to O(n) in Time Complexity.

Conclusion

That’s how you can solve and optimize the Sparse Arrays Challenge in HackerRank.

If you have another approach different from mine, please do comment below!

Check out the rest of my blog for more helpful contents on Data Structures and Algorithms in JavaScript! We’ll also discuss more HackerRank solutions in JavaScript for the upcoming posts!

See you next post!

Leave a Comment