Convert Min Heap into Max Heap

public class ConvertMinHeapToMaxheap {

    public static void main(String[] args) {

        ConvertMinHeapToMaxheap convertMinHeapToMaxheap = new ConvertMinHeapToMaxheap();

        int arr[]  ={3 ,5 ,9 ,6, 8, 20, 10, 12, 18, 9};

        for(int i = arr.length/2-1;i>=0;i--){

            convertMinHeapToMaxheap.heapify(arr,arr.length,i);

        }

        System.out.println(Arrays.toString(arr));

    }

    void heapify(int[] arr, int n, int i){

        int l = 2*i+1;

        int r = 2*i+2;

        int largest = i;

        if(l<n){

            if(arr[l]>arr[largest]){

                largest = l;

            }

        }

        if(r<n){

            if(arr[r]>arr[largest]){

                largest = r;

            }

        }

        if(largest!=i){

            int temp = arr[largest];

            arr[largest] = arr[i];

            arr[i] = temp;

            heapify(arr,n,largest);

        }

    }

}

output: [20, 18, 10, 12, 9, 9, 3, 5, 6, 8]

Find kth min element in array in java using MinHeap

public class findKthsmallestElement {

    public static void main(String[] args) {

        int[] arr = {4,1,7,2,3,8,10};

        findKthsmallestElement findKthsmallestElement = new findKthsmallestElement();

        findKthsmallestElement.findKth(arr,3);

    }

    void findKth(int[] arr,int kth){

        if(kth<=0 || kth>arr.length){

            System.out.println("no element found");

            return;

        }

        for(int i = (arr.length/2)-1;i>=0;i--){

            heapify(arr,arr.length,i);

        }

        System.out.println(Arrays.toString(arr));

        

        int length = arr.length;

//execute loop k times from end index, move root element to ith element and heapify again to maintain min heap

        for(int i= length-1;i>=length-kth ;i--){

            swap(arr,i,0);

            heapify(arr,i,0);

        }

        System.out.println(+kth+" kth:"+arr[arr.length-kth]);

        System.out.println(Arrays.toString(arr));

        

    }

    void heapify(int[] arr, int n,int i){

        int l = 2*i+1;

        int r = 2*i+2;

        int smallest = i;

        if(l<n){

            if(arr[l]<arr[smallest]){

                smallest = l;

            }

        }

        if(r<n){

            if(arr[r]<arr[smallest]){

                smallest = r;

            }

        }

        if(smallest!=i){

            swap(arr,i,smallest);

            heapify(arr,n,smallest);

        }

    }

    void swap(int[] arr, int i, int j){

        int temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }

}

output: 

[1, 2, 7, 4, 3, 8, 10]

3 kth:3

[4, 8, 7, 10, 3, 2, 1]

Arranging Coins : LeetCode

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2:

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

Solution:
class Solution {
    public int arrangeCoins(int n) {
        long start =0;
        long end = n;
        while(start<=end){
            long k = start+(end-start)/2;
            long total = k*(k+1)/2;
            if(total==n){
                return (int)k;
            }
            if(n<total){
                end = k-1;
            }else{
                start = k+1;
            }
        }
        return (int)end;
    }
}

Plus One : LeetCode

Given a non-empty array of digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Solution:
class Solution {
    public int[] plusOne(int[] digits) {
       int length = digits.length;
        int i=length -1;
        while(i>=0){
            if(digits[i]!=9){
                digits[i] = digits[i]+1;
                return digits;
            }
             digits[i]=0;
            i--;
            
        }
        int[] finalArr = new int[length+1];
        finalArr[0]=1;
        return finalArr;
    }
}