Skip to main content

Array Basics

Find 2nd Maximum in Array

After identifying the maximum value in an array, the next step in some scenarios is to find the second-highest value. This could represent the runner-up score or the next best option in a dataset. Let’s explore how to determine the second maximum efficiently, ensuring we account for all edge cases.

Given an array of integers, we need to find the 2nd maximum element in the array. The function should print the 2nd maximum value found in the array. If no such value is found print -1.

Example

Input: nums = [3, 7, 11, 2, 1, 10]
Output: 10
Explanation: The 2nd maximum element in the array is 10

Input: nums = [3, 4, 1, 5, 2, 5, 1, 10]
Output: 5
Explanation: The 2nd maximum element in the array is 5.

Intuition

Imagine you're back in that queue, but now your goal is to find not just the tallest person but the second tallest. You start by assuming the first person you see is the tallest. As you move down the line, you keep track of the tallest person you've seen so far. But this time, you also need to keep track of the second tallest person.

How To Think About It

  • You begin by assuming the first person in line is both the tallest and the second tallest. However, as you move along the queue and find someone taller, you need to update both your tallest and second tallest. If the new person is taller than your current tallest, the previous tallest becomes the second tallest.
  • For each person in line, you compare them to your current tallest. If they are taller, you update your tallest to this new person, and the previous tallest becomes the second tallest. If they aren’t taller but still taller than your second tallest, you only update your second tallest.
  • By the time you reach the end of the queue, the person you’ve identified as the second tallest will be the second tallest in the entire line.

Applying This Intuition to the Array

  • Start by assuming the first element in the array is both the maximum and second maximum. This gives you a reference point, just like starting with the first person(in finding maximum problem)  in the queue.
  • As you traverse the array, compare each element with the current maximum and second maximum:
    • If the current element is greater than the maximum, update the second maximum to the previous maximum and update the maximum to the current element.
    • If the current element is not greater than the maximum but greater than the second maximum, then update the second maximum to the current element.
  • Continue this process until you’ve gone through all the elements. By the end, your second maximum variable will hold the second highest value in the array.

Let’s walk through an example:

Consider the array nums = [3, 7, 11, 2, 1, 10].

  • Start by assuming maxElement = 3 and secondMaxElement = INT_MIN (since there’s no valid second maximum at the start).

Why initialize the 2nd Maximum as INT_MIN?

Initializing a secondMaxElement with INT_MIN ensures that any valid array element will be larger, allowing it to be correctly updated during traversal. This approach handles cases where the array may contain very small or uniform values or there is no 2nd larger element. Without this, if no larger value is found, secondMaxElement might remain incorrectly initialized. This guarantees a valid comparison throughout the process.

Approach

The goal of the problem is to find the second maximum element in an array of integers. If there is no valid second maximum (e.g., if the array has fewer than two distinct elements), the function should return -1. Here's a detailed step-by-step approach to solving this problem:

  1. Initialization:
    • Start by initializing two variables maxElement and secondMaxElement to INT_MIN (the smallest possible integer). This ensures that even if all the elements are negative, we have a valid initial comparison comparison point.
      • maxElement will keep track of the largest element encountered so far.
      • secondMaxElement will store the second largest element.
  2. Iterate through the Array:

Loop through each element of the array using a for loop.

    • Condition 1 (If element is greater than maxElement):
        • If the current element is greater than maxElement, it means we've found a new largest element.
        • Update secondMaxElement to the old maxElement (since the previous largest element will now become the second largest).
        • Update maxElement to the current element (since it is now the largest).
    • Condition 2 (If element is between maxElement and secondMaxElement):
        • If the current element is smaller than maxElement but larger than secondMaxElement, update secondMaxElement to the current element.
        • This ensures that secondMaxElement always stores the second largest distinct value.
  1. Edge Case Handling:
    • After iterating through the array, if secondMaxElement is still INT_MIN, it means a valid second maximum wasn't found (i.e., the array has fewer than two distinct elements). In this case, print -1.
    • Otherwise, print the value of secondMaxElement.

4. Return the Result:

    • Print the second maximum element, or -1 if no valid second maximum exists.
0:00
/1:35

Dry Run

  1. Initialize Variables:
    • maxElement = INT_MIN (or -∞ in practical terms)
    • secondMaxElement = INT_MIN (or -∞)
  3. Start Iterating through the Array:First Iteration (i = 0):
    • nums[0] = 3
    • Check if nums[0] > maxElement → 3 > -∞, which is true.
    • So, update secondMaxElement = maxElement = -∞, and then maxElement = nums[0] = 3.
    • maxElement = 3, secondMaxElement = -∞
  5. Second Iteration (i = 1):
    • nums[1] = 7
    • Check if nums[1] > maxElement → 7 > 3, which is true.
    • So, update secondMaxElement = maxElement = 3, and then maxElement = nums[1] = 7.
    • maxElement = 7, secondMaxElement = 3
  7. Third Iteration (i = 2):
    • nums[2] = 11
    • Check if nums[2] > maxElement → 11 > 7, which is true.
    • So, update secondMaxElement = maxElement = 7, and then maxElement = nums[2] = 11.
    • maxElement = 11, secondMaxElement = 7
  9. Fourth Iteration (i = 3):
    • nums[3] = 2
    • Check if nums[3] > maxElement → 2 > 11, which is false.
    • Check if nums[3] > secondMaxElement && nums[3] < maxElement → 2 > 7 && 2 < 11, which is false.
    • No changes to maxElement or secondMaxElement.
    • maxElement = 11, secondMaxElement = 7
  11. Fifth Iteration (i = 4):
    • nums[4] = 1
    • Check if nums[4] > maxElement → 1 > 11, which is false.
    • Check if nums[4] > secondMaxElement && nums[4] < maxElement → 1 > 7 && 1 < 11, which is false.
    • No changes to maxElement or secondMaxElement.
    • maxElement = 11, secondMaxElement = 7
  13. Sixth Iteration (i = 5):
    • nums[5] = 10
    • Check if nums[5] > maxElement → 10 > 11, which is false.
    • Check if nums[5] > secondMaxElement && nums[5] < maxElement → 10 > 7 && 10 < 11, which is true.
    • So, update secondMaxElement = nums[5] = 10.
    • maxElement = 11, secondMaxElement = 10
  15. End of Iteration:
    • The loop ends after checking all elements of the array.
  17. Final Check:
    • Since secondMaxElement = 10, which is not equal to INT_MIN, we print the second maximum element: 10.

