</>EmbeddedInterview

How do you find the second largest element in an array?

EasyArrays & Strings (Coding Round)

Short answer: Scan once, keeping largest and second. When a value beats largest, the old largest becomes second; when a value is between them (and not equal to largest), it becomes second. Start both at INT_MIN, not 0, so negative arrays work.

#include <limits.h>
#include <stdbool.h>
#include <stddef.h>

/* returns false if there is no distinct second largest */
bool second_largest(const int *arr, size_t n, int *out)
{
    int first = INT_MIN, second = INT_MIN;
    bool found = false;

    for (size_t i = 0; i < n; i++) {
        if (arr[i] > first) {
            second = first;
            first = arr[i];
            if (i > 0) found = true;          /* a previous value now sits in second */
        } else if (arr[i] < first && (arr[i] > second || !found)) {
            second = arr[i];
            found = true;
        }
    }
    if (found) *out = second;
    return found;
}
/* {96, 54, 4, 69, 4, 6, 3, 4, 0} -> 69 */

Dry run for {96, 54, 69}: 96 → first=96. 54 → between, second=54. 69 → between and > 54, second=69. Answer 69.

Mistakes interviewers look for

  1. Initialising to 0. int max = 0, sec = 0; gives the wrong answer for {-5, -2, -9} (it returns 0, which is not in the array). Use INT_MIN or the first element.
  2. Duplicates of the maximum. For {7, 7, 3} the second largest distinct value is 3. The arr[i] < first check stops the second 7 from being taken.
  3. No answer exists: an array of one element or all equal values. Return a status instead of a magic number.

Complexity: O(n) time and O(1) space, one pass. Sorting (O(n log n)) and picking the second-from-end is acceptable only if the interviewer allows it, and you still need to skip duplicates.

Follow-up: "k-th largest?" Use a min-heap of size k (O(n log k)) or quickselect (average O(n)).