703. Kth largest

703_solution1.c

#include <stdlib.h>

typedef struct {
  int *heap; // min-heap holding the k largest values
  int size;
  int cap;
} KthLargest;

static void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

static void siftUp(int *h, int i) {
  while (i > 0 && h[(i - 1) / 2] > h[i]) {
    swap(&h[(i - 1) / 2], &h[i]);
    i = (i - 1) / 2;
  }
}

static void siftDown(int *h, int n, int i) {
  for (;;) {
    int min = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && h[l] < h[min])
      min = l;
    if (r < n && h[r] < h[min])
      min = r;
    if (min == i)
      return;
    swap(&h[min], &h[i]);
    i = min;
  }
}

static void push(KthLargest *obj, int val) {
  obj->heap[obj->size] = val;
  siftUp(obj->heap, obj->size++);
  if (obj->size > obj->cap) {
    obj->heap[0] = obj->heap[--obj->size];
    siftDown(obj->heap, obj->size, 0);
  }
}

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

int kthLargestAdd(KthLargest *obj, int val) {
  push(obj, val);
  return obj->heap[0];
}

void kthLargestFree(KthLargest *obj) {
  free(obj->heap);
  free(obj);
}

703_solution2.c

#include <stdlib.h>

typedef struct {
  int *heap; // min-heap holding the k largest values
  int size;
  int cap;
} KthLargest;

static void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

static void siftUp(int *h, int i) {
  while (i > 0 && h[(i - 1) / 2] > h[i]) {
    swap(&h[(i - 1) / 2], &h[i]);
    i = (i - 1) / 2;
  }
}

static void siftDown(int *h, int n, int i) {
  for (;;) {
    int min = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && h[l] < h[min])
      min = l;
    if (r < n && h[r] < h[min])
      min = r;
    if (min == i)
      return;
    swap(&h[min], &h[i]);
    i = min;
  }
}

static void push(KthLargest *obj, int val) {
  if (obj->size < obj->cap) {
    obj->heap[obj->size] = val;
    siftUp(obj->heap, obj->size++);
  } else if (val > obj->heap[0]) {
    obj->heap[0] = val;
    siftDown(obj->heap, obj->size, 0);
  }
}

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

int kthLargestAdd(KthLargest *obj, int val) {
  push(obj, val);
  return obj->heap[0];
}

void kthLargestFree(KthLargest *obj) {
  free(obj->heap);
  free(obj);
}

703_solution1.cpp

#include <functional>
#include <queue>
#include <vector>

using namespace std;

class KthLargest {
private:
  int cap;
  priority_queue<int, vector<int>, greater<int>> pq;

public:
  KthLargest(int k, vector<int> &nums) : cap(k), pq(nums.begin(), nums.end()) {
    while (pq.size() > cap)
      pq.pop();
  }

  int add(int val) {
    pq.push(val);
    if (pq.size() > cap)
      pq.pop();
    return pq.top();
  }
};

703_solution2.cpp

#include <functional>
#include <queue>
#include <vector>

using namespace std;

class KthLargest {
private:
  int cap;
  priority_queue<int, vector<int>, greater<int>> pq;

public:
  KthLargest(int k, vector<int> &nums) : cap(k) {
    for (int n : nums)
      add(n);
  }

  int add(int val) {
    if (pq.size() < cap) {
      pq.push(val);
    } else if (val > pq.top()) {
      pq.pop();
      pq.push(val);
    }
    return pq.top();
  }
};

703_solution1.go

package heaps

import (
    "container/heap"
    "sort"
)

type minHeap struct{ sort.IntSlice }

func (h *minHeap) Push(x any) { h.IntSlice = append(h.IntSlice, x.(int)) }

func (h *minHeap) Pop() any {
    old := h.IntSlice
    x := old[len(old)-1]
    h.IntSlice = old[:len(old)-1]
    return x
}

type KthLargest struct {
    cap int
    pq  *minHeap
}

func Constructor(k int, nums []int) KthLargest {
    pq := &minHeap{nums}
    heap.Init(pq)
    for pq.Len() > k {
        heap.Pop(pq)
    }
    return KthLargest{cap: k, pq: pq}
}

func (this *KthLargest) Add(val int) int {
    heap.Push(this.pq, val)
    if this.pq.Len() > this.cap {
        heap.Pop(this.pq)
    }
    return this.pq.IntSlice[0]
}

703_solution2.go

package heaps

import (
    "container/heap"
    "sort"
)

type minHeap struct{ sort.IntSlice }

func (h *minHeap) Push(x any) { h.IntSlice = append(h.IntSlice, x.(int)) }

func (h *minHeap) Pop() any {
    old := h.IntSlice
    x := old[len(old)-1]
    h.IntSlice = old[:len(old)-1]
    return x
}

type KthLargest struct {
    cap int
    pq  *minHeap
}

func Constructor(k int, nums []int) KthLargest {
    kl := KthLargest{cap: k, pq: &minHeap{}}
    for _, n := range nums {
        kl.Add(n)
    }
    return kl
}

func (this *KthLargest) Add(val int) int {
    if this.pq.Len() < this.cap {
        heap.Push(this.pq, val)
    } else if val > this.pq.IntSlice[0] {
        this.pq.IntSlice[0] = val
        heap.Fix(this.pq, 0)
    }
    return this.pq.IntSlice[0]
}

703_solution1.java

import java.util.PriorityQueue;

