POTD #3 - Kth Smallest / Largest Element in Unsorted Array | GeeksforGeeks | DSA in Tamil

Kth Smallest / Largest Element in Unsorted Array | GeeksforGeeks | DSA in Tamil Problem Overview - Find the k-th smallest or k-th largest element from an unsorted array without fully sorting it unnecessarily. - Input: An unsorted array of integers and an integer k. - Output: The k-th smallest or k-th largest element. Solution Strategy - Initial Thought: Sort the array and directly access the k-th index. This is simple but not optimal for large datasets. - Optimization: Use Heap (Priority Queue) or Quickselect algorithm to reduce unnecessary sorting work and improve performance. Step-by-Step Logic 1. Brute Force (Sorting Approach): - Sort the array in ascending order. - Return arr[k-1] for k-th smallest or arr[n-k] for k-th largest. 2. Heap-Based Optimization: - Use a Max Heap of size k for k-th smallest. - Traverse the array, maintain top k smallest elements. - The root of the heap gives the k-th smallest element. 3. Quickselect (Best Average Case): - Use partition logic similar to QuickSort. - Place pivot in correct position. - Recurse only on the relevant partition (left or right). - Stop when pivot index == k-1. Complexity Analysis - Brute Force (Sorting): - Time Complexity: O(n log n) - Space Complexity: O(1) or O(n) depending on sorting - Heap Approach: - Time Complexity: O(n log k) - Space Complexity: O(k) - Quickselect: - Time Complexity: O(n) average, O(n²) worst case - Space Complexity: O(1) Resource Links - Problem Link: https://www.geeksforgeeks.org/dsa/kth-smallest-largest-element-in-unsorted-array/ - Logic Visualization (Excalidraw): https://excalidraw.com/?authuser=1#json=Lktas1Jv6axO8qDrxufxG,5KGzqZh-Sa39Xf7UkvxAzg Community & Support - Daily POTD: Join our WhatsApp channel for daily Problem of the Day challenges https://whatsapp.com/channel/0029Vavu8mF2v1IpaPd9np0s - Subscribe: For more DSA and System Design content in Tamil: https://www.youtube.com/@UCUCxBs1RK38mSr00-wfokMw About the Instructor - Syed Jafer: Backend Engineer specializing in DSA and System Design. - Blog: https://parottasalna.com - Events: https://calendar.parottasalna.com Feedback Please leave a comment if you have questions regarding the logic or if you would like to suggest a specific problem for the next video.