Count kth largest element in linked list

Question

Given a singly linked list, write a function to find and return the kth largest element in the list. The function should handle cases where k is greater than the number of elements in the list by returning an appropriate value (e.g., None). The input will be the head of the linked list and an integer k, and the output should be the kth largest element as an integer.

Codemia · Accepted Answer

To solve the problem of finding the kth largest element in a singly linked list, we can recognize that this requires sorting or maintaining a priority order of the elements. Since the linked list does not allow random access like an array, we must traverse it sequentially. The most suitable approach here relates to using a min-heap (or priority queue) to keep track of the largest k elements as we traverse the list. This approach is efficient because it allows us to maintain the k largest elements dynamically, even as we encounter more elements in the list.

1. **Initialize a min-heap** to store the k largest elements. 
2. **Traverse the linked list** node by node. For each node's value: 
   - If the size of the heap is less than k, push the value onto the heap. 
   - If the size of the heap has reached k and the current value is larger than the smallest element (root of the heap), replace the root with the current value. This maintains the heap size at k. 
3. **After traversing the list**, if the heap size is less than k, return None (indicating that there are not enough elements). Otherwise, return the root of the heap, which will be the kth largest element.

**Example:** For a linked list with values [3, 1, 4, 1, 5, 9, 2, 6] and k = 3, we would maintain a heap that evolves like this: 
- After processing '3': Heap = [3] 
- After processing '1': Heap = [1, 3] 
- After processing '4': Heap = [3, 4] 
- After processing '1': Heap remains [3, 4] 
- After processing '5': Heap = [4, 5] 
- After processing '9': Heap = [5, 9] 
- After processing '2': Heap remains [5, 9] 
- After processing '6': Heap = [6, 9] 
The root of the heap now is '5', which is the 3rd largest element.

```python
import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def kthLargest(head: ListNode, k: int) -> int:
    min_heap = []
    current = head
    
    while current:
        if len(min_heap) < k:
            heapq.heappush(min_heap, current.val)
        elif current.val > min_heap[0]:
            heapq.heapreplace(min_heap, current.val)
        current = current.next
    
    return min_heap[0] if len(min_heap) == k else None
```

The time complexity of this approach is O(n log k), where n is the number of nodes in the linked list. This is because we traverse each node exactly once (O(n)), and for each node, we perform a heap operation (either push or replace) which takes O(log k) time. The space complexity is O(k) due to the storage of k elements in the heap. This is efficient given that we are only storing the k largest elements rather than sorting the entire list.

1. **k is greater than the length of the list**: In this case, we should return None since there aren't enough elements to find the kth largest. 
2. **k is zero or negative**: We should return None since a valid kth largest element cannot exist for non-positive k values. 
3. **Empty linked list**: If the head is None, return None since there are no elements to evaluate. 
4. **k equals one**: This should return the maximum element in the list.

Count kth largest element in linked list

Airbnb

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Airbnb Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string