Problems

function findKthLargest(nums, k) {
    const minHeap = new PriorityQueue(); // Min-heap

    for (const num of nums) {
        minHeap.push(num);

        // Keep only k largest elements
        if (minHeap.heap.length > k) {
            minHeap.pop();
        }
    }

    return minHeap.peek();
}

import heapq

def findKthLargest(nums, k):
    min_heap = []

    for num in nums:
        heapq.heappush(min_heap, num)

        # Keep only k largest elements
        if len(min_heap) > k:
            heapq.heappop(min_heap)

    return min_heap[0]

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.offer(num);

            // Keep only k largest elements
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        return minHeap.peek();
    }
}

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minHeap;

        for (int num : nums) {
            minHeap.push(num);

            // Keep only k largest elements
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }

        return minHeap.top();
    }
};

func findKthLargest(nums []int, k int) int {
    minHeap := &IntHeap{}
    heap.Init(minHeap)

    for _, num := range nums {
        heap.Push(minHeap, num)

        // Keep only k largest elements
        if minHeap.Len() > k {
            heap.Pop(minHeap)
        }
    }

    return (*minHeap)[0]
}

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

def find_kth_largest(nums, k)
    min_heap = []

    nums.each do |num|
        min_heap << num
        min_heap.sort!

        # Keep only k largest elements
        if min_heap.length > k
            min_heap.shift
        end
    end

    min_heap[0]
end

function lastStoneWeight(stones) {
    const maxHeap = new PriorityQueue((a, b) => b - a); // Max-heap

    // Add all stones to max-heap
    for (const stone of stones) {
        maxHeap.push(stone);
    }

    while (maxHeap.heap.length > 1) {
        const stone1 = maxHeap.pop();
        const stone2 = maxHeap.pop();

        // If stones have different weights, add difference back
        if (stone1 > stone2) {
            maxHeap.push(stone1 - stone2);
        }
    }

    return maxHeap.isEmpty() ? 0 : maxHeap.peek();
}

import heapq

def lastStoneWeight(stones):
    # Python heapq is min-heap, so negate values for max-heap behavior
    max_heap = [-stone for stone in stones]
    heapq.heapify(max_heap)

    while len(max_heap) > 1:
        stone1 = -heapq.heappop(max_heap)
        stone2 = -heapq.heappop(max_heap)

        # If stones have different weights, add difference back
        if stone1 > stone2:
            heapq.heappush(max_heap, -(stone1 - stone2))

    return 0 if not max_heap else -max_heap[0]

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

        // Add all stones to max-heap
        for (int stone : stones) {
            maxHeap.offer(stone);
        }

        while (maxHeap.size() > 1) {
            int stone1 = maxHeap.poll();
            int stone2 = maxHeap.poll();

            // If stones have different weights, add difference back
            if (stone1 > stone2) {
                maxHeap.offer(stone1 - stone2);
            }
        }

        return maxHeap.isEmpty() ? 0 : maxHeap.peek();
    }
}

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        // C++ priority_queue is max-heap by default
        priority_queue<int> maxHeap;

        // Add all stones to max-heap
        for (int stone : stones) {
            maxHeap.push(stone);
        }

        while (maxHeap.size() > 1) {
            int stone1 = maxHeap.top();
            maxHeap.pop();
            int stone2 = maxHeap.top();
            maxHeap.pop();

            // If stones have different weights, add difference back
            if (stone1 > stone2) {
                maxHeap.push(stone1 - stone2);
            }
        }

        return maxHeap.empty() ? 0 : maxHeap.top();
    }
};

func lastStoneWeight(stones []int) int {
    maxHeap := &IntMaxHeap{}
    heap.Init(maxHeap)

    // Add all stones to max-heap
    for _, stone := range stones {
        heap.Push(maxHeap, stone)
    }

    for maxHeap.Len() > 1 {
        stone1 := heap.Pop(maxHeap).(int)
        stone2 := heap.Pop(maxHeap).(int)

        // If stones have different weights, add difference back
        if stone1 > stone2 {
            heap.Push(maxHeap, stone1-stone2)
        }
    }

    if maxHeap.Len() == 0 {
        return 0
    }
    return heap.Pop(maxHeap).(int)
}

