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

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.

Source: leetcode | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        

Solutions:
class Solution:

	def thirdMax(self, nums):
		nums = sorted(list(set(nums)))
		if len(nums) < 3:
			return max(nums)
		else:
			return nums[-3]


class Solution:

	def thirdMax(self, nums):
		v = [float('-inf'), float('-inf'), float('-inf')]
		for num in nums:
			if num not in v:
				if num > v[0]:
					v = [num, v[0], v[1]]
				elif num > v[1]:
					v = [v[0], num, v[1]]
				elif num > v[2]:
					v = [v[0], v[1], num]
		return max(nums) if float('-inf') in v else v[2]


class Solution:

	def thirdMax(self, nums):
		max3 = [nums[0], None, None]
		for i in range(1, len(nums)):
			if nums[i] in max3:
				continue
			if nums[i] > max3[0]:
				max3[2] = max3[1]
				max3[1] = max3[0]
				max3[0] = nums[i]
			elif max3[1] is None or nums[i] > max3[1]:
				max3[2] = max3[1]
				max3[1] = nums[i]
			elif max3[2] is None or nums[i] > max3[2]:
				max3[2] = nums[i]
			else:
				continue
		if None in max3:
			return max3[0]
		else:
			return max3[2]


class Solution:

	def thirdMax(self, nums):
		n = len(nums)
		m3 = [nums[0]]
		for y in nums[1:]:
			if m3[0] != y:
				if len(m3) == 1:
					if m3[0] > y:
						m3.append(y)
					else:
						m3.insert(0, y)
				elif m3[1] != y:
					if m3[0] < y:
						m3.insert(0, y)
					elif m3[1] < y:
						m3.insert(1, y)
					else:
						m3.append(y)
					break
		if len(m3) < 3:
			return max(m3)
		for y in nums[3:]:
			if y == m3[0] or y == m3[1] or y <= m3[2]:
				continue
			m3.pop()
			if y > m3[0]:
				m3.insert(0, y)
			elif y > m3[1]:
				m3.insert(1, y)
			else:
				m3.append(y)
		return m3[2]


class Solution:

	def thirdMax(self, nums):
		(max3, max2, max1) = (float('inf'), float('inf'), float('inf'))
		for num in nums:
			carry = num
			if max3 == carry or max2 == carry or max1 == carry:
				continue
			if max3 == float('inf'):
				max3 = carry
				continue
			elif max3 < carry:
				(max3, carry) = (carry, max3)
			if max2 == float('inf'):
				max2 = carry
				continue
			elif max2 < carry:
				(max2, carry) = (carry, max2)
			if max1 == float('inf'):
				max1 = carry
				continue
			elif max1 < carry:
				max1 = carry
		print((max3, max2, max1))
		return max1 if max1 != float('inf') else max3


class Solution:

	def thirdMax(self, nums):
		if len(nums) < 3:
			return max(nums)
		m1 = m2 = m3 = -2 ** 32
		for v in nums:
			if v == m1 or v == m2 or v == m3:
				continue
			if v > m1:
				(m1, m2, m3) = (v, m1, m2)
			elif v == m1 or v > m2:
				(m2, m3) = (v, m2)
			elif v == m2 or v > m3:
				m3 = v
		return m3 if m3 > -2 ** 32 else max(nums)


class Solution:

	def thirdMax(self, nums):
		if not nums:
			return None
		seen = set([])
		import heapq
		min_heap = []
		max_number = nums[0]
		for num in nums:
			if num not in seen:
				max_number = max(max_number, num)
				seen.add(num)
				if len(min_heap) == 3:
					if min_heap[0] < num:
						heapq.heappop(min_heap)
					else:
						continue
				heapq.heappush(min_heap, num)
		if len(min_heap) < 3:
			return max_number
		return heapq.heappop(min_heap)


class Solution:

	def thirdMax(self, nums):
		maxes = []
		for i in nums:
			if self.isNew(i, maxes):
				if len(maxes) < 3:
					maxes.append(i)
					maxes.sort()
				else:
					pos = self.findPos(i, maxes)
					if pos != None:
						maxes[pos] = i
						maxes.sort()
		if len(maxes) == 3:
			return maxes[0]
		else:
			return maxes[-1]

	def isNew(self, val, maxes):
		isNew = True
		for i in maxes:
			if val == i:
				isNew = False
		return isNew

	def findPos(self, val, maxes):
		for (ind, aMax) in enumerate(maxes):
			if val > aMax:
				return ind
		return None


class Solution:

	def thirdMax(self, nums):
		stack = [float('-inf'), float('-inf'), float('-inf')]
		for num in nums:
			if num > stack[0]:
				stack = [num, stack[0], stack[1]]
			elif num < stack[0]:
				if num > stack[1]:
					stack = [stack[0], num, stack[1]]
				elif num < stack[1]:
					if num > stack[2]:
						stack = [stack[0], stack[1], num]
		if stack[-1] == float('-inf'):
			return stack[0]
		return stack[-1]


class Solution:

	def thirdMax(self, nums):
		max_list = [None] * 3
		max_list[0] = nums[0]
		for num in nums[1:]:
			print(max_list)
			if num > max_list[0]:
				max_list[2] = max_list[1]
				max_list[1] = max_list[0]
				max_list[0] = num
			if max_list[1]:
				if max_list[0] > num > max_list[1]:
					max_list[2] = max_list[1]
					max_list[1] = num
				if max_list[2]:
					if max_list[1] > num > max_list[2]:
						max_list[2] = num
				elif max_list[1] > num:
					max_list[2] = num
			elif max_list[0] > num:
				max_list[1] = num
		return max_list[2] if max_list[2] is not None else max_list[0]


class Solution:

	def thirdMax(self, nums):
		R = []
		for n in nums:
			if n not in R:
				if len(R) < 3:
					R.append(n)
				elif min(R) < n:
					R.remove(min(R))
					R.append(n)
				R = sorted(R)
		return R[0] if len(R) == 3 else max(R)


class Solution:

	def thirdMax(self, nums):
		if not nums:
			return None
		nums = set(nums)
		if len(nums) < 3:
			return max(nums)
		max3 = [-float('inf'), -float('inf'), -float('inf')]
		for n in nums:
			if n > max3[0]:
				(max3[0], max3[1], max3[2]) = (n, max3[0], max3[1])
			elif n > max3[1]:
				(max3[1], max3[2]) = (n, max3[1])
			elif n > max3[2]:
				max3[2] = n
		return max3[2]


class Solution:

	def thirdMax(self, nums):
		a = b = c = -9999999999
		for n in nums:
			if n > c and n != b and (n != a):
				c = n
				if c > b:
					(b, c) = (c, b)
				if b > a:
					(a, b) = (b, a)
		if c == -9999999999:
			return a
		return c