Minimum jumps to reach at end

Minimum jumps to reach end of array

Given an array of integers, find minimum jumps to reach end of the array. Condition is that you can maximum jump a[i] indices from index i.

For example, in following array, minimum jumps required are 2.

Original array

At index 1, we can either jump 0, 1 or 2 indices ahead. If we jump 2 indices, we would require two more jumps (at 1 and 1) to reach at 4. So total number of jumps would be 3.

You jump maximum at start, but at the end, more number of jumps required.

However if we jump only 1 index ahead, next A[i] will allow us to jump 3 indices ahead, doing so we will reach at the end of the array. So minimum number of jumps to reach at the end of array is 2.

minimum jumps required
Not starting with maximum jump actually save one jump to reach at the end

Minimum number of jumps : thought process

What would be the brute force method to solve this? At each index, you try all possible jumps and get the combination which gives you the minimum jumps. This method will have exponential complexity which we do not want.

What is the original problem? It’s minJumps(start, end) Of all the jumps possible from start, let’s say we go to index k, then what how does problem reduces? Well, now we have to find minimum number of jumps from k to end. How to decide on k now? We try all k values from start+1 to start + a[i].

minJumps(start, end) = Min ( minJumps(k, end) )
for all k reachable from start 

Now, we have clear recursion relationship, what should be the base case? When k + A[k] > end, or k == end, we should return 1 as there would be only one jump required from k to end now.

package com.company;

/**
 * Created by sangar on 10.10.18.
 */
public class MinimumJumps {

    public int minimumNumberOfJump(int[] a, int start, int end){
        //If start == end, we reached the end, return 0.
        if(start == end) return 0;

        //if current element is 0, you cannot jump to end at all
        if(a[start] == 0) return Integer.MAX_VALUE;

        int minimumJumps = Integer.MAX_VALUE;

        for(int k=start+1; k<=start+a[start] && k<=end; k++){
            /*
            For each K from start+1 to end, find the minimum jumps.
             */
            int jumps = minimumNumberOfJump(a,k,end);
            if(jumps != Integer.MAX_VALUE && jumps + 1 <; minimumJumps){
                minimumJumps  = jumps + 1;
            }
        }
        return minimumJumps;
    }
}

Test cases for above function

package test;

import com.company.MinimumJumps;
import org.junit.jupiter.api.Test;

import static org.junit.Assert.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class MinimumJumpTest {

    MinimumJumps tester = new MinimumJumps();

    @Test
    public void baseTest() {

        int[] a = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
        assertEquals(3,
			tester.minimumNumberOfJump(a,0, a.length-1));
    }

    @Test
    public void arrayContainsZeroTest() {

        int[] a = {1, 3, 0, 0, 0, 2, 6, 7, 6, 8, 9};
        assertEquals(Integer.MAX_VALUE, 	  
			tester.minimumNumberOfJump(a,0, a.length-1));
    }

    @Test
    public void nullArrayTest() {

        assertEquals(0, tester.minimumNumberOfJump(null,0, 0));
    }

    @Test
    public void arrayWithTwoElementsTest() {

        int[] a = {1, 0};
        assertEquals(1,
			tester.minimumNumberOfJump(a,0, a.length-1));
    }
}

Let’s see execution trace of above function for an input.

Nodes in red are re-calculated

From the above execution tree, we notice that some subproblems are calculated again and again. This is typically known as overlapping subproblems.
Also, optimal solution to subproblem actually lead us to optimal solution for original problem which is optimal subproblem structure. These two property are must to apply dynamic programming to a problem.

What if we store minimum number of jumps required to reach a particular index. To reach first index, jumps required is 0. Jump[i] represents the number of reach index i. Solution to reach at the end of the array would be Jump[n-1]. How do we feel this array? For each i,  from  j = 0 to i-1 and check if j+a[j] <= i, if yes, update jump[i] = min (jump[i], jump[j]+1).

Minimum number of jumps: dynamic programming approach

package com.company;

/**
 * Created by sangar on 10.10.18.
 */
