Hackerrank Gemstones Solution

Question

I'm looking for any possible improvements in terms of memory usage and speed, but really any advice is welcome.

Problem statement:

John has discovered various rocks. Each rock is composed of various elements, and each element is represented by a lower-case Latin letter from 'a' to 'z'. An element can be present multiple times in a rock. An element is called a gem-element if it occurs at least once in each of the rocks.

Given the list of rocks with their compositions, display the number of gem-elements that exist in those rocks.

Input Format

The first line consists of an integer, , the number of rocks. Each of the next lines contains a rock's composition. Each composition consists of lower-case letters of English alphabet.

Constraints Each composition consists of only lower-case Latin letters ('a'-'z'). length of each composition

Output Format

Print the number of gem-elements that are common in these rocks. If there are none, print 0.

My code: Essentially I build N lists of True or False values (since the number of times the same element appears doesn't matter), and at the end just "and" them two by two using reduce to end up with a final list of True values for the elements that were True in each rock, and then just sum up the True values.

import sys
from functools import reduce

# this is just to get test cases input
N = int(input())
strings = []
for i in range(N):
    strings.append(input())

# actual implementation starts here
lists = [[False] * 26 for i in range(N)]

for i in range(N):
    for c in strings[i]:
        # ord() gives the ASCII value of a character
        lists[i][ord(c) - ord('a')] = True

final_list = reduce(lambda x, y: [x[i] and y[i] for i in range(26)], lists)

print(reduce(lambda x, y: x + y, final_list))

Answer 1

There are several ways you can save memory, where you’re storing more information than you really need. In some cases, way more information than you need.

If you only save what you need, you’ll reduce memory and get a performance benefit to boot!

Memory improvement #1

These three lines are wasting memory:

strings = []
for i in range(N):
    strings.append(input())

You don’t actually need to gather up all the rocks into a list – you’re only ever looking at one at a time. Although in this case it’s unlikely to matter, creating a list when you don’t need one is a bad antipattern.

You can rewrite your code to make the strings list unnecessary, thus saving memory, like so:

lists = [[False] * 26 for i in range(N)]

for i in range(N):
    rock = input()
    for c in rock:
        # ord() gives the ASCII value of a character
        lists[i][ord(c) - ord('a')] = True

Note that this also only features one for loop of length N, which will likely have a (small) benefit to performance.

Memory improvement #2

The lists variable (that’s not a great name, btw) is a 26 x N-sized matrix. Again, this has the potential to get quite large if you have lots of rocks, or lots of different elements. And you’re storing more data than you need to – all we’re interested in is which elements were present in each rock. A simpler way to store that would be something like:

rock_elements = []

for _ in range(N):
    rock = input()
    rock_elements.append(set(rock))

final_list = reduce(lambda x, y: [i in x and i in y for i in range(26)], lists)

Now the rock_elements list only contains the set of elements in each rock. We’re not provisioning lots of unwanted memory for small rocks.

Memory improvement #3

We’re still storing more information than we need. For example, suppose the first rock omits a, and every other rock contains a. Remembering that those later rocks contain a is pointless, because we know that a isn’t a gem-element.

So an even more efficient solution would be to keep a set of possible gem-elements, and throw elements away whenever we find a rock that doesn’t contain them. Like so:

import string

gem_elements = set(string.ascii_lowercase)

for _ in range(N):
    rock = input()
    gem_elements = gem_elements & set(rock)

print(len(gem_elements))

Now our gem_elements set will never be larger than the number of possible elements, and we’re only storing the data for one rock at a time. Much better!

And as a nice side benefit, we’ve got rid of the two calls to reduce(), which are:

• Generally not very Pythonic – idiomatic Python tends towards list comprehensions and similar rather than reduce() and map().
• Moderately expensive – I think at least \$O(N)\$ in the number of rocks?