algoadvance

Leetcode 414. Third Maximum Number

Problem Statement

Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.

Clarifying Questions

1. Can the array contain negative numbers?
   • Yes.
2. What if the array has less than three distinct numbers?
   • Return the maximum number in this case.
3. Are there any constraints on the length of the array?
   • The length of the array is between 1 and 10,000.

Strategy

1. Use Three Variables to Keep Track of the Top 3 Maximum Numbers:
   • Use three variables to maintain the first, second, and third maximums with initial values set to the minimum possible integer value (or set as undefined initially and handle accordingly).
2. Iterate Over the Array:
   • For each element:
     • Skip the element if it is equal to any of the current top three maximum values.
     • Update the top three maximums if the current element is greater than any of them, adjusting the values accordingly.
3. Check the State of the Third Maximum:
   • If the third maximum has been set (is not the initial value), return it.
   • Otherwise, return the first maximum.

Steps in the Logic:

1. Initialize three variables to represent the top three distinct maximum values.
2. Traverse the array, updating these variables based on the conditions described.
3. After the traversal, check and return the appropriate value.

Code

#include <vector>
#include <climits> // For INT_MIN

int thirdMax(std::vector<int>& nums) {
    long firstMax = LONG_MIN, secondMax = LONG_MIN, thirdMax = LONG_MIN;
    bool foundThird = false;
   
    for (int num : nums) {
        if (num == firstMax || num == secondMax || num == thirdMax) {
            continue;
        }
        
        if (num > firstMax) {
            thirdMax = secondMax;
            secondMax = firstMax;
            firstMax = num;
        } else if (num > secondMax) {
            thirdMax = secondMax;
            secondMax = num;
        } else if (num > thirdMax) {
            thirdMax = num;
            foundThird = true;
        }
    }
    
    return foundThird ? thirdMax : firstMax;
}

Time Complexity

• O(n): We traverse the array once, performing constant-time operations for each element.
  • The space complexity is O(1) since we are only using a fixed amount of extra space aside from the input array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?