public class MinimumJumps {

    public int minimumNumberOfJumpDP(int[] a){

        if(a == null || a.length == 0) return 0;

        if(a[0] == 0) return Integer.MAX_VALUE;

        int[] jump = new int[a.length];

        //no jumps required for first element
        jump[0] = 0;

        for(int i=1; i<a.length;i++){
            jump[i] = Integer.MAX_VALUE;

            for(int j=0; j<i; j++){
                if(j+a[j]>=i && jump[j] != Integer.MAX_VALUE ){
                    jump[i] = Integer.min(jump[i], 1 + jump[j]);
                }
            }
        }
        return jump[a.length-1];
    }
}

Complexity of dynamic programming approach to find minimum number of jumps to reach end of an array is O(n2) with space complexity of O(n)

If you are interested to solve this problem in O(n) time, please visit stack overflow discussion 

Please share if there is something wrong or missing. If you are interested in taking coaching from one of our experienced teachers, please reach out to us at communications@algorithmsandme.com

Find peak in array (local maxima)

Peak in array

Given an unsorted array, find a peak in array. A peak is defined as an element which is not smaller than its immediate neighbors. In an unsorted array, there can be many such peaks, referred to as local Maxima. Mathematically, ith element is called as peak following property holds true:

A[i-1] <= A[i] >=A[i+1]

For first element and last elements of array, left and right neighbors respectively, are considered as negative infinity.

A[0] = A[n] = -infinity

For example, peak in following array would be 6 or 7

Can you identify the peak in this array?

What would be peak in sorted array? It will be the last element of array and similarly, for reverse sorted array, first element will be peak.

Peak  in array : Thought process

I recommend two things: First, get your pen and paper to practice this problem yourself. Second, try to come up with brute force solution as soon as possible. Why? Because it adds to your confidence, when you have some solution already in hand.

Brute force approach to find peak in an array of integers will be to scan through it and for each element, check if greater than it’s greater than previous and next element.  If it is, return index of that element. In worst case we would end up scanning whole array (in a sorted array), so worst case complexity of brute force solution is O(N)

Obviously, this would not have been an interview question, if expectation was to solve it in O(N) complexity, anyone with basic programming knowledge can solve it. There is no way to differentiate a good candidate from an average based on this question then. However, interviewer expects you to solve it in better than O(N) complexity and that’s where problem becomes interesting.

What if we do not go linear and randomly check index m for local maxima? If it is local maxima, we are good, return the index of that element. If it is not peak and given that array is unsorted, three situations possible at that index :
1. Array is rising toward right, that means, next element is greater than current and it’s previous element.

2.  Array is falling towards right, that means, next element is less than current and it’s previous element.

3.  It’s a valley, where current element is less than both previous and next element.

In first situation, maximum should be on the right side of current index, why? In second situation, peak will be in left side of current index.

If A[m] < A[m+1], A[m] cannot be peak. However, if A[m+2] is less than A[m+1] is less than A[m+1], then A[m+1] can be a peak or some subsequent element can be. In worst case it would be the last element of array if whole A[m..end] is sorted.
If A[m] < A[m-1], in that case, either A[m-1] is peak or some element preceding it can surely be. In worst case, first element will be the peak.

Algorithm to find peak in array

Now question is how to select m? We want to minimize the worst case number of elements to check after splitting, which is possible by splitting the array in middle. Take mid as the starting point, this is classic case of divide and conquer  approach as we will discard half of the array based on certain condition.

  1. Find mid = low + (high-low)/2
  2. If A[mid-1] <= A[mid] =>A[mid+1], then return mid
  3. If A[mid-1] > A[mid], high = mid-1
  4. If A[mid+1] > A[mid], low = mid+1
  5. Repeat step 1 to 4 till there are more than one element in array. Else return that last element.

Let’s take an example and see if this algorithm works. We have given array a as below

peak in array example

Find mid and see if mid is peak we are looking for, in this case it is not as A[mid] is less than A[mid+1].We will discard left subarray and look for peak in right subarray starting from mid+1.

