How can I optimize my Python code to run faster?

Question

Define an element of a list of items to be a dominator if every element to its right (not just the one element that is immediately to its right) is strictly smaller than that element. Note how by this definition, the last item of the list is automatically a dominator. This function should count how many elements in items are dominators, and return that count. For example, the dominators of the list [42, 7, 12, 9, 13, 5] would be the elements 42, 13 and 5. The last element of the list is trivially a dominator, regardless of its value, since nothing greater follows it.

I am working on this practice problem and have a code that works, however it's quite slow. How can I best optimize this to run faster?

def count_dominators(items):
    item_count = len(items)
    count = 0
    if item_count==0:
        return count;
        
    count+=1;
    
    if item_count==1:
        return count;
    
    for i in range(0,len(items)-1):
        flag=1
        for j in range(i+1,len(items)):
            
            if(items[j]>=items[i]):
                flag=0;
                break;
          
       
        if(flag==1):
            count+=1;
    return count

Answer 1

import numpy as np

def count_dominators(items):
    dominators = np.unique(np.maximum.accumulate(seq[::-1]))
    return dominators.size, dominators

seq = [42, 7, 12, 9, 13, 5]
print(count_dominators(seq))
>>>(3, array([5, 13, 42]))

Answer 2

Iterating in reverse order will reduce this from a O(n²) to O(n) as you'll keep a running maximum as you go, without needing to rescan all trailing elements for each new element. So without relying on complex utilities you didn't write, you can just do:

def count_dominators(items):
    max_so_far = float('-inf')  # Smaller than any value to it's replaced immediately,
                                # identifying first element as dominator by definition

    count = 0
    for item in reversed(items):  # Iterate in reverse order so we only need to know max
                                  # so far to identify new dominators
        if item > max_so_far:
            max_so_far = item
            count += 1
    return count

If you want more magic to do less of the work yourself, Python's itertools module provides an accumulate function that can repeatedly perform an operation on elements as it goes, yielding the result so far. If you use max as the operation, then it generates a stream of numbers that changes only when you see a new dominator. Convert the result to a set or use itertools.groupby (which is roughly equivalent to the uniq command line utility when run without arguments, making it a cheap way to deduplicate adjacent duplicates) to dedupe, and the length of the set or the number of groups is the dominator count:

from itertools import accumulate, groupby

def count_dominators(items):
    return sum(1 for _, _ in groupby(accumulate(reversed(items), max)))

or at the cost of a technically unnecessary, growing for each new dominator, set (likely faster, as itertools.groupby has more overhead than you might expect, and the number of elements collected after deduplication is likely small enough to be irrelevant):

from itertools import accumulate

def count_dominators(items):
    return len(set(accumulate(reversed(items), max)))

You could replace the sum(1 for _, _ in (and the matching trailing parenthesis) with a more efficient recipe for counting elements in an iterator if you like (though it hardly matters unless the inputs are huge).

Answer 3

Assuming there are only positive numbers, you can run on a list from its end and mark the biggest number you've met. It will be O(n) complexity, instead of O(n^2) that you've suggested. Something like that shall work:

def count_dominators(items):
    count = 0
    last_biggest = -1
    for i in range(len(items)-1,-1,-1):
      if items[i] > last_biggest:
        last_biggest = items[i]
        count += 1

    return count