Solution: Find Second Maximum Value in an Array

Let’s solve the Find Second Maximum Value in an Array problem.

We'll cover the following

Statement

Given an array of integers, nums, find the second maximum value from the array.

Constraints:

  • 2≤2 \leq nums.length ≤103\leq10^3

  • −105≤-10^5\leq nums[i] ≤105\leq10^5

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:

  1. Initialize two variables, firstMax and secondMax, both set to negative infinity. These variables will hold the first maximum and second maximum values found during the traversal of the array.

  2. Iterate through the array to find the first maximum:

    1. For each element in the array, if the current element is greater than firstMax, update firstMax to store the current element.

  3. Iterate through the array again to find the second maximum:

    1. For each element in the array, if the current element is not equal to firstMax and is greater than secondMax, update secondMax to store the current element.

  4. 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.