logoNEURAL COOK
SearchAll PostsTagsNotesAuthor
logoNEURAL COOK

A posts created with Next.js and Tailwind.css

Explore

  • All posts
  • Notes
  • Snippets
  • Tags
  • RSS feed

Connect

instagramtwitterfacebookyoutubelinkedinmailgithub

© 2026 VIKI. All rights reserved.

Built with
Contents
Table Of Contents
2. Add Two Numbers3. Longest Substring Without Repeating Characters5. Longest Palindromic Substring8. String to Integer (atoi)11. Container With Most Water15. 3Sum17. Letter Combinations of a Phone Number19. Remove Nth Node From End of List22. Generate Parentheses33. Search in Rotated Sorted Array34. Find First and Last Position of Element in Sorted Array48. Rotate Image49. Group Anagrams50. Pow(x, n)53. Maximum Subarray54. Spiral Matrix56. Merge Intervals61. Rotate List73. Set Matrix Zeroes74. Search a 2D Matrix75. Sort Colors78. Subsets137. Single Number II138. Copy List with Random Pointer150. Evaluate Reverse Polish Notation151. Reverse Words in a String153. Find Minimum in Rotated Sorted Array155. Min Stack162. Find Peak Element169. Majority Element198. House Robber207. Course Schedule215. Kth Largest Element in an Array227. Basic Calculator II236. Lowest Common Ancestor of a Binary Tree237. Delete Node in a Linked List238. Product of Array Except Self451. Sort Characters By Frequency540. Single Element in a Sorted Array560. Subarray Sum Equals K636. Exclusive Time of Functions875. Koko Eating Bananas1011. Capacity To Ship Packages Within D Days1101. The Earliest Moment When Everyone Become Friends1283. Find the Smallest Divisor Given a Threshold2140. Solving Questions With Brainpower3169. Count Days Without Meetings3481. Apply Substitutions
Code Scratch/leetcode/medium

215. Kth Largest Element in an Array

4 min read
On this pageQuestion
QuestionSolutionPatternHow to IdentifyDescriptionThe IntuitionComplexityCodeCaveatsConcepts to Think AboutLogical Follow-upSolution 2 (using heap)

# Question

Given an unsorted integer array nums and an integer k, return the kthk^{th}kth largest element in the array.

Note: It is the kthk^{th}kth largest element in sorted order, not the kthk^{th}kth distinct element.

# Solution

# Pattern

