Find all occurrences of max value in an unsorted list - single pass with constant memory

Question

This question was asked to me in an interview. Given an unsorted list of integers if one can find all occurrences of the max value in linear time and constant memory.

I couldn't answer it back then and came across the median of medians algorithm. Still unsure if this algorithm is applicable in this case.

Answer 1

You can find a max value of a set in O(n). Just go through the list and update the max:

max = int_array[0]
for i = 1 to int_array.size():
    if int_array[i] > max:
        max = int_array[i]

In the next pass, you can call the desired functionality on every such element. E.g. if you want to print out their position, and finally their count:

count = 0
for i = 0 to int_array.size():
    if int_array[i] == max:
        print "Index i"
        count += 1
print count

You can always determine the count in the first pass, increasing it whenever the current element is equal to max and resetting it to one every time you change the current max (e.g. current element is larger than the current max). In the same way, you could remember the positions of the maximums in the first pass. So, integrating it all to one:

count = 1
max = int_array[0]
indexes = [0]
for i = 1 to int_array.size():
    if int_array[i] == max:
        count += 1
        indexes.insert(i)
    else if int_array[i] > max:
        count = 1
        indexes = [i]
        max = int_array[i]
print "There are " + count + " elements with maximal value of " + max
print "On positions: "
for int i = 0 to count:
    print indexes[i]