New low and high are shown, we find new mid. Is new mid, local maxima? No, as it is less than previous and next element, it is valley. We will discard right subarray and look for peak in left subarray.

Now, there is only one element, hence it should be peak in array.

peak in array example

Peak in array : Implementation

package com.company;

/**
 * Created by sangar on 25.3.18.
 */
public class BinarySearcchAlgorithm {

    public  static int findPeak(int[] a){
        int low = 0;
        int high = a.length-1;

        while (low<high){
            int mid = low + (high-low)/2;
            if(mid == low ) return a[low] > a[high] ? low:high;

            //If mid is local maxima, return it.
            if(a[mid-1] <= a[mid]
                    && a[mid] >= a[mid+1]) return mid;
            //Discard right subarray
            else if(a[mid-1] > a[mid]) high = mid-1;
            //Discard left subarray
            else low = mid+1;
        }
        return low;
    }

    public static void main(String[] args) {
        int[] input = {1,2,6,5,3,7,4};

        int index = findPeak(input);
        System.out.print("Peak found at : " + index);
    }
}

Always remember to check for array with two elements, that will catch almost all bugs regarding boundary overflow. Also, notice that since we are accessing mid+1 and mid-1 indices of array, make sure that these indices are within bounds of array. These two things are very important for a solution to be correct and acceptable in interview. Also, to understand more about binary search algorithm and how it works, please refer to Binary search algorithm

Complexity of divide and conquer algorithm to find peak in unsorted array is O(log n). Recurrence relation for this would be T(n) = T(n/2) + c

Please share if there is something wrong or missing. If you want to contribute to website and help others to learn, please reach out to us on communications@algorithmsandme.com

Move all zeros at the end of the array

Move all zeros at the end of the array

Given an array, which contains random numbers, including zero. We have to move all zeros at the end of the array. For example input array is

Output array is

Basic idea is to scan through array, whenever we find a zero, move all successive elements accordingly. We wont be moving all elements every time we hit zero. Trick is similar to problem where we delete specific characters from a string. For complete explanation refer to this post. For above example, at some point, below will be state of array and other variables

By the time we reach at the end of the array, we may have a difference between the last element of the array and size of the given input array. That will be the number of zeros in the input array. Fill all those spots with zero.

#define MAX_ELEM 10
void move_zeroes(int a[], int size){
    int i, dest = 0;

    for(i =0; i<size; i++){
        if(a[i] != 0){
            a[dest++] = a[i];
        }
    }
    for(i= dest; i<size; i++){
        a[i] = 0;
    }
    printf("\n");
    for(i= 0; i<size; i++){
        printf("%d ", a[i]);
    }
}

int main(){
    int a[] = {0,1,3,4,0,0,0,5,6,7};
    int size = sizeof(a)/sizeof(a[0]);
    move_zeroes(a, size);
    return 0;
}

Simple it is O(N). There is another problem which can be solved with the same approach. Problem is to delete consecutive duplicate elements except the first in an array. For example, input array is { 0,1,1,3,3,5,0,0,6,6}  {0,1,3,5,0,6}

Find k number in sliding window problem

Sliding window problem

Given a large integer array of size x, window size of n and a random number k, find smallest k numbers in every window of n elements in array. This is commonly know as sliding window problem. For example: for an array [2,3,1,5,6,4,2,5,4,3,8] k = 2 and n = 6, output should be [1,2],[1,2],[1,3][1,4][1,3][1,3]. How? see below figure.

This problem regularly features in Amazon interviews.

Find k numbers in sliding window : thoughts

If we spit down the problem, it reduces to find k smallest elements in an array, which can easily be solve in multiple ways. All we have to take care of is moving the window and storing results for each window.

Quick sort method
First way is to use quick sort, we randomly pick a pivot and put it in right place. When pivot is at right place, all elements on the right side of pivot are greater than pivot and all elements on the left side are less than pivot. If pivot is a kth position in array, all elements on left side of pivot automatically become K smallest elements of given array. In worst case this method take O(n log n) for each window.

