Find The Second Largest Item - Heap & Tracking Approach (Beginner Big N Interview Question)

📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

Question: Given an array that may or may not be sorted, find the second largest item.

Approach 1 (Single Pass)

We keep track of a variable for the maximum number and keep track of a variable for the minimum number.

We do a linear traversal.

We keep track of a firstMax and a secondMax.

If the element is greater than firstMax:
firstMax becomes secondMax.
the element becomes firstMax.

Otherwise, if the first element is larger than secondMax and it is not the firstMax:
the element becomes secondMax.

The key thing here is to realize the case where the element might not dominate firstMax but it might still dominate the secondMax but it cannot dominate the secondMax if it is firstMax or else we will lose our actual secondMax.

At the end if secondMax is still not defined then we do not have an answer, otherwise, secondMax is our answer.

Complexities

Time: O( n )
n is the length of the array

Space: O( 1 )
we do not create anything past local variables that are primitives

Approach 2 (Min Heap)

We can use a min heap to hold at maximum 2 items. A min-heap will always have the smallest item available to us so we can get rid of it to only keep the k largest items.

it is almost like we need to think in opposites:
to extract the k max elements we use a min heap.
to extract the k min elements we use a max heap.

This is because the heap type desired corresponds to the item that we care the least about. To find maxes we don't care about mins. To find mins we don't care about maxes.

Every time we add a 3rd item we eject the smallest item from the min heap.

By the end of the traversal, we can just eject what our min heap held and that will be the 2nd largest item in the array.

Complexities

Time: O( n * log(2) ) = O( n )

insertion and removal from the heap will always take log(2) which is O( 1 ) time ("constant") assuming that it is a balanced binary heap.

We traverse an array of length n.

Space: O( 2 ) = O ( 1 )

The space used for the min heap will always be constant.

Critical that you keep in mind:
empty cases [ ]
cases where there is only 1 item [ 2 ]
cases where there are repeated items [ 3, 3, 3, 3, 3, 3 ], etc.

++++++++++++++++++++++++++++++++++++++++++++++++++

[BackToBackSWE]

Table of Contents:

Me Talking (Please Skip This) 0:00 - 0:33
The Problem Introduction 0:33 - 1:36
The First Solution I Thought Of 1:36 - 2:11
Roughly How The Heap Approach Would Go 2:11 - 5:00
Reflecting On The Heap Approach 5:00 - 5:24
Time & Space Complexities: Heap Approach 5:24 - 6:04
The Local Variables Approach Walkthrough 6:04 - 8:30
Time & Space Complexities: Local Variables Approach 8:30 - 8:53
Wrap Up 8:53 - 9:14

The full code for this problem is in the description. Fully commented for understanding and teaching purposes.

I forgot to explain time complexity for the heap approach. It is O(n) since for almost all elements (we skip items already in the heap) we will do insertion into the heap and some removals. Both operations will take log(2) time which is a constant. So O(n * log(2)) time is just O(n) ("linear") time where n is the length of the array.

[deepakps]

0:06 You are not a random dude . You are My Teacher. All your videos are incredible 🎁 . Your teaching clears sits in my mind ...

[udaychopra]

Dear Benyam,

Seeing the first part of the video of u saying how thanks makes you happy, I wanted to share something.
Your videos are the best of all in YouTube
When i was solving leetcode questions in my early stages i happened to see your video in a comment. I guess that question was make coin change.
From then on i have become a huge fan of yours and i never knew about Tushar Roy unless you told me.
After seeing that coin change problem, i made sure that until today i watch all your videos at-least once for my preparation and also not to forget about liking every video of yours (That helps you right and you help us).
Thanks for the hard work man, you are the dude.

[dansheldon]

Thanks dude, you're the best coding teacher I've seen so far!

[priyamvashi]

Thank you so much.
and the way you give detail in concept and even in description its so good.

[kartikeymishra]

Hey man, love the way you go through the thought process that goes into problem solving something which very few people in computer science touch upon generally

[adityasaxena]

Thanks a lot. Absolute amazing solution.

[adityasoni]

Awesome Video! Thanks! Binge watching all of your amazing video! Very few people explain the reasoning behind an algo, most of them jump into the solution directly.

We can also traverse the same array twice, first finding the max and then finding the second max.

[reactorscience]

Binge-watching your videos. They are great. Thanks for making

[darshannair]

Thank you so much for all your session. Its really a fun and encourages to learn more. Salute you!!!

[emmanuelo]

Thanks for the videos.
You're really helping lots of people.
Keep up the good work

[angelanayiga]

You are God sent! Thank you, Thank you, Thank you!

[cmyker]

You're amazing! Thank you for helping us to understand those solutions. Kudos from Ukraine.

[vibekdutta]

I am from India and your videos are so awesome Sir, thanks for all your efforts, I am really greatful to you and all other people like you on YouTube

[ericodoom]

This is incredible! Could we use a max heap and pop off the root while adding it to some array with a variation of this logic?

[freddiejefferson]

for( int i = 0; i < 100; i++ )
System.out.println("Thank you!! This helped a lot");

[MichaelSalo]

Would you consider the local variables approach for finding the 3rd or more largest item?

[saboorahamd]

Hats-off to the way of explanation. Wish you success in your target of an education network (if I understood correctly :P)

[varshamehra]

thankyou thank you thank you so much brother

[YT-yt-yt-]

I felt both the approach are almost similar. When you use min heap of capacity two, underneath it is working as two pointer thing. In 2nd approach, are we not just reimplementing the min heap push implementation.