type IntMaxHeap []int

func (h IntMaxHeap) Len() int           { return len(h) }
func (h IntMaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntMaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntMaxHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntMaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

def last_stone_weight(stones)
    # Ruby doesn't have built-in heap, so we'll use array with sort
    stones.sort!

    while stones.length > 1
        stone1 = stones.pop
        stone2 = stones.pop

        # If stones have different weights, add difference back
        if stone1 > stone2
            stones << (stone1 - stone2)
            stones.sort!
        end
    end

    stones.empty? ? 0 : stones[0]
end

function topKFrequent(nums, k) {
    const freq = new Map();
    const minHeap = new PriorityQueue((a, b) => a[0] - b[0]); // Min-heap by frequency

    // Count frequencies
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }

    // Add to heap [frequency, element] pairs
    for (const [num, count] of freq) {
        minHeap.push([count, num]);

        if (minHeap.heap.length > k) {
            minHeap.pop();
        }
    }

    // Extract elements (frequencies are not needed)
    return minHeap.heap.map(pair => pair[1]);
}

import heapq
from collections import Counter

def topKFrequent(nums, k):
    freq = Counter(nums)
    min_heap = []

    # Add to heap [frequency, element] pairs
    for num, count in freq.items():
        heapq.heappush(min_heap, (count, num))

        # Keep only k most frequent
        if len(min_heap) > k:
            heapq.heappop(min_heap)

    # Extract elements
    return [pair[1] for pair in min_heap]

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        // Count frequencies
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        // Add to heap [frequency, element] pairs
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            minHeap.offer(new int[]{entry.getValue(), entry.getKey()});

            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // Extract elements
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll()[1];
        }
        return result;
    }
}

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;

        // Count frequencies
        for (int num : nums) {
            freq[num]++;
        }

        // Add to heap [frequency, element] pairs
        for (auto& entry : freq) {
            minHeap.push({entry.second, entry.first});

            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }

        // Extract elements
        vector<int> result;
        while (!minHeap.empty()) {
            result.push_back(minHeap.top().second);
            minHeap.pop();
        }
        return result;
    }
};

func topKFrequent(nums []int, k int) []int {
    freq := make(map[int]int)
    minHeap := &FreqHeap{}
    heap.Init(minHeap)

    // Count frequencies
    for _, num := range nums {
        freq[num]++
    }

    // Add to heap [frequency, element] pairs
    for num, count := range freq {
        heap.Push(minHeap, [2]int{count, num})

        if minHeap.Len() > k {
            heap.Pop(minHeap)
        }
    }

    // Extract elements
    result := make([]int, k)
    for i := 0; i < k; i++ {
        result[i] = heap.Pop(minHeap).([2]int)[1]
    }
    return result
}

type FreqHeap [][2]int

func (h FreqHeap) Len() int           { return len(h) }
func (h FreqHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h FreqHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *FreqHeap) Push(x interface{}) {
    *h = append(*h, x.([2]int))
}

func (h *FreqHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

def top_k_frequent(nums, k)
    freq = Hash.new(0)
    nums.each { |num| freq[num] += 1 }

    min_heap = []

    # Add to heap [frequency, element] pairs
    freq.each do |num, count|
        min_heap << [count, num]
        min_heap.sort!

        # Keep only k most frequent
        if min_heap.length > k
            min_heap.shift
        end
    end

    # Extract elements
    min_heap.map { |pair| pair[1] }
end

class MedianFinder {
    constructor() {
        this.maxHeap = new PriorityQueue((a, b) => b - a); // Lower half
        this.minHeap = new PriorityQueue(); // Upper half
    }

    addNum(num) {
        // Add to max-heap, then move largest to min-heap
        this.maxHeap.push(num);
        this.minHeap.push(this.maxHeap.pop());

        // Balance: max-heap should have equal or one more element
        if (this.maxHeap.heap.length < this.minHeap.heap.length) {
            this.maxHeap.push(this.minHeap.pop());
        }
    }

    findMedian() {
        if (this.maxHeap.heap.length > this.minHeap.heap.length) {
            return this.maxHeap.peek();
        } else {
            return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
        }
    }
}

import heapq

class MedianFinder:
    def __init__(self):
        self.max_heap = []  # Lower half (negated for max-heap)
        self.min_heap = []  # Upper half

    def addNum(self, num):
        # Add to max-heap, then move largest to min-heap
        heapq.heappush(self.max_heap, -num)
        heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))

        # Balance: max-heap should have equal or one more element
        if len(self.max_heap) < len(self.min_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def findMedian(self):
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        else:
            return (-self.max_heap[0] + self.min_heap[0]) / 2

class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // Lower half
    private PriorityQueue<Integer> minHeap; // Upper half

    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        // Add to max-heap, then move largest to min-heap
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());

        // Balance: max-heap should have equal or one more element
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        } else {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }
}

class MedianFinder {
private:
    priority_queue<int> maxHeap; // Lower half
    priority_queue<int, vector<int>, greater<int>> minHeap; // Upper half

public:
    void addNum(int num) {
        // Add to max-heap, then move largest to min-heap
        maxHeap.push(num);
        minHeap.push(maxHeap.top());
        maxHeap.pop();

        // Balance: max-heap should have equal or one more element
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }

    double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.top();
        } else {
            return (maxHeap.top() + minHeap.top()) / 2.0;
        }
    }
};

type MedianFinder struct {
    maxHeap *IntMaxHeap
    minHeap *IntHeap
}

func Constructor() MedianFinder {
    return MedianFinder{
        maxHeap: &IntMaxHeap{},
        minHeap: &IntHeap{},
    }
}

func (mf *MedianFinder) AddNum(num int) {
    heap.Push(mf.maxHeap, num)
    heap.Push(mf.minHeap, heap.Pop(mf.maxHeap).(int))

    // Balance: max-heap should have equal or one more element
    if mf.maxHeap.Len() < mf.minHeap.Len() {
        heap.Push(mf.maxHeap, heap.Pop(mf.minHeap).(int))
    }
}

func (mf *MedianFinder) FindMedian() float64 {
    if mf.maxHeap.Len() > mf.minHeap.Len() {
        return float64((*mf.maxHeap)[0])
    } else {
        return float64((*mf.maxHeap)[0]+(*mf.minHeap)[0]) / 2.0
    }
}

class MedianFinder
    def initialize
        @max_heap = []  # Lower half
        @min_heap = []  # Upper half
    end

    def add_num(num)
        # Add to max-heap, then move largest to min-heap
        @max_heap << num
        @max_heap.sort!.reverse!
        @min_heap << @max_heap.shift
        @min_heap.sort!

        # Balance: max-heap should have equal or one more element
        if @max_heap.length < @min_heap.length
            @max_heap << @min_heap.shift
            @max_heap.sort!.reverse!
        end
    end

    def find_median
        if @max_heap.length > @min_heap.length
            @max_heap[0]
        else
            (@max_heap[0] + @min_heap[0]) / 2.0
        end
    end
end

function mergeKLists(lists) {
    class ListNode {
        constructor(val = 0, next = null) {
            this.val = val;
            this.next = next;
        }
    }

    const minHeap = new PriorityQueue((a, b) => a.val - b.val);

    // Add first node from each non-empty list
    for (const list of lists) {
        if (list) minHeap.push(list);
    }

    const dummy = new ListNode();
    let current = dummy;

    while (!minHeap.isEmpty()) {
        const node = minHeap.pop();
        current.next = node;
        current = current.next;

        // Add next node from same list
        if (node.next) {
            minHeap.push(node.next);
        }
    }

    return dummy.next;
}

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists):
    import heapq

    min_heap = []

    # Add first node from each non-empty list
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(min_heap, (head.val, i, head))

    dummy = ListNode()
    current = dummy

    while min_heap:
        val, i, node = heapq.heappop(min_heap)
        current.next = node
        current = current.next

        # Add next node from same list
        if node.next:
            heapq.heappush(min_heap, (node.next.val, i, node.next))

    return dummy.next

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);

        // Add first node from each non-empty list
        for (ListNode head : lists) {
            if (head != null) {
                minHeap.offer(head);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (!minHeap.isEmpty()) {
            ListNode node = minHeap.poll();
            current.next = node;
            current = current.next;

            // Add next node from same list
            if (node.next != null) {
                minHeap.offer(node.next);
            }
        }

        return dummy.next;
    }
}

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> minHeap(cmp);

        // Add first node from each non-empty list
        for (ListNode* head : lists) {
            if (head) {
                minHeap.push(head);
            }
        }

        ListNode dummy(0);
        ListNode* current = &dummy;

        while (!minHeap.empty()) {
            ListNode* node = minHeap.top();
            minHeap.pop();
            current->next = node;
            current = current->next;

            // Add next node from same list
            if (node->next) {
                minHeap.push(node->next);
            }
        }

        return dummy.next;
    }
};