Using heaps
What are we interested in is k elements, what if from current window, we take out first k numbers and consider them as k smallest elements? This set of k numbers may change based value of following numbers in the window. Which way? If new number is smaller than any of the number chosen randomly, new number has to be added into the k smallest element set. However, we have only k spaces there, so someone has to move out.

If new number is less than any number in set, it must be less than maximum number in set

Given above fact, we can always swap new number with maximum of set. Now problem is how to find max in a set? This set will modified repeatedly, so we cannot just sort it once and find the max. For use cases when data is changing and we have to find max of that set, heaps are the best data structures to use. In this case we will use max heap. Max heap is kind of heap where children of root node are smaller than root node. Max heap will give us O(1) complexity to find max and O(log n) complexity to heapify on removal old max and insertion of new number.

Algorithm

  1. Create a max heap with first k elements of window.
  2. Scan through remaining elements in window
    1. If root of max heap is less than new number, remove the root and add new element to heap
    2. All elements in heap at the end of processing are k smallest numbers in window.

    Sliding window algorithm to find k smallest elements : Implementation

    #include<stdio.h>
    #include<stdlib.h>
    #include <math.h>
    
    typedef struct node {
    	struct node * left;
    	struct node * right;
    	int data;
    } heapNode;
    
    int leftChild(int i){
    	return 2*i + 1;
    }
    
    int rightChild(int i){
    	return 2*i + 2;
    }
    
    void swapPtr(heapNode *a[], int i, int largest){
    	heapNode *temp = a[i];
    	a[i] = a[largest];
    	a[largest] = temp;
    }
    /* This function heapifies heap after removal of root  
    or at time of building heap from an array */
    void max_heapify_ptr(heapNode *a[], int i, int len){
            int largest = i;
            int left, right;
    
            left = leftChild(i);
            right = rightChild(i);
           
            if(left <= len && a[i]->data <a[left]->data){
                    largest = left;
            }
            if(right <= len && a[largest]->data < a[right]->data){
                    largest = right;
            }
            if(largest != i){
                    swapPtr(a, i, largest);
                    max_heapify_ptr(a, largest, len);
            }
    }
    
    /* Building heap from given elements */
    void build_max_heap_ptr(heapNode *a[], int len){
            int i = len/2 +1;
            for(; i>=0; i--){
                    max_heapify_ptr(a,i, len);
            }
    }
    
    /* This function allocates node of heap */
    heapNode * create_node(int data){
            heapNode *node = (heapNode *)(malloc)(sizeof(heapNode));
            if(node){
                    node->data = data;
            }
            return node;
    
    }
    
    /* This function is real implementation of 
    the sliding window algorithm */
    void slide_window(int buffer[], int N, int K, int buffer_len){
    
        int i =0, j =0,s;
        heapNode *max_heap[K+1];
        int num = K;
    
        for(j=0 ; j + N < buffer_len; j++){
          /* Window starts at index 0 and is of size N */
           printf("\nCurrent window :");
           for(s =j; s<j+N; s++){
               printf("%d ", buffer[s]);
           }
           printf("\n");
           /* Put K element from N element window */
           for(i=0;i<K; i++){
           /* Since we wold be doing for every window, 
              avoiding reallocation of node */
               if(max_heap[i]){
                    max_heap[i]->data = buffer[i+j];
                }
                else{
                    max_heap[i] = create_node(buffer[i+j]);
                }
            }
            /* Build min heap with those entered elements */
             build_max_heap_ptr(max_heap,K-1);
    
            /*Now for all remaining N-K-1 elements in window, 
             check if they fit in max heap */ 
             for(i=K+j; i< N+j; i++){
                 heapNode * root = max_heap[0];
                 if(buffer[i] < root->data){
                       root->data = buffer[i];
                       max_heapify_ptr(max_heap, 0, K-1);
                  }
              }
              
              /*Print the current max heap, it will contain K smallest 
                element in current window */
               printf("K minimum elements in this window :");
               for(int x=0; x< K; x++){
               	printf("%d ", max_heap[x]->data);
               }
               
               
            }
    }
    /* Driver Program to execute above code */
    int main(){
       int buffer[10] = {1,4,5,6,3,2,4,8,9,6};
    
       int K= 4;
       int N =5;
       
       int size = sizeof(buffer)/ sizeof(buffer[0]);
       
       slide_window(buffer,N, K,size);
       return 0;
    }
    

    Following figures explain how window slides and how heap is updated.
    1. Window starts at index 0 and ends at N. We take K minimum elements among N elements and store in max heap. Array is given in below picture with window size of 9 and k = 4.
    First step is to create a max heap with first 4 elements of window.

    sliding window problem

    Next we are looking at 4, which is less than max in max heap. So we remove the max from heap and add the new element(4) to heap.

    k smallest element in sliding window

    Next is 2, which is less than max in max heap. So we remove the max from heap and add the new element(2) to heap.

    Next is 3, which is less than max in max heap. So we remove the max from heap and add the new element(3) to heap.

    Next we have 10 and 11 which are greater than root of max heap, so nothing happens.

    We come to end of window. Therefore, 4 smallest element in window are [ 1,2,3,4 ]

    Next window moves one step ahead, that’s where you discard the max heap and create the new empty one and repeat the process.

    We can actually avoid discarding the entire heap when window moves, however complexity of overall algorithm will remain the same. This problem is asked in a different way, which is to find maximum in sliding window.

    #include <iostream>
    #include<deque>
    using namespace std;
    
    void slidingWindow(int buffer[], int n, int w, int output[])
    {
       deque<int> Q;
       int i;
       /*Initilize deque Q for first window, put all W elements, however also
       removing elements which cannot be maximum in this window */
       for (i = 0; i < w; i++)
       {
       	   //This is where we are removing all less than elements
           while (!Q.empty() && buffer[i] >= buffer[Q.back()])
               Q.pop_back();
           // Pushing the index
           Q.push_back(i);
       }
      
       for (i = w; i < n; i++)
       {
           output[i-w] = buffer[Q.front()];
    
           //update Q for new window
           while (!Q.empty() && buffer[i] >= buffer[Q.back()])
               Q.pop_back();
    
           //Pop older element outside window from Q    
           while (!Q.empty() && Q.front() <= i-w)
               Q.pop_front();
          
           //Insert current element in Q
           Q.push_back(i);
       }
       output[n-w] = buffer[Q.front()];
    }
    
    int main(){
    	int a[]={3,5,4,2,-1,4,0,-3};
    	int n = sizeof(a)/sizeof(a[0]);
    	int output[n];
    
    	slidingWindow(a,n,4,output);
    	return 0;
    }
    

    Worst case complexity of sliding window algorithm would be O(n2k). K is included as it takes O(k) complexity to build heap of k elements.

    Please share if there is something wrong or missing.

