Index of nth biggest item in Python list

Question

I can't edit or sort the list. How can I get that index?

Answer 1

What you've got is already O(n) in complexity (max is O(n), as is index(), IIRC). So while you could technically just remove the largest if it's not appropriate and try again, you're starting to get into bubblesort territory in terms of big-O. How many items are typically on the list?

One option is QuickSelect, which is basically a reduced QuickSort, but honestly just sorting the list up front is not going to be much slower than what you've got already.

You can use the sorted() function to return a new sorted list if you don't want to change the ordering of the original list.

Answer 2

The heapq module provides a nlargest function that efficiently finds the n largest elements of a list:

>>> from heapq import nlargest
>>> items = [100, 300, 200, 400]
>>> indexes = [0, 1, 2, 3]
>>> nlargest(2, indexes, key=lambda i: items[i])
[3, 1]