Quickselect (Hoare's / Lomuto Partitioning) A selection algorithm related to Quicksort. Instead of sorting both sides of a partition, we only recurse into the side containing our target index.

# How to Identify

  • Find the kthk^{th}kth smallest/largest element.
  • Requirement for O(n)O(n)O(n) average time complexity.
  • Constraints suggest that sorting (O(nlog⁡n)O(n \log n)O(nlogn)) is too slow or unnecessary.

# Description

Step-by-step explanation:

  1. Target Index: In a sorted array of size nnn, the kthk^{th}kth largest element is at index target = n - k.
  2. Partitioning: Pick a pivot (randomly to avoid worst-case). Move all elements smaller than the pivot to its left and larger to its right.
  3. Check Pivot Position: After partitioning, the pivot is in its final sorted position i.
    • If i == target, you found the element.
    • If i > target, search the left partition.
    • If i < target, search the right partition.
  4. Repeat: Continue until the search range narrows to the target index.

# The Intuition

Think of Quickselect as "Goal-Oriented Quicksort". In Quicksort, you are trying to organize the entire room. In Quickselect, you only care about who sits in the kthk^{th}kth chair. Once you partition the room, if the kthk^{th}kth chair is on the left side, you completely ignore everyone on the right.

Why O(n)O(n)O(n) and not O(log⁡n)O(\log n)O(logn)?

  • Level 1: Scan nnn elements.
  • Level 2: Scan n/2n/2n/2 elements.
  • Level 3: Scan n/4n/4n/4 elements.
  • Sum: n(1+1/2+1/4+… )≈2nn(1 + 1/2 + 1/4 + \dots) \approx 2nn(1+1/2+1/4+…)≈2n, which is O(n)O(n)O(n).

# Complexity

LabelWorstAverage
Time ComplexityO(n2)O(n^2)O(n2)O(n)O(n)O(n)
Space ComplexityO(1)O(1)O(1)O(1)O(1)O(1)

# Time Complexity

Average case is linear because the problem size reduces geometrically. Worst case (highly skewed partitions) is O(n2)O(n^2)O(n2), though randomized pivoting makes this nearly impossible in practice.

# Space Complexity

Strictly O(1)O(1)O(1) if implemented iteratively. Recursive implementations use O(log⁡n)O(\log n)O(logn) stack space on average.

# Code

import java.util.Random;
 
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        int target = n - k; // Index in sorted array
        int start = 0, end = n - 1;
        Random rand = new Random();
        
        while (start <= end) {
            // Randomized pivot to prevent O(n^2)
            int pivotIndex = start + rand.nextInt(end - start + 1);
            int pivotPos = partition(nums, start, end, pivotIndex);
            
            if (pivotPos == target) {
                return nums[pivotPos];
            } else if (pivotPos < target) {
                start = pivotPos + 1;
            } else {
                end = pivotPos - 1;
            }
        }
        return -1;
    }
 
    private int partition(int[] nums, int start, int end, int pivotIndex) {
        int pivotValue = nums[pivotIndex];
        swap(nums, pivotIndex, end); // Move pivot to end
        int storeIndex = start;
        
        for (int i = start; i < end; i++) {
            if (nums[i] < pivotValue) {
                swap(nums, i, storeIndex);
                storeIndex++;
            }
        }
        swap(nums, storeIndex, end); // Move pivot to its final place
        return storeIndex;
    }
 
    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

# Caveats

  • Modifies Input: Quickselect is an in-place algorithm. If you cannot modify the original array, you must use a Min-Heap (O(nlog⁡k)O(n \log k)O(nlogk) time, O(k)O(k)O(k) space).
  • Duplicate Elements: Standard partitioning handles duplicates, but very large numbers of identical elements can lead to skewed partitions.
  • Worst Case: Always mention that while average is O(n)O(n)O(n), the theoretical worst case is O(n2)O(n^2)O(n2).

# Concepts to Think About

  • Min-Heap Approach: Useful if kkk is very small compared to nnn or if data is streaming.
  • Hoare vs. Lomuto: Hoare's partition uses two pointers from both ends and is generally faster with fewer swaps.
  • Median of Medians: The "Introselect" algorithm uses this to ensure O(n)O(n)O(n) worst-case.
  • Introselect: Used in C++ std::nth_element, which switches from Quickselect to Heapsort if recursion goes too deep.

# Logical Follow-up

Question: What if the array is too large to fit in memory? Solution: Use a Min-Heap of size kkk. Iterate through the file, keeping only the kkk largest elements seen so far in the heap. Space: O(k)O(k)O(k), Time: O(nlog⁡k)O(n \log k)O(nlogk).

Question: What if the numbers are in a specific range (e.g., 1 to 1000)? Solution: Use Counting Sort logic. Count frequencies and iterate from 1000 downwards until you hit the kthk^{th}kth element. Time: O(n+Range)O(n + Range)O(n+Range).

# Solution 2 (using heap)

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer&gt; minHeap = new PriorityQueue<&gt;();
 
    for ( int i = 0; i &lt; nums.length; ++i) {
        minHeap.add(nums[i]);
 
        // to ensure we keep the K smallest element
        if (minHeap.size() &gt; k) {
            minHeap.remove();
        }
    }
 
    return minHeap.peek();        
}
←Previous207. Course ScheduleNext→227. Basic Calculator II

On this page

QuestionSolutionPatternHow to IdentifyDescriptionThe IntuitionComplexityCodeCaveatsConcepts to Think AboutLogical Follow-upSolution 2 (using heap)