Find Kth smallest element in array

Kth smallest element in array

Given an array of integers which is non sorted, find kth smallest element in that array. For example: if input array is A = [3,5,1,2,6,9,7], 4th smallest element in array A is 5, because if you sort the array A, it looks like A = [1,2,3,5,6,7,9] and now you can easily see that 4th element is 5.

This problem is commonly asked in Microsoft and Amazon interviews as it has multiple layers and there is some many things that can be measured with this one problem.

Kth smallest element : Line of thought

First of all, in any interview, try to come up with brute force solution. Brute force solution to find Kth smallest element in array of integers would be to sort array and return A[k-1] element (K-1 as array is zero base indexed).

What is the complexity of brute force solution? It’s O(n2)? Well, we have sort algorithms like merge sort and heap sort which work in O(n log n) complexity. Problem with both searches is that they use additional space. Quick sort is another sort algorithm. It has problem that it’s worst case complexity will be O(n2), which happens when input is completely sorted.
In our case, input is given as unsorted already, so we can expect that quick sort will function with O(n log n) complexity which is it’s average case complexity. Advantage of using quick sort is that there is no additional space complexity.

Optimising quick sort

Let’s see how quick sort works and see if we can optimize solution further?
Idea behind quick sort is to find correct place for the selected pivot. Once pivot is at correct position, all the elements on left side of pivot are smaller and on right side of pivot are greater than pivot. This step is partitioning.

