Find Three Largest in O(n) time

Problem

Given an array with N number of elements. The array may or may not be sorted. You have to find the three largest numbers from the array in sorted order.

For Example:

Input:

[5,12,3,-8,-2,1,6]

Output

[5,6,12]

Algorithm:

1. Take List Input

2. check if list size is less than 3 then

3. return "List size should be less than or equal to 3" and terminate the program

4. declare a empty array of size 3 and fill them with Null or None

5. iterate through the entire array and check if

if array[2]==None(Null) or array[2]<iterable(i) then

array[0] = array[1]

array[1] = array[2]

array[2] = i

elif array[1]==None or array[1]<i then

array[0] = array[1]

array[1] = i

elif array[0]==None or array[0]<i then

array[0] = i

6. Print array

Code:

def get_three_largest(array):
 if len(array)<3:
 return "Array Size should be more than or equal to 3!"
    result = [None,None,None]
 for i in array:
 if result[2]==None or result[2]<i:
            result[0] = result[1]
            result[1] = result[2]
            result[2] = i
 elif result[1]==None or result[1]<i:
            result[0] = result[1]
            result[1] = i
 elif result[0]==None or result[0]<i:
            result[0] = i
 return result

#Test Case 1
array = [141,1,17,-7,-17,-27,18,571,8,7,7]
print(get_three_largest(array))
#output [18,141,571]

#Test Case 2
array = [5,12,3,-8,-2,1,6]
print(get_three_largest(array))
#output [5,6,12]

#Test Case 3
array = [0,1]
print(get_three_largest(array))
#Array Size should be more than or equal to 3! 

---

Happy Coding! Follow us on Instagram @programmersdoor Join us on Telegram @programmersdoor Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem. Follow Programmers Door for more. #blog #interview #placement #learn #computer #science