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]
print(three_highest(rand_ar))
print(rand_ar)
Last updated
Was this helpful?