Wednesday, May 10, 2017

Third Maximum Number

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Link to GitHub :Code

Example 1:
Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:
Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.
Git hub link : link


  • We need to have 3 variables max1, max2 and max3
  • In the initial 3 iteration all variables would be assigned null values based on the index 
          max1=n , max2=n max3=n
  • We need to check if n is greater than max1 . If yes then we need to swap the values
  • Next we need to check if  n is greater than max2
  • Finally we would get the third max number
package Algorithms.Arrays;

public class ThirdMaxNumber {
 public static int get(int [] arr)
 Integer max1=null;
 Integer max2=null;
 Integer max3=null;
 //loop through the array
 for(Integer n : arr)
  if(n.equals(max1) || n.equals(max2) || n.equals(max3))
  else if(max1==null || n> max1)
  else if(max2==null || n> max2)
  else if(max3==null || n> max3)
 return max3==null?max1 :max3;


No comments:

Post a Comment