If after partitioning, pivot is at position j, can we say that pivot is actually jth smallest element of the array? What if j is equal to k? Well problem solved, we found the kth smallest element.

If j is less than k, left subarray is less than k, we need to include more elements from right subarray, therefore kth smallest element is in right subarray somewhere. We have already found j smallest elements, all we need to find is k-j elements from right subarray.

What if j is greater than k? In this case, we have to drop some elements from left subarray, so our search space would be left subarray after partition.

Theoretically, this algorithm still has complexity of O(n log n), but practically, you do not need to sort the entire array before you find k smallest elements.

Algorithm to find K smallest elements in array

  1. Select a pivot and partition the array with pivot at correct position j
  2. If position of pivot, j, is equal to k, return A[j].
  3. If j is less than k, discard array from start to j, and look for (k-j)th smallest element in right sub array, go to step 1.
  4. If j is greater than k, discard array from j to end and look for kth element in left subarray, go to step 1

Let’s take an example and see if this algorithm works? A =  [4, 2, 1, 7, 5, 3, 8, 10, 9, 6 ], and we have to find fifth smallest element in array A.

Kth smallest element in array

Start with pivot as first index of array, so pivot = 0, partition the array into two parts around pivot such that all elements on left side of pivot element, i.e. A[pivot] are smaller and all elements on right side are greater than A[pivot].

Start with pivot as first index of array, so pivot = 0, partition the array into two parts around pivot such that all elements on left side of pivot element, i.e. A[pivot] are smaller and all elements on right side are greater than A[pivot].

In our example, array A will look like below after pivot has found it’s correct position.

k smallest element
After partition, correct position of pivot is index 3

If pivot == k-1 (array is represented as zero base index), then A[pivot] is kth smallest element. Since pivot (3) is less than k-1 (4), look for kth smallest element on right side of the pivot.

k remains as it is as opposed to k-j mentioned in algorithm as pivot is given w.r.t entire array and not w.r.t subarray.

In second iteration, pivot = 4 (index and not element). After second execution of quick sort array A will be like

After partition of right subarray, correct position of pivot is index 4

pivot(4) which is equal to k-1(5-1). 5th smallest element in array A is 5.

Implementation

package com.company;

/**
	* Created by sangar on 30.9.18.
*/
public class KthSmallest {
	private void swap(int[] a, int i, int j){
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	private int partition(int[] a, int start, int end){
		int pivot = a[start];
		int i  = start+1;
		int j  = end;

		while(i < j){
			while(a[i] < pivot) i++;
			while(a[j] > pivot) j--;

			if(i < j) {
				swap(a, i, j);
			}
		}
		swap(a, start, j);
		return j;
	}

	public int findKthSmallestElement(int a[], int start, 
				int end, int k){
		if(start < end){
		int p = partition(a, start, end);
		if(p == k-1){
			return a[p];
		}
		if(p > k-1)
			return findKthSmallestElement(a, start, p, k);
		if(p < k-1)
			return findKthSmallestElement(a, p+1, end, k);
		}
		return -1;
	}
}
package test;

import com.company.KthSmallest;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 28.8.18.
 */
public class KthSmallestTest {

	KthSmallest tester = new KthSmallest();
	private int[] a = {4, 2, 1, 7, 5, 3, 8, 10, 9};
	@Test
	public void kthSmallest() {
		assertEquals(7, tester.findKthSmallestElement(a,0,8,6));
	}

	@Test
	public void firstSmallest() {
		assertEquals(1, tester.findKthSmallestElement(a,0,8,1));
	}

	@Test
	public void lastSmallest() {
		assertEquals(10, tester.findKthSmallestElement(a,0,8,9));
	}

