Count "Word Order" with further optimization

Question

Question:
You are given n words. Some words may repeat. For each word, print its number of occurrences. The output order should correspond with the input order of appearance of the word.

Sample Input:

4
bcdef
abcdefg
bcde
bcdef

Sample Output

3
2 1 1

Here's what I came up with:

n = int(input())
array = []
elements = {}
for index in range(n):
    value = input()
    if value not in array:
        array.append(value)
        elements[value] = 1
    else:
        elements[value] += 1

print(len(elements))
print(*(i for i in elements.values()), end=' ')

I stress tested it on Try it Online with the random string generator and found the runtime to be around 1.98s. But I'm getting TLE on the coding platform. How do I improve the speed (bit offtopic - is there any other approach)?

Answer 1

TLE

You're probably getting a TLE because,

if value not in array:

Is a O(N) operation meaning it has to traverse the entire array (worst case) to check if the value exists in the array

I can understand why you felt the need to have an extra array, because of dictionaries are not ordered.

But you can make use of the collections.OrderedDict module, to have an ordered dictionary!

Other

1. join!

   print(*(i for i in elements.values()), end=' ')
   

   This can be done cleaner with joining the values instead of unpacking

   print(" ".join(map(str, e.values())))
   

2. Counter

   Python is often described as batteries included,

   Your element dictionary is the same the collections.Counter

Code

We can make an OrderedCounter class to combine these two and make get the most out of the included modules.

from collections import Counter, OrderedDict

class OrderedCounter(Counter, OrderedDict):
    pass

c = OrderedCounter(input() for _ in range(int(input())))
print(len(c))
print(" ".join(map(str, c.values())))