Huy's Notes
Find the Second Largest Element

Find the Second Largest Element

#algorithm

Given an array of integers, our task is to write a program that efficiently finds the second largest element present in the array.

Example:

Input : arr[] = {12, 35, 1, 10, 34, 1}
Output : The second largest element is 34.

Input : arr[] = {10, 5, 10}
Output : The second largest element is 5.

Input : arr[] = {10, 10, 10}
Output : The second largest does not exist.

The solutions:

  1. Simple solution: Sort array in descending order, then print out the second element. This one is O(n log n).

  2. Better solution: Traverse the array twice, in the first traversal, find the max. In the second, find the greatest element but less than the max. This one is O(n).

  3. Best solution:

  - Initialize two variables first and second to INT_MIN as:
        first = second = INT_MIN
  - Start traversing the array,
    a) If the current element in array say arr[i] is greater
        than first. Then update first and second as,
        second = first
        first = arr[i]
    b) If the current element is in between first and second,
        then update second to store the value of current variable as
        second = arr[i]
  - Return the value stored in second.

Referred in


If you think this note resonated, be it positive or negative, please feel free to send me an email and we can talk.