Leetcode discuss: 215. Kth Largest Element in an Array

Here is the post.

C# SortedDictionary minimum heap practice in 2020

June 4, 2020

Find kth largest element is very classical algorithm. I work on two tricky things to convert the problem into a minimum heap problem.

Warmup and best design talk

Let us walk through an example, how to design data structure heap for the help.
For example, integer array [1, 2, 3, 4, 5,6,7,8,9,10], k = 2
Minimum heap
Every number has to be went through, so the last one the heap should be [9, 10], the size is 2.
9 is the top of minimum heap.

Another example, still [1, 9, 2, 3, 4, 5, 6, 7, 8, 10], the last one the heap still should be [9, 10], the size is 2. Kth number is the top of heap.

The size of heap is important to find kth number in minimum heap. k = 2, heap size is 2.

If the array size is 10,000, number from 1 to 10,000, and then kth number is 9995, why we keep heap size as 9995, it is better to reverse the array in ascending order using -10,000 to -1. So the heap size can be 5 instead of 9995.

The exercise is warmup our design muscle and have a short break ice for real coding work.

Maximum heap
Since maximum heap can be processed using negative value of element array. We can stay with the minimum heap all the time.

Two tips
Work on a test case, array, [1, 2, 3, 4, 5], kth largest element, for example, 2th largest element is the fourth smallest element. Both are 4.

In order to apply kth largest element problem, it is to save -1 * element value. So largest one is converted into smallest one.If k is very big number close to size of array, then -1 * element will make sense, because n - k + 1 will be small integer, the minimum heap's size is small one.

Here are my highlights:

1. Design a minimum heap using SortedDictionary<int, int>, key is -1 * element value, value is count of element value; Notice that largest kth element not largest kth distinct element;
2. Write a class called MinHeap, two APIs, one is called Add(int val), second one is PopMin(), public property called sorted using SortedDictionary<int, int>;
3. Work on test case [1, 2, 3, 4,5], k = 2, 2th largest one is 4, and it is 4th smallest one. k -> n - k + 1 is the conversion mapping;
4. In order to get kth smallest minimum element, the heap size should be n - k + 1 at most.

Tips to share
I wrote a solution using minimum heap to find 814: third largest distinct element in the array, similar idea. The post is here.

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

namespace _215_kth_largest_element
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// First practice: June 4, 2020
        /// </summary>
        public class MinHeap
        {
            /// <summary>
            /// use SortedDictionary to implement the minimum heap              
            /// </summary>
            public SortedDictionary<int, int> sorted = new SortedDictionary<int, int>();

            public void Add(int val)
            {
                if (sorted.ContainsKey(val))
                {
                    sorted[val]++;
                }
                else
                {
                    sorted.Add(val, 1); 
                }
            }

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

                var count = sorted[minKey];
                if (count == 1)
                {
                    sorted.Remove(minKey);
                }
                else
                {
                    sorted[minKey]--;
                }

                return minKey;
            }
        }

        /// <summary>
        /// Find kth largest element in the array, not kth largest distinct element
        /// Save each element value * -1, so kth largest one will be (n - k + 1)th smallest one. 
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public int FindKthLargest(int[] nums, int k)
        {            
            if (nums == null || nums.Length == 0 || k < 0)
                return -1;

            k = nums.Length - k + 1; // convert largest kth to smallest 

            var length = nums.Length;
            var heap = new MinHeap();            
          
            // Let us keep min heap size as k all the time
            // In other words, add one number to the heap, 
            // move the minimum one in the heap as well if heap's size is bigger than k. 
            int size = 0; 
            
            for (int i = 0; i < length; i++)
            {
                var negativeValue = -1 * nums[i];
                size++; 

                heap.Add(negativeValue);

                if (size > k)
                {
                    heap.PopMin();
                }
            }

            return -1 * heap.PopMin();
        }
    }
}