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

Free 5-Day Mini-Course: https://backtobackswe.com Try Our Full Platform: https://backtobackswe.com/pricing 📹 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