Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in C#

Solution Review: Finding “K” Smallest Elements in the Array

Explore how to find the k smallest elements in an array using a minimum heap. Understand building the heap and repeatedly removing minimum values to obtain a sorted subset efficiently. This lesson helps you grasp the time complexity and implementation details essential for coding interviews in C#.

We'll cover the following...

Solution 1: removeMin() kk times

C#
using System;
using System.Collections.Generic;
namespace chapter_8
{
    class excercise_2
    {
        static List<int> findKSmallest(int[] arr, int size, int k)
        {
            MinHeap<int> heap = new MinHeap<int>();
            heap.buildHeap(arr, size);
            List<int> output = new List<int>();
            for (int i = 0; (i < k) && (i < size); i++)
            {
                output.Add(heap.getMin());
                heap.removeMin();
            }
            return output;
        }
        static void Main(string[] args)
        {
            int size = 7;
            int[] input = { 9, 4, 7, 1, -2, 6, 5 };
            int [] output = findKSmallest(input, size, 3).ToArray();
            for (int i = 0; i < output.Length; i++)
            {
                Console.Write(output[i] + " ");
            }
            return;
        }
    }
   
}

Here create a heap and then call the buildHeap (line 12) function to create a minimum heap from the given array. To find the k smallest elements in an array:

  • You get the minimum value from the heap.

  • Save the result to the vector output.

  • Remove the minimum value from the heap.

Repeat the same steps k times (provided k < size).

Time complexity

The time complexity of building a heap is ...