Code Optimization By Not Using Nested For Loop - Hackerrank Sparse Arrays

Question

I need help.

https://www.hackerrank.com/challenges/three-month-preparation-kit-sparse-arrays/problem?h_l=interview&isFullScreen=true&playlist_slugs%5B%5D%5B%5D=preparation-kits&playlist_slugs%5B%5D%5B%5D=three-month-preparation-kit&playlist_slugs%5B%5D%5B%5D=three-month-week-one

The link above is the question on hackerrank. I have solved the problem and I was allowed to do the next challenge but I don't think my solution is the most optimized. I really wanna know about the best possible approach.

My code / solution:

def matchingStrings(strings, queries):
    # Write your code here

    # strings = sorted(strings)
    # queries = sorted(queries)
    results = []

    LENGTH_Q = len(queries)
    LENGTH_S = len(strings)
    for i in range(LENGTH_Q):
        total = 0
        query = queries[i]
        for j in range(LENGTH_S):
            string = strings[j]
            if query == string:
                total += 1
        results.append(total)

    return results

I believe my solution results to quadratic complexity which is not good. Please show me or give me hints on how to think of a better solution to this problem.

Thank you.

UPDATE:

I have a second version of my solution but still not sure if it is more efficient because I don't know how the function [LIST].count() works inside. Anyway, please take a look the 2nd version:

def matchingStrings2(strings, queries):
    results = []

    LENGTH_Q = len(queries)
    for i in range(LENGTH_Q):
        query = queries[i]
        results.append(strings.count(query))

    return results

To make it slightly more efficient you can create an array of tuples of all possible two-element combinations of two input lists using `itertools` module and then go through all the resulting tuples and do a set intersection of elements to see if one of the strings contains the other. — NotAName, Oct 06 '22 at 03:56
@pavel Thank you. I will consider that but currently it is kinda new concept for me. Could you take a look at my update. I added a 2nd version of my solution. — Moron Boy, Oct 06 '22 at 04:09
`list.count` has a complexity of `O(n)` (see [here](https://stackoverflow.com/a/44813154/7938503)) so its still quadratic in runtime complexity. — Plagon, Oct 06 '22 at 05:01

shawn caza · Accepted Answer · 2022-10-07T02:02:14.253

Instead of getting the length of the queries list and using i as an index to reference each value, in python you could just do a for loop for the length of an iterable like this:

for query in queries:

Then instead of defining an empty list and appending counts in the for loop, you could use list comprehension like this:

results = [strings.count(query) for query in queries]

I've been watching Raymond Hettinger videos. He is the 'itertools guy'. He's also on stackoverflow.

In the video he also talks about generator expressions. If we take out the square brackets from the above maybe it uses less memory? Probably doesn't matter with short input lists.

results = (strings.count(query) for query in queries)
return list(results)

I'm not sure if there are any good alternatives to .count() in this situation.

Code Optimization By Not Using Nested For Loop - Hackerrank Sparse Arrays

1 Answers1