Leetcode discuss: 414. Third Maximum Number

Here is the post.

C# SortedSet and minimum heap warm up practice in June 2020

June 2, 2020
It is an easy level algorithm. I like to review the code I wrote back in 2018 and then warmup C# SortedSet and how to implement a minimum heap using SortedSet.

Case study
The algorithm is to find third largest number in the array; if there are less than three distinct numbers, return maximum one.

How to approach the problem? Let me walk throught the test case and explain the approach.
Given an integer array, [1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10].

Design a minimum heap using C# SortedSet, which is a set with unique values, but contains numbers sorted based on binary tree data structure. I will add some detail later.

The idea is to maintain a minimum heap with size three. If a new number is added to minimum heap, if the size is not less than 3, then the minimum one is removed from the heap. This is a little tricky, but it works perfect to translate "find third largest number" into "find minimum number in minimum heap in general".

Based on the integer array, [1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10], the first three numbers are added to heap, [1, 2, 3], the fourth number is not in heap, so 4 is added to heap, minimum one with value 1 is removed; continue to work on second 4, skipped; continue to work on 5, 5 is added to heap, minimum one 2 is removed, [3, 4 , 5], until last one 10, heap is [8, 9, 10], return minimum one, value 8.

Here are highlights:

1. Design a minimum heap using C# SortedSet;
2. If there is less than three distinct numbers in the array, return maximum one;
3. Always keep minimum heap size on check, make sure that it is less and equal to 3;
4. More on step 3, if the size of heap is bigger than three, remove minimum one;
5. Go over all the numbers in the array, put them to heap;
6. Remove smallest one at the end.

My 2018 practice is here.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_414_third_maximum_number_SortedSet
{
    class Program
    {
        /// <summary>
        /// code review: June 2, 2020
        /// </summary>
        public class MinHeap
        {
            /// <summary>
            /// use SortedSet to implement the minimum heap 
            /// Also, duplicate integer is removed from SortedSet. 
            /// </summary>
            public SortedSet<int> sortedSet = new SortedSet<int>();

            public void Add(int val)
            {                
                sortedSet.Add(val);                
            }

            /// <summary>
            /// SortedSet<int> default is in ascending order. 
            /// 
            /// </summary>
            /// <returns></returns>
            public int PopMin()
            {
                int minKey = sortedSet.First();

                sortedSet.Remove(minKey);

                return minKey;
            }
        }

        static void Main(string[] args)
        {
            var result = ThirdMax(new int[] { 2, 2, 3, 1 });
            var result2 = ThirdMax(new int[] { 1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10 });
            Debug.Assert(result2 == 8);
        }

        /// <summary>
        /// try to use MinHeap - August 15, 2018
        /// Requirement: 
        /// 1. Remove third maximum number;
        /// 2. If total of distinct numbers is less than three, remove maximum number. 
        /// Tips:
        /// 1. Design a minimum heap using C# SortedSet;
        /// 2. If there is less than three distinct numbers in the array, return maximum one;
        /// 3. Always keep minimum heap size on check, make sure that it is less and equal to 3;
        /// 4. More on step 3, if the size of heap is bigger than three, remove minimum one;
        /// 5. Go over all the numbers in the array, put them to heap;
        /// 6. Remove smallest one at the end. 
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public static int ThirdMax(int[] nums)
        {
            if (nums == null || nums.Length == 0)
                return -1;

            var length = nums.Length;
            var heap = new MinHeap();
           
            int index = 0;
            for (; index < length && heap.sortedSet.Count < 3; index++)
            {
                var current = nums[index];

                heap.Add(current);
            }

            // less than three distinct number in the array - return maximum one
            if (heap.sortedSet.Count < 3)
            {
                return heap.sortedSet.Last();
            }

            // heap.Set.Count = 3
            // Let us keep min heap size as 3 all the time
            // In other words, add one number to the heap, 
            // move the minimum one in the heap as well. 
            for (int i = index; i < length; i++)
            {
                var current = nums[i];
                if (heap.sortedSet.Contains(current))
                {
                    continue; 
                }

                heap.Add(current);
                heap.PopMin();                
            }

            return heap.PopMin();
        }
    }
}