> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/sorting-and-searching/three-highest-numbers.md).

# 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

```python
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)
```