Find 2nd largest element. Two variables vs priority queue for interview

Question

A classical interview problem is "Find 2nd largest element in an array".

The most straight forward way would be to keep track of variables like largest, secondLargest, and iterate over, O(n) time complexity, and O(1) space complexity.

Another option would be to keep priority queue implemented by using heap size 2 (or K), and get the elements the heap, after you iterate. For each iteration, I am adding to queue size of 2, so the time complexity is O(n*log(K)), where K is 2, so it is technically O(n).

Here is argument from each side:

Two variables:

• simple for loop
• thinking about going beyond k=2 is a "You Aren't Gonna Need It (YAGNI)" problem.
• Some O(n) are better solutions, if it requires less computations.

Priority queue:

• overhead of heap exists and it affects the coefficient in the time complexity. But we drop constants in complexity analysis, so it is technically a linear solution.
• But can be easily modified for find kth largest element.
• It isn't that much more difficult to implement it.

My point of view is that the two variables version is definitely more performant and simple for this specific question, but I have slight preference toward the heap version because even with some expense and extra code, it can be easily scaled. I don't think the scope is big enough to consider using heap a "YAGNI".

Assuming back and forth discussion has been done during the interview, which one would you prefer?

Edit: As mentioned in the comments/answer section, I have specified priority queue with heap implementation.

Answer 1

If you look at the definition for priority queue, it basically states:

A priority queue is a special type of queue in which each element is associated with a priority value

Note that no particular data structure is mentioned to implement the priority queue. It is generally done using a heap (like you have assumed in your statement), but that's not always true (here's a priority queue using linked list). As Matt has pointed out in his comment, keeping a track of the largest and second largest element is the same thing as having a priority queue of size 2.