Author: devangini123

🌙 Problem Statement: Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. You must find a solution with a memory complexity better than O(n2). Examples: Example 1: Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 Output:13 Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13 Example 2: Input:matrix = [[-5]], k = 1 Output:-5 Constraints: n == matrix.length == matrix[i].length 1…

🌙 Problem Statement: Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Examples: Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output:[1,2] Example 2: Input:stones = [1], k = 1 Output:[1] Constraints: 1 x.freq); for(key in map) { pq.push({val: key, freq: map [key]}); // log k if(pq.size() > k) { pq.pop(); // removing smallest element // log k } } // retrun remaining k element in PQ return pq. toArray().map(x=> Number(x.val)) }; import heapq from collections import Counter def topKFrequent(arr, k): # Count frequencies freq_map…

🌙 Problem Statement: You are part of a university admissions office and need to keep track of the kth highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores. You are tasked to implement a class which, for a given integer k, maintains a stream of test scores and continuously returns the kth highest test score after a new score has been submitted. More specifically, we are looking for the kth highest score in the sorted list of all scores. Implement the KthLargest class: KthLargest(int k,…

🌙 Problem Statement: Given an integer array nums and an integer kth, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Can you solve it without sorting? Example 1: Input: nums = [3,2,1,5,6,4], k = 2 Output:5 Example 2: Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output:4 Constraints: 1 k: heapq.heappop(pq) return pq[0] nums = [3, 2, 1, 5, 6, 4] k = 2 print(findKthLargest(nums, k)) import java.util.*; public class Main { public static int findKthLargest(int[] nums, int k) { PriorityQueue pq = new…

🌙 Time and Space Complexity of Heap Sort Space Complexity: O(1) Time Complexity: (HeapifyDown) O(logn) Creating a maxHeap out of an array Total nodes: n Leaf nodes: n/2 For leaf nodes, we have to do zero operations. Create a maxHeap out of array Time Complexity: O(n) Time Complexity = O(n) + O(nlogn) Total: O(nlogn) Time Comparison with Other Sorts Stable Sorting Algorithm Sort the array by ‘age’ [ {name: Rahul, age: 20}, {name: Akshay, age: 18}, {name: Simran. age: 18}, {name: Sachin, age: 30} ] Sroted Array: [{Sachin}, {Rahul}, {Akshay}, {Simran}] (sorted in decreasing order) Stable Algorithm: This algorithm ensures…

🌙 Priority Queues A queue which serves elements based on priority, irrespective of their insertion order. Real Life Example In Hospital 🏥 Patient A: Fever Patient B: Accident Patient C: Headache Here, Tasks with higher priority should be treated first. Normal Queue (FIFO) A -> B -> C Priority Queue (Highest Priority) B -> C -> A Higher the Priority faster will be treated. Use Cases: CPU Scheduling Cache System Real Time Systems Dijkstra’s Algorithm Implementation of Priority Queue 1. Sorting Implementation Whenever you add elements, ensure that the highest priority element is at the front. When you add elements,…

🌙 Heap Sort Algorithm arr = [4, 10, 3, 5, 1] No Extra Space: O(1) Visual Representation The steps are as follows: Create Max Heap. Ignore the leaf nodes. Run Loop in Reverse. For each node we create it a maxHeap. Sort Extract maximum element. Store at end. HeapifyDown Repeat till whole array is sorted. Output: arr = [1, 4, 3, 5, 10] Code let arr = [10, 4, 5, 1, 3]; function heapSort(arr) { let n = arr.length; // create a MaxHeap for(let i=n-1; i >= 0; i–){ heapifyDown(arr, i, n); } // sort the array for(let i =…

🌙 Heap Sort Algorithm Create a Max Heap from unsorted-arr: [10, 5, 3, 4, 1] arr[0] = maxHeap Visual Representation: Swap the first and last value. Reduce the size of heap. Do HeapifyDown. Keep repeating steps 2 to 4 until the array is sorted. Sorted Array: [1, 3, 4, 5, 10] Space Complexity: O(n) Taking an extra space. Create a MaxHeap out of Array: Without an Extra SpaceO(1) Unsorted Array: [4, 10, 5, 3, 1] We will start from the end of the array and heapify down every node. Ignore the leaf nodes, as heapify does not affect them. Solution:…

🌙 Deleting (Extracting) Elements from a Heap Min Heap: Extraction only happen from the top = heap[0]. Heapify down is the process of restoring the heap property after removing the root element (or moving an element downwards). MinHeap is formed. Practice: Solution: Min Heap is formed. Code class MinHeap { constructor() { this.heap = [5, 10, 20, 30]; } getLeftChildIndex(i) { return (2 * i) + 1; } getRightChildIndex(i) { return (2 * i) + 2; } getParentIndex(i) { return Math.floor((i – 1) / 2); } insert(val) { this.heap.push(val); let lastIndex = this.heap.length – 1; this.heapifyUp(lastIndex); } heapifyUp(i) { while…

🌙 Array Representation of Heap Min Heap: Insert 1 Add the element at the end. Heapify-Up from the last index. class MinHeap { constructor() { this.heap = [5, 10, 20, 30]; } getLeftChildIndex(i) { return (2 * i) + 1; } getRightChildIndex(i) { return (2 * i) + 2; } getParentIndex(i) { return Math.floor((i – 1) / 2); } insert(val) { this.heap.push(val); let lastIndex = this.heap.length – 1; this.heapifyUp(lastIndex); } heapifyUp(i) { while (i > 0) { let parentIndex = this.getParentIndex(i); if (this.heap[i] < this.heap[parentIndex]) { [this.heap[i], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[i]]; i = parentIndex; } else break; } } }…