Return to Answer

• 1

• 1k
• 7
• 14

• 1k
• 7
• 14

Let's get some obvious stuff out of the way first:

1. Do not compare to None using ==. Use variable is None instead. See this document for rationale: https://www.python.org/dev/peps/pep-0008/#id51
2. countSmaller should use snake case: count_smaller (similar convention).
3. res[::-1] - creates a reversed copy, which you don't need, since res is a local variable, which is not shared with other functions. You could use res.reverse() instead, saving some memory allocations.
4. Names of classes need to be in Pascal case, i.e. count_smaller needs to be CountSmaller.

Some subtleties: Python actually has array type, rarely used and, to be honest, not very useful, but, maybe if you are required to return an array, it is what you should return (or just reflect on the level of competence of the person describing the problem).

Now, while, in principle it's hard for me to think about a theoretically better algorithm, notice that a naive solution given below performs better on even reasonably long lists than the one you have simply because all the memory allocation and function calls needed to support this tree structure you've built are so expensive:

import cProfile
import random
def count_smaller(nums):
 result = [0] * len(nums)
 for i, n in enumerate(nums):
 for j in nums[i+1:]:
 if j < n:
 result[i] += 1
 return result
def test_count_smaller(n, m):
 for _ in range(n):
 count_smaller(random.sample(range(m), m))
def test_countSmaller(n, m):
 for _ in range(n):
 Solution().countSmaller(random.sample(range(m), m))
cProfile.run('test_count_smaller(100, 50)')

Gives:

 18888 function calls in 0.019 seconds
 Ordered by: standard name
 ncalls tottime percall cumtime percall filename:lineno(function)
 100 0.011 0.000 0.011 0.000 <stdin>:1(count_smaller)
 1 0.000 0.000 0.019 0.019 <stdin>:1(test_count_smaller)
 1 0.000 0.000 0.019 0.019 <string>:1(<module>)
 300 0.000 0.000 0.000 0.000 _weakrefset.py:70(__contains__)
 200 0.000 0.000 0.000 0.000 abc.py:178(__instancecheck__)
 5000 0.003 0.000 0.005 0.000 random.py:229(_randbelow)
 100 0.002 0.000 0.007 0.000 random.py:289(sample)
 1 0.000 0.000 0.019 0.019 {built-in method builtins.exec}
 200 0.000 0.000 0.000 0.000 {built-in method builtins.isinstance}
 200 0.000 0.000 0.000 0.000 {built-in method builtins.len}
 100 0.000 0.000 0.000 0.000 {built-in method math.ceil}
 100 0.000 0.000 0.000 0.000 {built-in method math.log}
 5000 0.000 0.000 0.000 0.000 {method 'bit_length' of 'int' objects}
 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
 7584 0.001 0.000 0.001 0.000 {method 'getrandbits' of '_random.Random' objects}

While your original code gives:

cProfile.run('test_countSmaller(100, 50)')
 59449 function calls (33812 primitive calls) in 0.030 seconds
 Ordered by: standard name
 ncalls tottime percall cumtime percall filename:lineno(function)
 1 0.001 0.001 0.030 0.030 <stdin>:1(test_countSmaller)
 100 0.004 0.000 0.022 0.000 <stdin>:14(countSmaller)
 5000 0.002 0.000 0.002 0.000 <stdin>:2(__init__)
30637/5000 0.016 0.000 0.016 0.000 <stdin>:2(add_node)
 1 0.000 0.000 0.030 0.030 <string>:1(<module>)
 300 0.000 0.000 0.000 0.000 _weakrefset.py:70(__contains__)
 200 0.000 0.000 0.000 0.000 abc.py:178(__instancecheck__)
 5000 0.003 0.000 0.004 0.000 random.py:229(_randbelow)
 100 0.002 0.000 0.007 0.000 random.py:289(sample)
 1 0.000 0.000 0.030 0.030 {built-in method builtins.exec}
 200 0.000 0.000 0.000 0.000 {built-in method builtins.isinstance}
 100 0.000 0.000 0.000 0.000 {built-in method builtins.len}
 100 0.000 0.000 0.000 0.000 {built-in method math.ceil}
 100 0.000 0.000 0.000 0.000 {built-in method math.log}
 5000 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}
 5000 0.000 0.000 0.000 0.000 {method 'bit_length' of 'int' objects}
 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
 7608 0.001 0.000 0.001 0.000 {method 'getrandbits' of '_random.Random' objects}