Fastest way to find all the indexes of maximum value in a list - Python

Question

I am having list which as follows

input_list= [2, 3, 5, 2, 5, 1, 5]

I want to get all the indexes of maximum value. Need efficient solution. The output will be as follows.

output = [2,4,6] (The above list 5 is maximum value in a list)

I have tried by using below code

m = max(input_list)
output = [i for i, j in enumerate(a) if j == m]

I need to find any other optimum solution.

You are doing two pass, the best you can do it in single pass, keeping track of current maximum and its all indexes , but again time complexity for the algorithm would still be `O()` or `O(len(input_list))`. — Yaman Jain, May 08 '19 at 04:01
Given that (in CPython) `max` loops in C and that your list comprehension allocates very little extra memory, what you have may already be optimal (rather than merely asymptotically optimal). — Davis Herring, May 09 '19 at 03:49

Netwave · Answer 1 · 2019-05-08T09:42:36.883

0

Use a for loop for O(n) and iterating just once over the list resolution:

from itertools import islice

input_list= [2, 3, 5, 2, 5, 1, 5]

def max_indexes(l):
    max_item = input_list[0]
    indexes = [0]
    for i, item in enumerate(islice(l, 1, None), 1):
        if item < max_item:
            continue
        elif item > max_item:
            max_item = item
            indexes = [i]
        elif item == max_item:
            indexes.append(i)
    return indexes

Here you have the live example

edited May 08 '19 at 09:42

answered May 08 '19 at 04:03

Netwave

40,134
6
50
93

Not sure if this is different then what the OP already does, but seems to add more verbosity to the solution! – Devesh Kumar Singh May 08 '19 at 09:35
@DeveshKumarSingh, It is verbose in purpose to explain all the conditions. And it is the only answer that solves it in one iteration over the elements :) – Netwave May 08 '19 at 09:40
1

So the complexity does get reduced from 2 to 1 iterations, but still the time complexity is O(n), maybe you want to mention that in your comment ? – Devesh Kumar Singh May 08 '19 at 09:41
is it fine if I take your idea of doing in it one iteration, but implement in another way? – Devesh Kumar Singh May 08 '19 at 09:45
@DeveshKumarSingh, yeah, your answer LGTM :) – Netwave May 08 '19 at 09:48

score 0 · Answer 2 · answered May 08 '19 at 04:05

0

 from collections import defaultdict
 dic=defaultdict(list)
 input_list=[]
 for i in range(len(input_list)):
         dic[input_list[i]]+=[i]

 max_value = max(input_list)

 Sol = dic[max_value]

answered May 08 '19 at 04:05

sahasrara62

10,069
3
29
44

score 0 · Answer 3 · answered May 08 '19 at 04:20

0

Here's the approach which is described in comments. Even if you use some library, fundamentally you need to traverse at least once to solve this problem (considering input list is unsorted). So even lower bound for the algorithm would be Omega(size_of_list). If list is sorted we can leverage binary_search to solve the problem.

def max_indexes(l): 
     try: 
         assert l != [] 
         max_element = l[0] 
         indexes = [0] 
         for index, element in enumerate(l[1:]): 
             if element > max_element: 
                 max_element = element 
                 indexes = [index + 1] 
             elif element == max_element: 
                 indexes.append(index + 1) 
         return indexes 
     except AssertionError: 
         print ('input_list in empty')

answered May 08 '19 at 04:20

Yaman Jain

1,254
11
16

That try/except block is completely unnecessary. Also this answer is just a slightly modified version of one ot the other answers and do not make any improvement whatsoever. – Netwave May 08 '19 at 04:56
@Netwave we may need to check whether it is an empty list or not, it is just a way to perform defensive programming. – Yaman Jain May 08 '19 at 04:57
That message is just a sample of how OP wants to handle that error. – Yaman Jain May 08 '19 at 04:59
Why not using IndexError instead? or check if the list is empty and actually raise and exception? – Netwave May 08 '19 at 05:04

Devesh Kumar Singh · Answer 4 · 2019-05-08T09:54:05.583

0

Think of it in this way, unless you iterate through the whole list once, which is O(n), n being the length of the list, you won't be able to compare the maximum with all values in the list, so the best you can do is O(n), which you already seems to be doing in your example.

So I am not sure you can do it faster than O(n) with the list approach.

edited May 08 '19 at 09:54

answered May 08 '19 at 09:24

Devesh Kumar Singh

20,259
5
21
40

R4444 · Answer 5 · 2019-05-08T04:19:17.130

-1

You can use numpy (numpy arrays are very fast):

import numpy as np
input_list= np.array([2, 3, 5, 2, 5, 1, 5])
i, = np.where(input_list == np.max(input_list))
print(i)

Output:

[2 4 6]

edited May 08 '19 at 04:19

answered May 08 '19 at 04:01

R4444

2,016
2
19
30

Fastest way to find all the indexes of maximum value in a list - Python

5 Answers5