func mergeKLists(lists []*ListNode) *ListNode {
    minHeap := &ListNodeHeap{}
    heap.Init(minHeap)

    // Add first node from each non-empty list
    for _, head := range lists {
        if head != nil {
            heap.Push(minHeap, head)
        }
    }

    dummy := &ListNode{}
    current := dummy

    for minHeap.Len() > 0 {
        node := heap.Pop(minHeap).(*ListNode)
        current.Next = node
        current = current.Next

        // Add next node from same list
        if node.Next != nil {
            heap.Push(minHeap, node.Next)
        }
    }

    return dummy.Next
}

type ListNode struct {
    Val  int
    Next *ListNode
}

type ListNodeHeap []*ListNode

func (h ListNodeHeap) Len() int           { return len(h) }
func (h ListNodeHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h ListNodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *ListNodeHeap) Push(x interface{}) {
    *h = append(*h, x.(*ListNode))
}

func (h *ListNodeHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

class ListNode
    attr_accessor :val, :next

    def initialize(val = 0, next = nil)
        @val = val
        @next = next
    end
end

def merge_k_lists(lists)
    min_heap = []

    # Add first node from each non-empty list
    lists.each do |head|
        if head
            min_heap << [head.val, head]
            min_heap.sort!
        end
    end

    dummy = ListNode.new(0)
    current = dummy

    while !min_heap.empty?
        val, node = min_heap.shift
        current.next = node
        current = current.next

        # Add next node from same list
        if node.next
            min_heap << [node.next.val, node.next]
            min_heap.sort!
        end
    end

    dummy.next
end

function maxSlidingWindow(nums, k) {
    const result = [];
    const deque = []; // Store indices

    for (let i = 0; i < nums.length; i++) {
        // Remove elements out of current window
        while (deque.length > 0 && deque[0] <= i - k) {
            deque.shift();
        }

        // Remove elements smaller than current element
        while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
        }

        deque.push(i);

        // Add to result when window is complete
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
}

def maxSlidingWindow(nums, k):
    from collections import deque

    result = []
    dq = deque()  # Store indices

    for i in range(len(nums)):
        # Remove elements out of current window
        while dq and dq[0] <= i - k:
            dq.popleft()

        # Remove elements smaller than current element
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()

        dq.append(i)

        # Add to result when window is complete
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {
            // Remove elements out of current window
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            // Remove elements smaller than current element
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }

            deque.offerLast(i);

            // Add to result when window is complete
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }
}

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> dq;  // Store indices

        for (int i = 0; i < nums.size(); i++) {
            // Remove elements out of current window
            while (!dq.empty() && dq.front() <= i - k) {
                dq.pop_front();
            }

            // Remove elements smaller than current element
            while (!dq.empty() && nums[dq.back()] <= nums[i]) {
                dq.pop_back();
            }

            dq.push_back(i);

            // Add to result when window is complete
            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }

        return result;
    }
};

func maxSlidingWindow(nums []int, k int) []int {
    result := make([]int, 0, len(nums)-k+1)
    dq := make([]int, 0)

    for i := 0; i < len(nums); i++ {
        // Remove elements out of current window
        for len(dq) > 0 && dq[0] <= i-k {
            dq = dq[1:]
        }

        // Remove elements smaller than current element
        for len(dq) > 0 && nums[dq[len(dq)-1]] <= nums[i] {
            dq = dq[:len(dq)-1]
        }

        dq = append(dq, i)

        // Add to result when window is complete
        if i >= k-1 {
            result = append(result, nums[dq[0]])
        }
    }

    return result
}