Solution: Find Second Maximum Value in a List

Let’s solve the Find Second Maximum Value in a List problem.

We'll cover the following

Statement

Given a list of integers, nums, find the second maximum value from the list.

Constraints:

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

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

Solution 1: Traverse the list twice

The essence of the algorithm is to iteratively identify the maximum and second maximum elements in a list through two separate traversals. During the first traversal, identify the maximum element in the list. 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, first_max and second_max, both set to negative infinity. These variables will hold the first maximum and second maximum values found during the traversal of the list.

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

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

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

    1. For each element in the list, if the current element is not equal to first_max and is greater than second_max, update second_max to store the current element.

  4. Return the value stored in second_max.

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.