Solution: Find Second Maximum Value in an Array
Let’s solve the Find Second Maximum Value in an Array problem.
Statement
Given an array of integers, nums
, find the second maximum value from the array.
Constraints:
nums.length
nums[i]
Solution 1: Traverse the array twice
The essence of the algorithm is to iteratively identify the maximum and second maximum elements in an array through two separate traversals. During the first traversal, identify the maximum element in the array. Subsequently, in the second traversal, locate the greatest element that is less than the maximum element found in the initial traversal.
Here are the steps of the algorithm:
Initialize two variables,
firstMax
andsecondMax
, both set to negative infinity. These variables will hold the first maximum and second maximum values found during the traversal of the array.Iterate through the array to find the first maximum:
For each element in the array, if the current element is greater than
firstMax
, updatefirstMax
to store the current element.
Iterate through the array again to find the second maximum:
For each element in the array, if the current element is not equal to
firstMax
and is greater thansecondMax
, updatesecondMax
to store the current element.
Return the value stored in
secondMax
.
Let’s look at the illustration below to better understand the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.