The Heap Space

Time Complexity - O(N log N) || Space Complexity - O(N) In bucket sort, we create buckets first, using some formula. After the creation of the bucket, we one by one put the elements into the buckets, again using some formula. After we put all the elements into created buckets, we sort the elements bucketwise using any sorting algorithm like quicksort, mergesort, etc After sorting elements in all the buckets, we concatenate the elements from all the buckets together. The biggest advantage of Bucket Sort compared to other sort is that each bucket can be sorted independently. Hence, it is a great suite for distributed computing. Suppose we have given a very large array of Person objects and we have to sort the people in increasing order of age. We know it is a large array hence efficiency is very important. Also, we know that the value of 'age' lies in a small range. Bucket sort is perfect for these kinds of situations. We can make small multiple buckets of 1 different year

Time Complexity - O(nlogn) We use min-heap if we want to sort in ascending order and max heap if we want to sort in descending order. We insert one by one into the heap, heapifying  from bottom to top while inserting in order to maintain corresponding heap property. Now, after all elements are insered into the heap, we extract elements one by one. Remember- we can only extract the root of a heap.  Also, after extraction, we put the last element in the level order traversal of heap as the new root and again heapify from top to bottom this time, in order to maintain the corresponding heap property. It is not a stable sort __________________________________________________________________________________________________________________________________________________________________ public class Main {     int[] heapArr;     int endOfHeap;          Main(int size){         this.heapArr=new int[size];         this.endOfHeap=0;     }          public vo

According to me, it is the easiest and one of the most important and efficient sorting algorithm. Java 7 also uses quicksort for their .sort() method Time Complexity - O(nlogn) Space Complexity - O(n) -> As we are using recursion, it uses the internal stack In quicksort, we chose a pivot element first (in this program, I chose the last element as pivot) All the elements in any array, which are less than the pivot remains to the left of pivot and all the elements which are greater than the pivot element remains to the right of pivot. To do the above, we first chose last element as pivot element, i as (start-1) and j as start In quicksort, we only have to take care of pivot, i and j Now, we compare if a[i]<= pivot element. If yes, we increment i and swap arr[i] and arr[j] After completing one iteration from start to end, we get a pivot element fixed at its right position. Now, we recursively do this for the left subarray and right subarray to the pivot element. QuickS

Time Complexity - O(nLogn) || Space Complexity - O(n) [Due to two temp arrays taken to store left and right subpart] It follows a divide and conquer strategy It is a stable sort Java 6 and below versions of Java used merge sort in for their inbuilt .sort() method __________________________________________________________________________________________________________________________________________________________________ public class Main {          public static void mergeSort(int[] arr, int left, int right){         // if left is less than right, it means there is more than 1 element. Hence, this problem can be broken down into smaller sub-problems         if(left<right){             // we find the mid first and break this array into 2 parts around mid             int mid = (left+right)/2;             // first part             mergeSort(arr,left,mid);             // second part             mergeSort(arr,mid+1,right);                     

Time Complexity - O(n^2) || Space Complexity - O(1) We maintain array like this - [sorted portion | unsorted portion] (same as selection sort) Now in every iteration of i , we take first element of unsorted portion and try to insert it in sorted portion at it's correct place by comparing the currently picked first element of unsorted  and swapping it repeteadly with previous elements in sorted portion [starting from last element of sorted portion] and swapping them according to our need whether we want to sort in increasing or decreasing order. While doing the above swapping, remember we are moving from last to first element of sorted portion and swapping them. If sorting in increasing order, if we find any element before swapping to be less than the current element, we do not swap and break from the inner loop of j and continue our next iteration of i loop. Insertion sort is best sorting algorithm if we are continuously getting new inputs and we have to place the new input

Time Complexity - O(n^2)  || Space Complexity - O(1) In selection sort, we divide an array into two parts - sorted and unsorted (by i loop here in code) We find the minimum element's index from the unsorted array (here by j loop) and swap public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                 System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // selection sort         for(int i=0;i<arr.length;i++){                         int minIndex=i;             // find minimum from unsorted array             for(int j=i+1;j<arr.length;j++){                 if(arr[minIndex]>arr[j]){                     minIndex=j;                 }             }             // now as we got index of minimum element from unsorted array in minIndex,

Time complexity - O(n^2)  || Space Complexity - O(1) Bubble sort is an inplace sorting algorithm, that means we do not any extra space while bubble sorting public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                  System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // bubble sort         for(int i=0;i<arr.length-1;i++){ // iterates through first to last cell             for(int j=0;j<arr.length-1-i;j++){ // inner loop controls swapping and extent to which swapping is to be performed in array                 if(arr[j]>arr[j+1]){                     int temp = arr[j];                     arr[j]=arr[j+1];                     arr[j+1]=temp;                 }             }             // after each iteration we ge

  What is trie? Trie is a search tree that is used to store and search strings in space and time-efficient way. How String is stored in a trie? A trie node consists of  Hashmap of <Character, address of next Trie Node> and a boolean flag endOfWord In any trie node, we can store non-repetitive multiple characters.(Remember we use hashmap. Right?) For any given string, it's each character is stored in different trie nodes. After storing all the characters of a string in different trie nodes, we make a new trie node and mark its endOfWord flag as true, indicating the end of that particular string. Practical Uses of Trie Spelling checker Autocomplete feature Code (Please read comments in code for the explanation of each step) import java.util.*; // A node of trie class TrieNode{           // A hashmap to store the characters and address of its next trie node     HashMap<Character,TrieNode> chars;            // a boolean flag to indicate the end of the

  public class Main {     // the array used to implement max heap     // left child index is [2*x]  and right child index is [(2*x)+1]  if 'x' is the index of parent in array 'arr'.     // Cell 0 is unused for the sake of mathemaical simplicity.     int arr[];     // variable to store the last used index of arr     int lastUsedIndex;       // creating heap using constuctor     // Time Complexity - O(1) , Space Complexity - O(n)     Main(int size){         this.arr = new int[size];         this.lastUsedIndex=0;     }       // method to initialize the arr with Integer.MIN_VALUE, when it is empty     public void initializeArray(){         if(this.lastUsedIndex==0){             for(int i=0;i<this.arr.length;i++){                 this.arr[i]=Integer.MIN_VALUE;             }         }     }       // method to add a new node to the binary max heap     // Time Complexity - O(log n) , Space Complexity - O(1)     public void addNode(int x){