Leetcode discuss: 215. Kth Largest Element in an Array

June 5, 2020

Here is the post.

C# SortedDictionary minimum heap practice II in June 2020

It is my second practice on this algorithm. I found out that my first practice has a unnecessary work to save -1 * element value in the array to minimujm heap. Here is the first practice. I think that my first practice shows weakness of my analytical skills using minimum heap; I should argue that minimum heap can deal with kth largest element algorithm perfectly, without using maximum heap.

Case study
Given an array, find kth largest element in the array. For example, array [1, 2, 3, 4, 5], k = 2, so kth largest element is value 4, index position = 3; We have to iterate all numbers in the array in order to find kth largest one.

If minimum heap is kept to size k, then kth largest one will be on top of minimum heap after last element is visited.

Kth largest element in the array can be solved using minimum heap, and heap size is also k. If k is not too largest, heap size is not an issue, then I just choose to go ahead to save element value in minimum heap; otherwise I can play the trick to save -1 * element value to reduce heap size.

Here are higlights:

1. Design a minimum heap and understand the importance to keep minimum heap size as k;
2. Use C# SortedDictionary<int, int> strong typing, value data type is count of same element value in the array;
3. Look into other C# data structure which may be best choice compared to SortedDictionary<int, int>

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
        /// For example, [1, 2, 3, 4, 5], kth largest element is 4 if k = 2; how to find 4? 
        /// All elements should be searched, last one is 5, kth one should be minimum one on the top. 
        /// The tricky part is to keep minimum heap size as k
        /// </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;            

            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 value = nums[i];
                size++;

                heap.Add(value);

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

            return heap.PopMin();
        }
    }
}

treesminimum heapc# sorteddictionary