Kth Largest Element in an Array

Data Structures and Algorithms

Statement

Find the kth largest element of an unsorted array.

Constraints

• 1 ≤ k ≤ array.length() ≤ 10³
• -10⁴ ≤ array[i] ≤ 10⁴

Solution

"""
production algorithm
"""

from data_structures.heap.heap import Heap


class Solution:
    def find_kth_largest(self, numbers, k):
        """
        time complexity O(nlogk)
        space complexity O(k)
        """
        smallest = Heap()

        for i in range(len(numbers)):
            smallest.push(MinHeapData(numbers[i]))
            if k < smallest.size():
                smallest.pop()

        return smallest.top().number


class MinHeapData:
    def __init__(self, number):
        self.number = number

    def __lt__(self, other):
        return self.number < other.number

"""
unit tests
"""

from unittest import TestCase
from algorithms.top_k_elements.kth_largest_element_of_array.solution import Solution


class SolutionTestCase(TestCase):
    def test_no_duplicates(self):
        # Given
        numbers = [51, 53, 55, 57, 59, 71, 73, 75, 77, 79, 91, 93, 95, 97, 99]
        k = 7
        solution = Solution()

        # When
        actual = solution.find_kth_largest(numbers, k)

        # Then
        expected = 77
        self.assertEqual(actual, expected)

    def test_some_duplicates(self):
        # Given
        numbers = [51, 53, 55, 57, 59, 71, 71, 73, 73, 75, 75, 77, 77, 79, 79]
        k = 9
        solution = Solution()

        # When
        actual = solution.find_kth_largest(numbers, k)

        # Then
        expected = 71
        self.assertEqual(actual, expected)

Strategy

Top K Elements.

Explanation

Sort all elements in a min heap with maximum size k. If the size of the min heap reaches k, then pop the top element so that the size of the min heap remains k. The kth largest element of the array is at the top of the min heap.

Time Complexity

Given n elements, there are n iterations of operations of a heap with size proportional to k. Therefore, the time complexity of the algorithm is O(nlogk).

Space Complexity

The maximum size of the heap is k. Therefore, the auxiliary space complexity of the algorithm is O(k).

Links

data_structures_algorithms/algorithms/top_k_elements/kth_largest_element_of_array at main ·…