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?
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
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:
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
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 k items from heap
for _ in range(1,k):
heapq.heappop(heap)
# Return the top of the heap.
return neg(heap[0])
class Solution {
public int findKthLargest(int[] nums, int k)
{
// Heapify the num array, create new array with negative values for each num
PriorityQueue<Integer> minheap=new PriorityQueue<>();
for (int i = 0; i < k; i++)
minheap.add(nums[i]);
// Remove len(nums) - k items from heap
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();
}
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
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.
O(k + (n - k) * log(k))
. This is because you first heapify the new array, which takes O(n)
time. Then, you remove k elements from the heap, which takes O(k * log(k))
time. Finally, you return the top of the heap, which takes O(1)
time. In total, the time complexity of your solution is O(n + k * log(k))
.O(N)
because we need to generate and store a heap.