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:
- parsing the file to an array -->
O(n)
- sorting the array -->
O(n)
- getting top -->
c
(constant time)
Doing this was boiling my blood.. and i was at unrest, so i wanted to optimize it by:
- 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;
}
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)