beingsde
Sign In
Back to all DSA patterns
Divide & Conquer•Pattern: Divide & Conquer•Medium

QuickSelect — find Kth smallest element in O(n) average

Problem Intuition & Objective

Find the kth smallest element without fully sorting the array.

Time ComplexityO(n) average, O(n²) worst
Optimal
Space ComplexityO(log n) average
Memory Bounds
Optimal Algorithmic Approach

Randomized QuickSelect partition.

Core Invariants & Edge Cases

  • Partition around a pivot (Lomuto or Hoare scheme)
  • If pivot index == k, return; else recurse into the correct half
  • Randomized pivot makes average O(n), worst O(n²)
Previous ProblemMerge sort — divide and conquer sortNext Problem Pow(x, n) — fast exponentiation

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.