Find Second Largest Number in Array

Find Second Largest Element in an Array

Refer to the Example and Explanationsections for more details about how to find second largest number in array and the Approach section to understand the explanation of how to find second largest number in array.

Example

Let us look at some of the examples provided to find second largest element in array.

Example 1: Given input array is {12, 35, 1, 10, 34, 1} Output: The second largest element in array is 34.

Example 2: Given input array is {10, 5, 10} Output: The second largest element in array is 5.

Example 3: Given input array is {10, 10, 10} Output: N/A. (No second largest element is present in the given array, so we cannot find second largest number in array.)

Example Explanation

Before getting into the explanation of how to find second largest element in array, let us first get a brief introduction about the arrays.

An array is a linear collection of values stored at contiguous memory locations. Array stores homogeneous values(similar data type values).

Some of the important points to keep in mind regarding arrays are as follows:

• The arrays occupy continuous (contiguous) space in the memory.
• The indexing of the array starts with 0 and goes on to (length of array - 1).
• Arrays are of fixed length, i.e. after the creation of an array, we cannot change the size of the array.
• The access of elements is very fast in arrays. We can easily access any element using the index of the array.

Example: The array os 56, 50, 34, 24, 12 will look like:

To learn more about the arrays, refer to the article - Arrays in Data Structure.

Constraints

• The first input is the number of elements present in the array i.e. n.
• The second input is the sequential set of elements of the array.

In some problems, you may find the number of test cases represented by t. So, we only need to call the reverse function t-times.

The problem is to find second largest element in array.

Approach 1 (Simple Solution)

Let us learn the simple or brute force approach to find second largest element in array. One of the most simple solutions can be sorting the array in ascending order and then finding the second element which is not equal to the largest element from the sorted array. So, in this way, we can find second largest element in array.

Pseudo code can be:

C++ :

Java:

JavaScript:

Python:

Output:

Complexity Analysis

In this simple approach to find second largest element in array, we are first sorting the array which takes O(log n) time. Apart from that, we are not using any extra space rather than one variable namely second_largest to store and return the answer.

Time Complexity

The time complexity of this above approach to find second largest number in array is O(n log(n)), where n is the number of elements present in the array.

Space Complexity

The space complexity of the above approach is O(1).

Approach 2 (Better Solution)

Let us learn a better yet simple approach to find second largest element in array. One of the most basic or simple solutions can be running two loops. The first loop will find the first largest element in the array (let's say first_largest is the largest element present in the array). After that, the second loop will find the largest element present in the array which is smaller than first_largest. So, in this way, we can find second largest element in array.

Pseudo code can be:

C++:

Java:

JavaScript:

Python:

Output:

The second largest element in the array is:  34

Complexity Analysis

In this better yet simple approach to find second largest element in array, we are using two loops but one after the other (not a nested loop). Here, we are traversing the array twice. Apart from that, we are not using any extra space rather than two variables namely first_largest and second_largest.

Time Complexity

The time complexity of the above approach to find second largest number in array is O(n), where n is the number of elements present in the array.

Space Complexity

The space complexity of the above approach is O(1).

Approach 3 (Efficient Solution)

Let us now discuss an efficient approach to find second largest element in array. In this approach, we need two variables namely first_largest and second_largest. As the name suggests, the second_largest variable will ultimately store the index of the second largest element.

Initially, set the value of the first_largest variable with 0 and the second_largest variable with the value -1. Now, we will need only one traversal (one loop) to get our answer. In each iteration, we need to check if the current element in the array (i.e. a[i]) is greater than the element at the first_largest index (a[first_largest]) or not. If it is greater, then we need to update the values of second_largest and first_largest. Update the value of second_largest with the value present in first_largest (i.e. second_largest = first_largest) and update the value of first_largest with the index value of the current element (i.e. first_largest = i). (Refer to the pseudo-code and code for better clarity). On the other hand, if the value of the current element is in between first_largest and second_largest, then update second_largest to store the index value of the current element (i.e. second_largest = i). Once the loop is completed, return the element present at the second_largest as result. So, in this way, we can find second largest element in array.

Pseudo code can be:

C++:

Java:

JavaScript:

Python:

Output:

Complexity Analysis

In this effective approach to find second largest element in array, we are traversing the array only once. Apart from that, we are not using any extra space rather than two variables namely first_largest and second_largest.

Time Complexity

The time complexity of the above approach to find second largest number in array is O(n), where n is the number of elements present in the array.

Space Complexity

The space complexity of the above approach is O(1).