class KthLargest {
    private final int cap;
    private final PriorityQueue<Integer> pq = new PriorityQueue<>();

    public KthLargest(int k, int[] nums) {
        cap = k;
        for (int n : nums)
            pq.offer(n);
        while (pq.size() > cap)
            pq.poll();
    }

    public int add(int val) {
        pq.offer(val);
        if (pq.size() > cap)
            pq.poll();
        return pq.peek();
    }
}

703_solution2.java

import java.util.PriorityQueue;

class KthLargest {
    private final int cap;
    private final PriorityQueue<Integer> pq = new PriorityQueue<>();

    public KthLargest(int k, int[] nums) {
        cap = k;
        for (int n : nums)
            add(n);
    }

    public int add(int val) {
        if (pq.size() < cap) {
            pq.offer(val);
        } else if (val > pq.peek()) {
            pq.poll();
            pq.offer(val);
        }
        return pq.peek();
    }
}

703_solution1.js

class MinHeap {
  constructor() {
    this.data = [];
  }

  size() {
    return this.data.length;
  }

  top() {
    return this.data[0];
  }

  push(val) {
    const h = this.data;
    h.push(val);
    let i = h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (h[p] <= h[i]) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  }

  pop() {
    const h = this.data;
    const last = h.pop();
    if (h.length === 0) return;
    h[0] = last;
    let i = 0;
    for (;;) {
      let min = i;
      const l = 2 * i + 1,
        r = 2 * i + 2;
      if (l < h.length && h[l] < h[min]) min = l;
      if (r < h.length && h[r] < h[min]) min = r;
      if (min === i) return;
      [h[min], h[i]] = [h[i], h[min]];
      i = min;
    }
  }
}

class KthLargest {
  constructor(k, nums) {
    this.cap = k;
    this.pq = new MinHeap();
    for (const n of nums) this.add(n);
  }

  add(val) {
    this.pq.push(val);
    if (this.pq.size() > this.cap) this.pq.pop();
    return this.pq.top();
  }
}

703_solution2.js

class MinHeap {
  constructor() {
    this.data = [];
  }

  size() {
    return this.data.length;
  }

  top() {
    return this.data[0];
  }

  push(val) {
    const h = this.data;
    h.push(val);
    let i = h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (h[p] <= h[i]) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  }

  pop() {
    const h = this.data;
    const last = h.pop();
    if (h.length === 0) return;
    h[0] = last;
    let i = 0;
    for (;;) {
      let min = i;
      const l = 2 * i + 1,
        r = 2 * i + 2;
      if (l < h.length && h[l] < h[min]) min = l;
      if (r < h.length && h[r] < h[min]) min = r;
      if (min === i) return;
      [h[min], h[i]] = [h[i], h[min]];
      i = min;
    }
  }
}

class KthLargest {
  constructor(k, nums) {
    this.cap = k;
    this.pq = new MinHeap();
    for (const n of nums) this.add(n);
  }

  add(val) {
    if (this.pq.size() < this.cap) {
      this.pq.push(val);
    } else if (val > this.pq.top()) {
      this.pq.pop();
      this.pq.push(val);
    }
    return this.pq.top();
  }
}

703_solution1.py

import heapq
from typing import List


class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.cap = k
        self.pq = nums
        heapq.heapify(self.pq)
        while len(self.pq) > k:
            heapq.heappop(self.pq)

    def add(self, val: int) -> int:
        heapq.heappush(self.pq, val)
        if len(self.pq) > self.cap:
            heapq.heappop(self.pq)
        return self.pq[0]

703_solution2.py

import heapq
from typing import List


class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.cap = k
        self.pq: List[int] = []
        for n in nums:
            self.add(n)

    def add(self, val: int) -> int:
        if len(self.pq) < self.cap:
            heapq.heappush(self.pq, val)
        elif val > self.pq[0]:
            heapq.heapreplace(self.pq, val)
        return self.pq[0]

703_solution1.rs

use std::cmp::Reverse;
use std::collections::BinaryHeap;

struct KthLargest {
    cap: usize,
    pq: BinaryHeap<Reverse<i32>>,
}

impl KthLargest {
    fn new(k: i32, nums: Vec<i32>) -> Self {
        let mut pq: BinaryHeap<_> = nums.into_iter().map(Reverse).collect();
        let cap = k as usize;
        while pq.len() > cap {
            pq.pop();
        }
        Self { cap, pq }
    }

    fn add(&mut self, val: i32) -> i32 {
        self.pq.push(Reverse(val));
        if self.pq.len() > self.cap {
            self.pq.pop();
        }
        self.pq.peek().unwrap().0
    }
}

703_solution2.rs

use std::cmp::Reverse;
use std::collections::BinaryHeap;

struct KthLargest {
    cap: usize,
    pq: BinaryHeap<Reverse<i32>>,
}

impl KthLargest {
    fn new(k: i32, nums: Vec<i32>) -> Self {
        let mut kl = Self { cap: k as usize, pq: BinaryHeap::new() };
        for n in nums {
            kl.add(n);
        }
        kl
    }

    fn add(&mut self, val: i32) -> i32 {
        if self.pq.len() < self.cap {
            self.pq.push(Reverse(val));
        } else if let Some(mut top) = self.pq.peek_mut() {
            if val > top.0 {
                *top = Reverse(val);
            }
        }
        self.pq.peek().unwrap().0
    }
}