Final Output:
The second maximum element in the array is 10.

Code for All Languages
C++ 
// Function to find the 2nd maximum element in the array
void findSecondMaxElement(int nums[], int n) {
   
    // Initialize the maximum and second maximum with the smallest possible value
    int maxElement = INT_MIN;
    int secondMaxElement = INT_MIN;

    // Iterate through the array to find the maximum element
    for (int i = 0; i < n; ++i) {
        if (nums[i] > maxElement) {

            // Update second maximum
            secondMaxElement = maxElement;

            // Update maximum
            maxElement = nums[i];
        }
        else if (nums[i] > secondMaxElement && nums[i] < maxElement) {

            // Update second maximum if it's less than maxElement and
            // greater than the current secondMaxElement
            secondMaxElement = nums[i];
        }
    }

    // Check if a valid second maximum was found
    if (secondMaxElement == INT_MIN) {

        // Print -1 if no valid second maximum found
        cout << -1 << endl;
    }
    else {

        // Print the 2nd maximum element found in the array
        cout << secondMaxElement << endl;  
    }
}

Java 
public class LearnYard {
    // Function to find the 2nd maximum element in the array
    public static void findSecondMaxElement(int[] nums, int n) {
    
        // Initialize the maximum and second maximum with the smallest possible value
        int maxElement = Integer.MIN_VALUE;
        int secondMaxElement = Integer.MIN_VALUE;

        // Iterate through the array to find the maximum element
        for (int i = 0; i < n; ++i) {
            if (nums[i] > maxElement) {
            
                // Update second maximum
                secondMaxElement = maxElement;
                
                // Update maximum
                maxElement = nums[i];
            } 
            else if (nums[i] > secondMaxElement && nums[i] < maxElement) {
            
                // Update second maximum if it's less than maxElement and greater than the current secondMaxElement
                secondMaxElement = nums[i];
            }
        }

        // Check if a valid second maximum was found
        if (secondMaxElement == Integer.MIN_VALUE) {
            System.out.println(-1);
        } 
        else {
            // Print the 2nd maximum element found in the array
            System.out.println(secondMaxElement);
        }
    }
}

Python 
# Function to find the 2nd maximum element in the array
def findSecondMaxElement(nums, n):

    # Initialize the maximum and second maximum with the smallest possible value
    maxElement = float('-inf')
    secondMaxElement = float('-inf')

    # Iterate through the array to find the maximum element
    for num in nums:
        if num > maxElement:
        
            # Update second maximum
            secondMaxElement = maxElement
            
            # Update maximum
            maxElement = num
        elif num > secondMaxElement and num < maxElement:
        
            # Update second maximum if it's less than maxElement and greater than the current secondMaxElement
            secondMaxElement = num

    # Check if a valid second maximum was found
    if secondMaxElement == float('-inf'):
        print(-1)
    else:
        # Print the 2nd maximum element found in the array
        print(secondMaxElement)

Javascript 
// Function to find the 2nd maximum element in the array
function findSecondMaxElement(nums, n) {
  
    // Initialize the maximum and second maximum with the smallest possible value
    let maxElement = -Infinity;
    let secondMaxElement = -Infinity;

    // Iterate through the array to find the maximum element
    for (let i = 0; i < n; ++i) {
        if (nums[i] > maxElement) {
          
            // Update second maximum
            secondMaxElement = maxElement;
          
            // Update maximum
            maxElement = nums[i];
        } else if (nums[i] > secondMaxElement && nums[i] < maxElement) {
          
            // Update second maximum if it's less than maxElement and greater than the current secondMaxElement
            secondMaxElement = nums[i];
        }
    }

    // Check if a valid second maximum was found
    if (secondMaxElement === -Infinity) {
        console.log(-1);
    } else {
        // Print the 2nd maximum element found in the array
        console.log(secondMaxElement);
    }
}

Time Complexity

We need to traverse all n elements in the array exactly once. During this single pass through the array, we compare each element to find the maximum and second maximum elements.Each comparison operation (to update maxElement or secondMaxElement) takes constant time, O(1). Since these operations are repeated for every element in the array.The overall time complexity remains O(n).

Space Complexity

The total space complexity consists of two parts: the space required for the input array and the auxiliary space used by the algorithm.

Total Space Complexity:The total space complexity is O(n) because the input array nums[] takes up O(n) space. This is necessary to store the n elements.

Auxiliary Space Complexity:The auxiliary space complexity is O(1). This is because we only use a constant amount of extra space, specifically for the variables maxElement and secondMaxElement. These variables do not depend on the size of the array and therefore take up constant space.