Program to Find Largest and Second Largest Element in an Array

• Write a program to find maximum and second maximum element in an unsorted array.
• Algorithm to find largest and second largest number in array without sorting it.

Given an integer array of size N, we have to find largest and second largest element of array. For Example:

Input Array : 3 8 -4 -2 0 5 -1 7 9
Largest element : 9
Second largest element : 8 

Here we are going to discuss about multiple approaches of finding maximum and second maximum element. Let inputArray be an integer array of size N.

---

By Sorting input Array : O(NLogN)

Sort input array using any O(nLogn) average time complexity sorting algorithm like quick sort or merge sort.

Print last and second last element of sorted inputArray.

---

By linearly searching maximum element twice : O(n)

Traverse inputArray from index 0 to N-1 and search for maximum element. Let maximum element is found at index i.

Swap maximum element(inputArray[i]) and last element of inputArray (inputArray[N-1]).

Now, again search for maximum element from index 0 to N-2.

---

By searching maximum and second maximum element in single scan : O(n)

Algorithm to find largest and second largest element of an array
We can optimize above method by finding both maximum and minimum element in single pass of inputArray.

• Initialize max and secondMax to INT_MIN.
• Traverse inputArray from index 0 to N-1. Let current element be inputArray[i].
• If inputArray[i] is > max then set secondMAx = max; and max = inputArray[i];
• Else if inputArray[i] is between max and secondMax (inputArray[i] > secondMax and inputArray[i] < max) then set secondMax = inputArray[i];
• At the end of the loop, max and secondMax will hold the largest and second largest element of inputArray.

C program to find largest and second largest element of array

#include <stdio.h>
#include <conio.h>
#include <limits.h>
 
int main(){
    int array[500], count, i;
    int max, secondMax;
     
    printf("Enter number of elements in array\n");
    scanf("%d", &count);
         
    printf("Enter %d numbers \n", count);
    for(i = 0; i < count; i++){
        scanf("%d", &array[i]);
    }
    /* Initialize max and secondMax 
       with INT_MIN */
     
    max = secondMax = INT_MIN;
     
    for(i = 0; i < count; i++){
        if(array[i] > max){
            secondMax = max;
            max = array[i];
        } else if (array[i] > secondMax 
            && array[i] < max){
            secondMax = array[i];
        }
    }
    /* Printing Maximum And Second Maximum element */
    printf("Maximum Element : %d \nSecond Maximum Element: %d", max, secondMax);
         
    getch();
    return 0;
}

Output

Enter number of elements in array
7
Enter 7 numbers
6 2 0 -3 4 1 7
Maximum Element : 7
Second Maximum Element: 6

Similar approach be used to find smallest and second smallest element of array.