Three Highest Numbers

Given an array, return the 3 max numbers in linear time, and constant space.

The Idea: Find the max 3 times. Every time, modify the contents of the array so that previous maximum is ignored. Restore the contents of the array in the end.

Complexity: O(n) time and O(1) space

import sys

def three_highest(nums):
    max_i_1 = nums.index(max(nums))
    max_v_1 = nums[max_i_1]
    nums[max_i_1] = -sys.maxsize

    max_i_2 = nums.index(max(nums))
    max_v_2 = nums[max_i_2]
    nums[max_i_2] = -sys.maxsize

    max_i_3 = nums.index(max(nums))
    max_v_3 = nums[max_i_3]
    nums[max_i_3] = -sys.maxsize

    nums[max_i_1] = max_v_1
    nums[max_i_2] = max_v_2
    nums[max_i_3] = max_v_3

    return [max_v_1, max_v_2, max_v_3]

rand_ar = [9,4,89,6,7,5,781,964,7,8,5,201,20,9,7,1,2,35,612,30,7]

Last updated