Computer Science
Updated 9 days ago | GitHub

Kth Largest Element in an Array

Problem Highlights

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Will k be smaller or equal to nums?
    • Yes, k is always smaller or equal to nums
  • What is the space and time complexity?
    • We want O(n) time and O(n) space.
HAPPY CASE
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

EDGE CASE
Input: nums = [3], k = 1
Output: 3

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Array problems, we want to consider the following approaches:

  • Sort.
    • The runtime will already be nlogn with the first sort, this is over our runtime expectations.
  • Two pointer solutions (left and right pointer variables).
    • We approach this array from both sides, but that requires sorting.
  • Storing the elements of the array in a HashMap or a Set.
    • A HashMap or Set just complicates our code.
  • Traversing the array with a sliding window. Similar to the two pointer solution.
    • A sliding window doesn’t really help us here.
  • Heap
    • Lets use a heap and remove k-1 times, this removes the k-1 largest elements and puts the kth largest element at the top of the heap. Heapifying costs O(n) and each removal costs O(logn), for O(n + k*logn) total, which is cheaper than fully sorting the array.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will heapify the nums, so that we can identify the largest stones at all times. We will remove k items to get the kth largest item at the top of the heap

1. Heapify the num array, create new array with negative values for each num, because python only supports minimum heaps.
2. Remove k items from heap
3. Return the top of the heap.

⚠️ Common Mistakes

  • We want to ask for space/time complexity. Yes this is an easy problem if we had O(nlogn) time. But the interviewer wants to solve this problem faster than O(nlogn) time.

4: I-mplement

Implement the code to solve the algorithm.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # Heapify the num array, create new array with negative values for each num, because python only supports minimum heaps.
        heap = [-num for num in nums]
        heapq.heapify(heap)

        # Remove the top k-1 items so the kth largest is at the top
        for _ in range(1,k):
            heapq.heappop(heap)
        
        # Return the top of the heap (negated back to the original value).
        return -heap[0]

class Solution {
    public int findKthLargest(int[] nums, int k) 
    {
        // Build a min-heap holding the first k elements
        PriorityQueue<Integer> minheap=new PriorityQueue<>();
        for (int i = 0; i < k; i++)
            minheap.add(nums[i]);
        
        // For each remaining element, replace the heap top whenever a larger value appears,
        // so the heap always holds the k largest values seen so far
        for (int i = k; i < nums.length; i++)
        {
            if (nums[i]>minheap.peek())
            {
                minheap.poll();
                minheap.add(nums[i]);
            }
        }

        // Return the top of the heap.
        return minheap.peek();
    }
}

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

  • Trace through your code with an input to check for the expected output
  • Catch possible edge cases and off-by-one errors

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of items in the array.

  • Time Complexity: Python solution: O(N + k * log(N)) — heapifying the array takes O(N) time, each of the k - 1 removals from the size-N heap takes O(log(N)), and reading the top takes O(1). Java solution: O(N * log(k)) — we keep a min-heap bounded to size k, and each of the N elements costs at most O(log(k)) to add or replace.
  • Space Complexity: Python solution: O(N) because we generate and store a heap of all N values. Java solution: O(k) for the bounded heap.