Kth Largest Element in a Stream - Practice Coding Problems

Kth Largest Element in a Stream - Problem

You are part of a university admissions office and need to keep track of the kth highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores.

You are tasked to implement a class which, for a given integer k, maintains a stream of test scores and continuously returns the kth highest score after a new score has been submitted.

More specifically, we are looking for the kth highest score in the sorted list of all scores.

Implement the KthLargest class:

KthLargest(int k, int[] nums) - Initializes the object with the integer k and the stream of test scores nums
int add(int val) - Adds a new test score val to the stream and returns the element representing the kth largest element in the pool of test scores so far

Input & Output

Example 1 — Basic Operations

$ Input: k = 3, nums = [4,5,8,2], operations = [["add",3],["add",5],["add",10],["add",9],["add",4]]

› Output: [4,5,5,8,8]

💡 Note: Initial: [8,5,4] are 3 largest. Add 3→4th largest is 4. Add 5→still 4. Add 10→now 5. Add 9→now 8. Add 4→still 8.

Example 2 — Minimum Size

$ Input: k = 1, nums = [1], operations = [["add",2],["add",0]]

› Output: [2,2]

💡 Note: k=1 means always return the maximum. After adding 2, max is 2. After adding 0, max is still 2.

Example 3 — Empty Initial Array

$ Input: k = 2, nums = [], operations = [["add",5],["add",3],["add",7]]

› Output: [5,3,5]

💡 Note: Add 5: only element so 2nd largest is 5. Add 3: 2nd largest is 3. Add 7: 2nd largest becomes 5.

Constraints

1 ≤ k ≤ 10⁴
0 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
-10⁴ ≤ val ≤ 10⁴
At most 10⁴ calls will be made to add

Visualization

Tap to expand

Understanding the Visualization

Initialize

Start with k=3 and initial scores [4,5,8,2]

Stream Processing

Add new scores one by one: 3, 5, 10, 9, 4

Track Results

Return 3rd largest after each addition: [4,5,5,8,8]

Key Takeaway

🎯 Key Insight: Use a min-heap of size k to efficiently track the k largest elements

Asked in

a Amazon 15 G Google 12 f Facebook 8 Apple 6

The key insight is to maintain only the k largest elements using a min-heap. The root of this heap is always the kth largest element. Best approach is the Min-Heap solution with Time: O(log k) per add operation, Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Sort Every Time	O(n log n)	O(n)	Sort the entire array every time we add a new element
Min-Heap of Size K	O(log k)	O(k)	Use a min-heap to maintain only the k largest elements

Brute Force - Sort Every Time — Algorithm Steps

Store all scores in a list
For each add operation, append the new score
Sort the entire list in descending order
Return the element at index k-1

Visualization

Tap to expand

Step-by-Step Walkthrough

Add Element

Append new score to the list

Sort All

Sort entire array in descending order

Get Kth

Return element at position k-1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int k;
    int* nums;
    int size;
    int capacity;
} KthLargest;

int compare(const void* a, const void* b) {
    return (*(int*)b - *(int*)a);
}

KthLargest* kthLargestCreate(int k, int* nums, int numsSize) {
    KthLargest* obj = (KthLargest*)malloc(sizeof(KthLargest));
    obj->k = k;
    obj->capacity = numsSize + 1000;
    obj->nums = (int*)malloc(obj->capacity * sizeof(int));
    obj->size = numsSize;
    
    for (int i = 0; i < numsSize; i++) {
        obj->nums[i] = nums[i];
    }
    
    return obj;
}

int kthLargestAdd(KthLargest* obj, int val) {
    obj->nums[obj->size++] = val;
    qsort(obj->nums, obj->size, sizeof(int), compare);
    return obj->nums[obj->k - 1];
}

int main() {
    int k = 3;
    int nums[] = {4, 5, 8, 2};
    int numsSize = 4;
    
    KthLargest* kthLargest = kthLargestCreate(k, nums, numsSize);
    
    int operations[] = {3, 5, 10, 9, 4};
    int results[5];
    
    for (int i = 0; i < 5; i++) {
        results[i] = kthLargestAdd(kthLargest, operations[i]);
    }
    
    printf("[");
    for (int i = 0; i < 5; i++) {
        printf("%d", results[i]);
        if (i < 4) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Each add operation sorts the entire array of n elements

⚡ Linearithmic

Space Complexity

O(n)

Store all n elements in the list

⚡ Linearithmic Space

125.0K Views

High Frequency

~25 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Sort Every Time — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler