Find Three Largest in O(n) time

Updated: Jul 14

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

        Contact Us

programmersdoor@gmail.com

  • LinkedIn
  • Facebook
  • Instagram

©2023 by Programmers Door