Count kth largest element in array

Question

Given an unsorted array of integers, write a function to find the kth largest element in the array. The function should take the array and an integer k as inputs and return the kth largest element. Note that k is guaranteed to be between 1 and the length of the array.

Codemia · Accepted Answer

To solve this problem, we can utilize the Quickselect algorithm, which is a selection algorithm to find the kth smallest (or largest) element in an unordered list. The Quickselect algorithm is efficient because it has an average time complexity of O(n). The reason it applies here is that we are only interested in the kth largest element, which allows us to avoid fully sorting the array. By partitioning the array around a pivot, we can narrow down which side of the pivot contains the kth largest element.

1. Choose a pivot element from the array (we can use the last element for simplicity). 
2. Partition the array such that elements greater than the pivot come before it and elements less than it come after. 
3. Determine the position of the pivot after partitioning. 
4. If the pivot's position is equal to `len(arr) - k`, we have found the kth largest element. 
5. If the pivot's position is greater, repeat the process on the left subarray. 
6. If the pivot's position is smaller, repeat on the right subarray.

**Example:** For the array [3, 2, 1, 5, 6, 4] and k = 2: 
- Let's choose the pivot as 4. 
- After partitioning, we might get [5, 6, 4, 1, 2, 3]. The pivot (4) is at index 2. 
- Since we want the 2nd largest, we check if index 2 equals `len(arr) - k` (which is 4). It doesn’t, so we check the left side.

Here is a Python implementation of the Quickselect algorithm for this problem:

```python
def quickselect(arr, left, right, k):
    if left == right:
        return arr[left]
    pivot_index = partition(arr, left, right)
    if pivot_index == len(arr) - k:
        return arr[pivot_index]
    elif pivot_index > len(arr) - k:
        return quickselect(arr, left, pivot_index - 1, k)
    else:
        return quickselect(arr, pivot_index + 1, right, k)

def partition(arr, left, right):
    pivot = arr[right]
    i = left
    for j in range(left, right):
        if arr[j] > pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[right] = arr[right], arr[i]
    return i

def find_kth_largest(arr, k):
    return quickselect(arr, 0, len(arr) - 1, k)
```

**Usage:** Call `find_kth_largest([3, 2, 1, 5, 6, 4], 2)` to get 5.

The average time complexity of the Quickselect algorithm is O(n) due to the partitioning step, which divides the problem size roughly in half each time. The worst-case time complexity is O(n^2), which occurs when the smallest or largest element is consistently chosen as the pivot. However, with a good pivot selection strategy (like randomization), the average case is typically achieved. The space complexity is O(1) since we are modifying the array in place and not using any extra space proportional to the input size.

1. **Single Element Array:** If the input is an array with only one element, e.g., `[1]` and k = 1, the output should be 1. 
2. **All Elements Same:** If the input is `[2, 2, 2, 2]` and k = 2, the output should still be 2. 
3. **Negative Numbers:** Input like `[-1, -2, -3, -4]` for k = 1 should return -1, the largest element. 
4. **Large k Value:** For an array with a large number of elements, ensure that k is valid and does not exceed the array length.

Count kth largest element in array

Walmart

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Walmart Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Merge Three Sorted strings

Find connected components in string

Binary Search on string

Detect anagram in array