	@Test
	public void kGreaterThanSize() {
		assertEquals(-1, tester.findKthSmallestElement(a,0,8,15));
	}
	@Test
	public void emptyArray() {
		int[] a = {};
		assertEquals(-1, tester.findKthSmallestElement(a,0,0,1));
	}

	@Test
	public void nullArray() {
		assertEquals(-1, tester.findKthSmallestElement(null,0,0,1));
	}
}

Complexity of using quick sort algorithm to find kth smallest element in array of integers in still O(n log n).

Kth smallest element using heaps

Imagine a case where there are a billion integers in array and you have to find 5 smallest elements from that array. Complexity of O(n log n) is too costly for that use case. Above algorithm using quick sort does not take into consideration disparity between k and n.

We want top k elements, how about we chose those k elements randomly, call it set A and then go through all other n-k elements, call it set B, check if element from set B (n-k elements) can displace element in set A (k elements)?

What will be condition for an element from set B to replace an element in set A? Well, if the new element is less than maximum in set A, than maximum in set A cannot be in set of k smallest elements right?  Maximum element in set A would be replaced by the new element from set B.

Now, problem is how to quickly find maximum out of set A. Heap is the best data structure there. What kind of heap: min heap or max heap? Max heap as it store the maximum of set at the root of it.

Let’s defined concrete steps to find k smallest elements using max heap. 

  1. Create a max heap of size k from first k elements of array.
  2. Scan all elements in array one by one.
    1.  If current element is less than max on heap, add current element to heap and heapify.
    2. If not, then go to next element.
  3. At the end, max heap will contain k smallest elements of array and root will be kth smallest element.

Let’s take an example and see if this algorithm works? Input array is shown below and we have to find 6th smallest element in this array.

kth smallest element using heaps
input array

Step 1 : Create a max heap with first 6 elements of array.

Create a max heap with set A

Step 2 : Take next element from set B and check if it is less than root of max heap. In this case, yes it is. Remove the root and insert the new element into max heap.

Element from set B removes root from max heap and added to max heap

Step 2 : It continues to 10, nothing happens as new element is greater than root of max heap. Same for 9.  At 6, again root of max heap is greater than 6. So remove the root and add 6 to max heap.

Again, new element from set B is less than root of max heap. Root is removed and new element is added.

Array scan is finished, so just return root of max heap, 6 which is sixth smallest element in given array.

	public int findKthSmallestElementUsingHeap(int a[], int k){
	//https://stackoverflow.com/questions/11003155/change-priorityqueue-to-max-priorityqueue
	PriorityQueue<Integer>  maxHeap =
			new PriorityQueue<>(k, Collections.reverseOrder());

		if(a == null || k > a.length) return -1;
		//Create max with first k elements
		for(int i=0; i<k; i++){
			maxHeap.add(a[i]);
		}
		/*Keep updating max heap based on new element
		If new element is less than root, 
		remove root and add new element
		*/
		for(int i=k; i<a.length; i++){
			if(maxHeap.peek() > a[i]){
				maxHeap.remove();
				maxHeap.add(a[i]);
			}
		}
		return maxHeap.peek();
	}

Can you calculate the complexity of above algorithm? heapify() has complexity of log(k) with k elements on heap. In worst case, we have to do heapify() for all elements in array, which is n, so overall complexity of algorithm becomes O(n log k). Also, there is additional space complexity of O(k) to store heap.
When is very small as compared to n, this algorithm again depends on the size of array.

We want k smallest elements, if we pick first k elements from a min heap, will it solve the problem? I think so. Create a min heap of n elements in place from the given array, and then pick first k elements.
Creation of heap has complexity of O(n), do more reading on it. All we need to do is delete k times from this heap, each time there will be heapify(). It will have complexity of O(log n) for n element heap. So, overall complexity would be O(n + k log n).

Depending on what you want to optimize, select correct method to find kth smallest element in array.

Please share if there is something wrong or missing. If you are interested in taking coaching sessions from our experienced teachers, please reach out to us at communications@algorithmsandme.com