In this article, we will learn how to find second largest number in an array. We will see various approaches to finding second largest number in an array with the time and space complexity of each approach. We will also see a dry run to solve the problem.
What is the Second Largest Element in an Array?
Lets see examples to understand what is the second largest element in an array.
Example 1:
In the above example, the second largest element in an array is 86 ( first largest = 98 ).
Example:2
In the above example, the second largest element in an array is 75.
How to Find Second Largest Number in Array?
Lets see different approaches to finding the kth largest element in an array.
Approach 1: Sorting
Below are the steps to find second largest number in array using the sorting method,
- Sort the array into descending order
- The second largest element in an array is arr[1] (0-based indexing).
- If the array is sorted into ascending order then,
- The second largest element in an array is arr[n-2] where n is the size of an array (0-based indexing).
Lets understand this approach to find the kth largest element in an array with an example.
In the above example, after sorting the array into descending order, the second largest number in an array is 75 (arr[1]).
Now, lets see how to write a program to find second largest number in array.
# Python program to find second largest number in array def secondSmallest(arr, N): # Sort the given array in descending order arr.sort(reverse=True) # return second largest number return arr[1] # Driver code if __name__ == '__main__': arr = [30, 15, 75, 7, 94, 45, 64, 22, 61] N = len(arr) print("The second smallest number in an array: ", secondSmallest(arr, N))
Output:
The second smallest number in an array: 75
Time Complexity: O(nlogn) where n is the size of an array, we are sorting the array which takes nlogn time.
Space Complexity: O(1) as we are not using any extra space.
Approach 2: Heap
In this approach, we will use max-heap to find second largest number in array. We know that the first element of the max-heap is always the largest one. So, we will remove the first elements from the max-heap and now the largest element present in the max-heap is our answer. Lets see a dry run of this approach to understand it better.
In the above image, we can see that we have inserted all the elements into the max-heap and all the elements are in sorted order.
Now, we will extract the first element from the max-heap.
Now, the second largest element is 75 here.
# python program to find second largest element in array using max-heap from heapq import heappush,heappop arr=[30, 15, 75, 7, 94, 45, 64, 22, 61] # create heap heap=[] n=len(arr) # insert all elements into heap for i in range(n): # by default heap is mean heap so we will make element negative to perform max heap heappush(heap,-1*arr[i]) # remove first max elements from the heap heappop(heap) ans=-heappop(heap) print("The second largest element in an array is:",ans)
Output:
The second largest element in an array is: 75
Time Complexity: O(n*log(n)) where n is the size of an array
Space Complexity: O(n)
Approach 3: QuickSelect Algorithm
In this approach, we will use the technique of the quicksort algorithm to find second largest number in array. Below are steps to find second largest number in array using the quickselect algorithm.
- First, choose any random position as a pivot position.
- Now, use the partition algorithm to split the array into two halves and find the correct position of the pivot.
- In the partition algorithm, all the elements are compared with the pivot, elements that are less than the pivot will be shifted to the left of the pivot, and elements that are greater than the pivot will be shifted to the right of the pivot.
- After performing the partition algorithm, all the elements left to the pivot are smaller than it, and all the elements right to the pivot are greater than it.
- Compare the index of pivot to 1.
- If the index matches then return the answer otherwise find other partition recursively.
# python program to find second largest element in array using quickselect def secondLargest(arr): left=0 right=len(arr)-1 ans=0 while(True): index=partition(arr,left,right) if index==1: ans=arr[index] break if index<1: left=index+1 else: right=index-1 return ans def partition(arr, left, right): pivot=arr[left] l=left+1 r=right while(l<=r): if arr[l]<pivot and arr[r]>pivot: arr[l],arr[r]=arr[r],arr[l] l+=1 r-=1 if arr[l]>=pivot: l+=1 if arr[r]<=pivot: r-=1 arr[left],arr[r]=arr[r],arr[left] return r arr = [30, 15, 75, 7, 94, 45, 64, 22, 61] N = len(arr) print("The second largest element in an array is:", secondLargest(arr))
Output:
The second largest element in an array is: 75
Time Complexity: Average time complexity O(n) Worst time complexity O(n^2)
Space Complexity: O(1)
Approach 4: Efficient Approach using Two Variables
In this approach, we will use two variables to keep track of the largest and second-largest elements so far. Let’s see an algorithm of this approach.
Algorithm:
- Initialize the largest and second_largest as min
- Start traversing the array,
- If the current element in the array say arr[i] is greater
than largest. Then update largest and second_largest as,
second_largest = largest
largest = arr[i] - If the current element is in between largest and second_largest,
then update second_largest to store the value of the current
variable as
second_largest = arr[i]
- If the current element in the array say arr[i] is greater
- Return the value stored of second_largest.
Lets see a dry run of this algorithm to understand it better.
arr= [30, 15, 75, 7, 94, 45, 64, 22, 61]
Initial largest = -2147483648, second_largest = -2147483648
i = 0:
arr[0] (30) >largest
largest = 30 (value of arr[0])
second_largest = -2147483648 (value of largest)
i = 1:
largest > arr[1] (15) > second_largest
largest = 30
second_largest = 15 (value of arr[2])
i = 2:
arr[1] (75) >largest
largest = 75 (value of arr[2])
second_largest = 30 (value of largest)
i = 3:
arr[3] (7) largest
largest = 94 (value of arr[4])
second_largest = 75 (value of largest)
i = 5:
arr[5] (45) < second_largest
largest = 94
second_largest = 75
i = 6:
arr[6] (64) < second_largest
largest = 94
second_largest = 75
i = 7:
arr[7] (22) < second_largest
largest = 94
second_largest = 75
i = 8:
arr[8] (61) < second_largest
largest = 94
second_largest = 75
Now, we can see that the second largest number is 75.
# python program to find second largest number in array def secondLargest(arr, n): if (n < 2): print(" Invalid Input ") return largest = second_largest = -2147483648 for i in range(n): if (arr[i] > largest): second_largest = largest largest = arr[i] elif (arr[i] > second_largest and arr[i] != largest): second_largest = arr[i] if (second_largest == -2147483648): print("There is no second largest element") else: print("The second largest element is", second_largest) arr = [30, 15, 75, 7, 94, 45, 64, 22, 61] n = len(arr) secondLargest(arr, n)
Output:
The second largest element is 75
Time Complexity: O(n)
Space Complexity: O(1)
FAQs Related To Find Second Largest Number in an Array
1) How to sort an array in reverse order in various languages?
Python: arr.sort(reverse = True)
Java: Arrays.sort(arr, Collections.reverseOrder())
C++: arr.sort(arr, arr+n, greater())
2) How to initialize heap data structure in different languages?
Python: heapq.heapify(heap)
Java: PriorityQueue pQueue = new PriorityQueue()
C++: priority_queue pq;
3) What is the best technique to find second largest number in array?
Out of the above-mentioned techniques last approach using two variables is the best technique to find second largest number in array because it always works in O(n) time complexity and the space complexity is also O
(1).