Kth Largest Element in a Stream

Leetcode Daily Challenge (23rd May, 2023)

23 May, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

Link: https://leetcode.com/problems/kth-largest-element-in-a-stream/description/

Problem Explanation with examples:-

Example 1

Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]

Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

Constraints

1 <= k <= 104
0 <= nums.length <= 104
-104 <= nums[i] <= 104
-104 <= val <= 104
At most 104 calls will be made to add.
It is guaranteed that there will be at least k elements in the array when you search for the kth element.

Intuition:-

Simply add the new element to the array and sort it in descending order. Then return the kth largest element.

Solution:-

In the constructor, we initialize the array and the value of k.
In the add function, we append the new element to the array and sort it in descending order. Then we return the kth element from the array.

Code:-

JAVA Solution

class KthLargest {
    private int k;
    private int[] nums;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.nums = nums;
    }

    public int add(int val) {
        int[] updatedNums = Arrays.copyOf(nums, nums.length + 1);
        updatedNums[nums.length] = val;
        Arrays.sort(updatedNums);
        nums = updatedNums;
        return nums[nums.length - k];
    }
}

Python Solution

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.nums = nums
        

    def add(self, val: int) -> int:
        self.nums.append(val)
        self.nums.sort(reverse = True)
        return self.nums[self.k-1]

Complexity Analysis:-

TIME:-

The time complexity of add method is O(n log n) because sorting the array takes O(n log n) time, where n is the length of the array nums

SPACE:-

The space complexity is O(1) because the additional space used is constant, regardless of the input size.

References:-

Sorting

Connect with me:-

java

python

leetcode

dsa