DEV Community

Murtaza Nathani
Murtaza Nathani

Posted on • Edited on

Optimizing to find the top 3 numbers from an array

How to find the the top 3 largest number in an array parsing from a file..

There were many solution popping... like sorting and grabbing the top 3 elements,
That would require:

  1. parsing the file to an array --> O(n)
  2. sorting the array --> O(n)
  3. getting top --> c (constant time)

Doing this was boiling my blood.. and i was at unrest, so i wanted to optimize it by:

  1. parse the file and keep record of top 3 in an array [0, 0, 0] and keep comparing the current with top 3 to update them. --> O(n)

As follows:

     // current is greater then topThree first then set the all top three  
      if (current > topThree[0]) {
        topThree[2] = topThree[1];
        topThree[1] = topThree[0];
        topThree[0] = current;
      }

     // current is greater then topThree second then set bottom two  
      if (current < topThree[0] && current > topThree[1]) {
        topThree[2] = topThree[1];
        topThree[1] = current;
      }

     // current is greater then topThree third then set the third only.  
      if (current < topThree[1] && current > topThree[2]) {
        topThree[2] = current;
      }
Enter fullscreen mode Exit fullscreen mode

For more details check the code for day 1, aoc 2022 here:

https://github.com/m-nathani/aoc-2022/blob/main/src/days/day-1.ts

Looking forward to hear from you on comments to find other learnings you had for day1 or could improve the current approach more.

Top comments (0)