Count kth largest element in linked list

Question

Given a singly linked list and an integer k, write a function to find the kth largest element in the linked list. The function should return the value of the kth largest element, or return -1 if k is greater than the number of elements in the list. The solution should efficiently handle the linked list structure.

Codemia · Accepted Answer

To find the kth largest element in a singly linked list, we can utilize a min-heap data structure. This is because the task requires us to maintain the top k largest elements while traversing the list. A min-heap allows us to efficiently manage the smallest of these largest elements. By maintaining a heap of size k, we can ensure that once we've processed the entire list, the root of the heap will represent the kth largest element. If the list has fewer than k elements, we can immediately return -1.

1. Initialize a min-heap of size k.  
2. Traverse the linked list node by node:  
   - For each node's value:  
     - If the heap has fewer than k elements, add the value to the heap.  
     - If the heap is full (has k elements), compare the current value with the smallest value in the heap (the root). If the current value is larger, replace the root with the current value.  
3. After traversing the list, check the size of the heap:  
   - If it contains exactly k elements, return the root of the heap (the kth largest).  
   - If it contains fewer than k elements, return -1.

**Example:**  
Given the linked list: 4 -> 5 -> 1 -> 2 -> 3 and k = 2:  
- Insert 4 -> Heap: [4]  
- Insert 5 -> Heap: [4, 5]  
- Insert 1 -> Heap: [4, 5] (1 is ignored)  
- Insert 2 -> Heap: [4, 5] (2 is ignored)  
- Insert 3 -> Heap: [4, 5] (3 is ignored)  
- The heap contains [4, 5], and the root (4) is the 2nd largest element.

```python
import heapq

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

def kth_largest(head, k):
    if not head:
        return -1

min_heap = []
    current = head

while current:
        if len(min_heap) < k:
            heapq.heappush(min_heap, current.value)
        else:
            if current.value > min_heap[0]:
                heapq.heapreplace(min_heap, current.value)
        current = current.next

return min_heap[0] if len(min_heap) == k else -1
```

The time complexity of this solution is O(n log k), where n is the number of nodes in the linked list and log k is the time complexity of inserting an element into a min-heap of size k. The space complexity is O(k) because we maintain a heap with at most k elements. This is efficient given the constraints of the problem, especially when k is much smaller than n.

1. **Empty List:** If the linked list is empty (head is None), return -1.  
2. **k is Zero:** If k = 0, this is not a valid request; we can choose to return -1.  
3. **k Greater than List Length:** If k is greater than the number of nodes in the list, return -1.  
4. **Single Element List:** If the list contains only one element and k = 1, return that element. If k > 1, return -1.

Count kth largest element in linked list

Roblox

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

Roblox 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