Skip to content

get kth-largest-element-in-an-array – implemented using maxheap but getting time exceeded in leetcode

I am trying to solve this leetcode challenge . I implemented a MaxHeap and tried to popout the values to get the Kth largest element in the array but I get a time limit exceeded.

Is there any issue with my MaxHeap implementation that it is slow or can this be done in a faster method?


class Solution {

private int capacity = 10;
private int size = 0;
int items [] = new int[capacity];

//parent = (i-1)/2
//left-child = 2i+1
//right-child = 2i

 public int findKthLargest(int[] nums, int k) {        
    for(int i=0;i<nums.length;i++){

    for(int i=0; i<k-1; i++){
        int val = pop();
        System.out.println("max val popped" + val);
      //  printHeapArray();
    return peek();

private int getLeftChildIndex(int index){
    return index*2+1;

private int getRightChildIndex(int index) {
    return index*2;

private int getParentIndex(int index) {
    return (index-1)/2;

private int leftChild(int index) {
    return items[getLeftChildIndex(index)];

private int rightChild(int index) {
    return items[getRightChildIndex(index)];

private int parent(int index) {
    return items[getParentIndex(index)];

private boolean hasParent(int index){
    return getParentIndex(index) >= 0;

private boolean hasLeftChild(int index){
    return getLeftChildIndex(index) < size;

private boolean hasRightChild(int index){
    return getRightChildIndex(index) < size;

private void swap(int indexOne, int indexTwo) {
    int temp = items[indexOne];
    items[indexOne] = items[indexTwo];
    items[indexTwo] = temp;

private void ensureCapacity() {
    if(capacity == size -1) {
        items = Arrays.copyOf(items, capacity*2);
        capacity *= 2;

public int peek() {
    if(size == 0) {
        throw new IllegalStateException();
    return items[0];

public void push(int item) {
    items[size] = item;

private void heapifyUp() {
    int index = size - 1;
    while(hasParent(index) && parent(index) < items[index]) {
        swap(getParentIndex(index), index);
        index = getParentIndex(index);

public int pop() {
    if(size == 0 ) throw new IllegalStateException();
    int item = items[0];
    items[0] = items[size-1];
    return item;

//1.Compare the children first and find the child you want to compare against with parent
//2.Compare the selected child with its parent to see if it needs to be swapped
private void heapifyDown() {
    int index = 0;
        int smallerChildIndex = getLeftChildIndex(index);
        if(hasRightChild(index) && rightChild(index) > leftChild(index)){
            smallerChildIndex = getRightChildIndex(index);
        if(items[index] > items[smallerChildIndex]) {

        if(items[smallerChildIndex] >  items[index]) {
            swap(smallerChildIndex, index);
        index = smallerChildIndex;


public void printHeapArray(){



You have an infinite loop, because you’re using the wrong formulas for left-child-index and right-child-index.

Look at heapifyDown. The first index tested is 0, and getRightChildIndex() says that it’s right child is also at 0*2 == 0.

For heaps with the root at 0, the left and right children of i are at i*2+1 and i*2+2. For heaps with the root at 1 (not your case), the left and right children of i are at i*2 and i*2+1.

Note that if you fix this then your algorithm can work, but it won’t be awesome. Appropriate solutions for this problem use quickselect (expected O(n)), a min-heap (O(n * log k)), or a partial heapsort (O(n + k log n)). Yours is like a partial heap sort, but without the O(n) heapify at the start, giving O(n log n).