Heaps¶

/*
QUESTION:
Implement a min heap with all the required methods.

APPROACH:
A min heap is a binary tree-based data structure where the value of each parent node is less than or equal to the values of its children. The heapify operation is used to maintain the heap property, where a node is compared with its children and swapped if necessary.

In the given code, the minHeap class is implemented using a vector to store the elements. The heapify function is used to maintain the heap property by comparing the node with its left and right children and swapping if necessary. The bottomUpHeapify function is used to fix the heap property from a child node to its parent node.

The insert function adds an element to the heap by appending it to the vector and performing bottom-up heapification. The removeMin function removes the minimum element from the heap by replacing it with the last element, removing the last element, and then performing heapify. The minElement function returns the minimum element of the heap.

COMPLEXITY ANALYSIS:
- The heapify operation takes O(log n) time complexity, where n is the number of elements in the heap.
- The bottomUpHeapify operation also takes O(log n) time complexity.
- The insert operation takes O(log n) time complexity.
- The removeMin operation takes O(log n) time complexity.
- The minElement operation takes O(1) time complexity.

Overall, the time complexity of the minHeap class methods is O(log n), where n is the number of elements in the heap.

CODE:-
*/


class minHeap {
public:
    vector<int> pq;

    // Function to heapify the heap.
    void heapify(int node) {
        int leftChild = (2 * node) + 1;
        int rightChild = (2 * node) + 2;
        int smallest = node;

        if (leftChild < pq.size() && pq[leftChild] < pq[smallest])
            smallest = leftChild;

        if (rightChild < pq.size() && pq[rightChild] < pq[smallest])
            smallest = rightChild;

        if (smallest != node) {
            swap(pq[node], pq[smallest]);
            heapify(smallest);
        }
    }

    void bottomUpHeapify(int node) {
        int parent = (node - 1) / 2;
        if (parent >= 0 && pq[parent] > pq[node]) {
            swap(pq[parent], pq[node]);
            bottomUpHeapify(parent);
        }
    }

    // Function to insert 'val' in the heap.
    void insert(int val) {
        pq.push_back(val);
        bottomUpHeapify(pq.size() - 1);
    }

    // Function to remove the minimum element.
    void removeMin() {
        pq[0] = pq.back();
        pq.pop_back();
        heapify(0);
    }

    // Function to return the minimum element.
    int minElement() {
        return (pq.empty()) ? -1 : pq[0];
    }
};

/*
QUESTION:
Given an array A of size N, the task is to check if the given array represents a Binary Max Heap.

APPROACH:
1. Start from the root node and recursively check if the current node satisfies the max-heap property.
2. The max-heap property states that every node should be greater than all of its descendants.
3. Check if the current node is greater than its left and right children.
4. Recursively check the max-heap property for the left and right subtrees.
5. If the current node is greater and the left and right subtrees also satisfy the max-heap property, then the array represents a binary max heap.

The solve function is implemented to recursively check the max-heap property for each node. It checks if the current node is greater than its left and right children. If the current node is greater and the left and right subtrees also satisfy the max-heap property, then the array represents a binary max heap.

The isMaxHeap function is the main function that calls the solve function with the root node (index 0) and the size of the array. It returns true if the array represents a binary max heap, and false otherwise.

TIME COMPLEXITY:
The time complexity of the isMaxHeap function is O(N), where N is the size of the array. This is because we need to check the max-heap property for each node in the array.

SPACE COMPLEXITY:
The space complexity is O(N) due to the recursive calls in the solve function.
*/

bool solve(int a[], int node, int n) {
    if (node >= n)
        return true;

    int left = (2 * node) + 1;
    int right = (2 * node) + 2;

    return (solve(a, left, n) && solve(a, right, n) && (a[node] > a[left] && a[node] > a[right]));
}

bool isMaxHeap(int a[], int n) {
    return solve(a, 0, n);
}

/*
QUESTION:
You are given an array arr of N integers representing a min Heap. The task is to convert it to a max Heap.

A max-heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node.

APPROACH:
To convert a min-heap to a max-heap, we need to rearrange the elements of the array in such a way that the max-heap property is satisfied.
1. Start from the last internal node of the heap (N/2 - 1) and perform heapify on each internal node.
2. Heapify a node by comparing it with its left and right children and swapping if necessary.
3. Continue this process for all internal nodes until the entire heap is converted to a max-heap.

The heapify function is implemented to compare a node with its left and right children and swap if necessary to satisfy the max-heap property.

The convertMinToMaxHeap function is the main function that converts the given min-heap to a max-heap. It starts from the last internal node (N/2 - 1) and performs heapify on each internal node.

TIME COMPLEXITY:
The time complexity of the convertMinToMaxHeap function is O(N), where N is the size of the array. This is because we need to perform heapify on each internal node of the heap.

SPACE COMPLEXITY:
The space complexity is O(1) as no extra space is used in the conversion process.
*/

void heapify(vector<int>& arr, int node) {
    int left = (2 * node) + 1;
    int right = (2 * node) + 2;
    int largest = node;
    int n = arr.size();

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != node) {
        swap(arr[node], arr[largest]);
        heapify(arr, largest);
    }
}

void convertMinToMaxHeap(vector<int>& arr, int N) {
    for (int i = (N / 2) - 1; i >= 0; i--) {
        heapify(arr, i);
    }
}

/*
QUESTION:
Given an integer array nums and an integer k, return the kth largest element in the array.

APPROACH:
To find the kth largest element in the array, we can use a min-heap of size k.
1. Initialize a min-heap (priority queue) of size k.
2. Insert the first k elements of the array into the min-heap.
3. For the remaining elements in the array, if an element is larger than the top element of the min-heap, replace the top element with the current element and heapify to maintain the min-heap property.
4. After processing all the elements, the top element of the min-heap will be the kth largest element in the array.

The findKthLargest function implements this approach. It uses a min-heap (priority queue) to find the kth largest element in the array without sorting the entire array.

TIME COMPLEXITY:
The time complexity of the findKthLargest function is O(N log k), where N is the size of the array. Inserting elements into the min-heap and heapifying take O(log k) time, and we do this for N-k elements. The overall time complexity is dominated by the heap operations.

SPACE COMPLEXITY:
The space complexity is O(k) as we need to store k elements in the min-heap.
*/

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < k; i++) {
        pq.push(nums[i]);
    }
    for (int i = k; i < nums.size(); i++) {
        if (nums[i] > pq.top()) {
            pq.pop();
            pq.push(nums[i]);
        }
    }
    return pq.top();
}

/*
QUESTION:
Given an array arr[] and an integer K, where K is smaller than the size of the array, the task is to find the Kth smallest element in the given array. It is given that all array elements are distinct.

APPROACH:
To find the Kth smallest element in the array, we can use a max-heap of size K.
1. Initialize a max-heap (priority queue) of size K.
2. Insert the first K elements of the array into the max-heap.
3. For the remaining elements in the array, if an element is smaller than the top element of the max-heap, replace the top element with the current element and heapify to maintain the max-heap property.
4. After processing all the elements, the top element of the max-heap will be the Kth smallest element in the array.

The findKthLargest function implements this approach. It uses a max-heap (priority queue) to find the Kth smallest element in the array without sorting the entire array.

TIME COMPLEXITY:
The time complexity of the findKthLargest function is O(N log K), where N is the size of the array. Inserting elements into the max-heap and heapifying take O(log K) time, and we do this for N-K elements. The overall time complexity is dominated by the heap operations.

SPACE COMPLEXITY:
The space complexity is O(K) as we need to store K elements in the max-heap.
*/

int findKthSmallest(vector<int>& arr, int K) {
    priority_queue<int> pq;
    for (int i = 0; i < K; i++) {
        pq.push(arr[i]);
    }
    for (int i = K; i < arr.size(); i++) {
        if (arr[i] < pq.top()) {
            pq.pop();
            pq.push(arr[i]);
        }
    }
    return pq.top();
}

/*
QUESTION:
Given K sorted arrays arranged in the form of a matrix of size K*K, the task is to merge them into one sorted array.

APPROACH:
To merge K sorted arrays, we can use a min-heap (priority queue) to store the smallest elements from each array.
1. Create a min-heap of size K to store the current smallest elements from each array.
2. Initialize the min-heap with the first element from each array.
3. While the min-heap is not empty, extract the smallest element from the min-heap, add it to the merged array, and replace it with the next element from the same array.
4. Repeat step 3 until all elements from all arrays are processed.

The mergeKArrays function implements this approach. It uses a min-heap (priority queue) to merge K sorted arrays into one sorted array.

TIME COMPLEXITY:
The time complexity of the mergeKArrays function is O(K^2 log K), where K is the size of each array. Inserting elements into the min-heap and extracting the minimum element take O(log K) time, and we do this for K^2 elements. The overall time complexity is dominated by the heap operations.

SPACE COMPLEXITY:
The space complexity is O(K) as we need to store K elements in the min-heap.
*/

typedef pair<int, pair<int, int>> triplet;

vector<int> mergeKArrays(vector<vector<int>>& arr, int K) {
    priority_queue<triplet, vector<triplet>, greater<triplet>> pq;

    for (int i = 0; i < K; i++) {
        pq.push({arr[i][0], {i, 0}});
    }

    vector<int> mergedArray;

    while (!pq.empty()) {
        triplet mini = pq.top();
        pq.pop();

        mergedArray.push_back(mini.first);

        int row = mini.second.first;
        int col = mini.second.second;

        if (col + 1 < K) {
            pq.push({arr[row][col + 1], {row, col + 1}});
        }
    }

    return mergedArray;
}

/*
QUESTION:
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

APPROACH:
To merge K sorted linked lists, we can use a min-heap (priority queue) to store the smallest nodes from each list.
1. Create a min-heap of size K to store the current smallest nodes from each list.
2. Initialize the min-heap with the head node from each list.
3. While the min-heap is not empty, extract the smallest node from the min-heap, add it to the merged linked list, and replace it with the next node from the same list.
4. Repeat step 3 until all nodes from all lists are processed.

The mergeKLists function implements this approach. It uses a min-heap (priority queue) to merge K sorted linked lists into one sorted linked list.

TIME COMPLEXITY:
The time complexity of the mergeKLists function is O(N log K), where N is the total number of nodes across all lists and K is the number of linked lists. Inserting nodes into the min-heap and extracting the minimum node take O(log K) time, and we do this for N nodes. The overall time complexity is dominated by the heap operations.

SPACE COMPLEXITY:
The space complexity is O(K) as we need to store K nodes in the min-heap.
*/

ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<pair<int, ListNode*>, vector<pair<int, ListNode*>>, greater<pair<int, ListNode*>>> pq;

    for (int i = 0; i < lists.size(); i++) {
        if (lists[i]) {
            pq.push({lists[i]->val, lists[i]});
        }
    }

    ListNode* dummy = new ListNode();
    ListNode* ans = dummy;

    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();
        dummy->next = new ListNode(top.first);
        dummy = dummy->next;
        ListNode* nxt = top.second->next;
        if (nxt) {
            pq.push({nxt->val, nxt});
        }
    }

    return ans->next;
}

/*
QUESTION:
Given an array of integers arr, replace each element with its rank.

APPROACH:
To assign ranks to the elements in the array, we can use a min-heap (priority queue) to sort the elements in ascending order along with their indices.
1. Create a min-heap to store pairs of (element, index) in ascending order.
2. Push each element along with its index into the min-heap.
3. Initialize the rank as 0 and the previous element as INT_MIN (an arbitrary value that never matches any element).
4. While the min-heap is not empty, extract the minimum element from the min-heap.
5. If the current element is different from the previous element, increment the rank.
6. Assign the rank to the element at its corresponding index in the result array.
7. Repeat steps 4-6 until all elements are processed.

The arrayRankTransform function implements this approach. It uses a min-heap to assign ranks to the elements in the array.

TIME COMPLEXITY:
The time complexity of the arrayRankTransform function is O(N log N), where N is the size of the array. Inserting elements into the min-heap and extracting the minimum element take O(log N) time, and we do this for N elements. The overall time complexity is dominated by the heap operations.

SPACE COMPLEXITY:
The space complexity is O(N) as we need to store N elements in the min-heap and the result array.
*/

vector<int> arrayRankTransform(vector<int>& arr) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i = 0; i < arr.size(); i++) {
        pq.push({arr[i], i});
    }
    vector<int> ans(arr.size());
    int rank = 0;
    int prev = INT_MIN; // an arbitrary value which never matches
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();
        if (top.first != prev) {
            rank++;
        }
        ans[top.second] = rank;
        prev = top.first;
    }
    return ans;
}

/*
QUESTION:
Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

APPROACH:
To minimize the total time, we need to consider the task with the maximum frequency. Let's assume the maximum frequency is maxfreq. The CPU will need at least (maxfreq - 1) intervals of cooldown time between the executions of the tasks with the maximum frequency.

1. Create a frequency map to count the occurrences of each task.
2. Find the maximum frequency maxfreq.
3. Calculate the total number of intervals required by multiplying (maxfreq - 1) with the cooldown period n.
4. Iterate through the frequency map and count the number of tasks with the maximum frequency. Add this count to the total number of intervals.
5. Return the maximum of the total number of intervals and the total number of tasks.

The leastInterval function implements this approach.

TIME COMPLEXITY:
The time complexity of the leastInterval function is O(N), where N is the number of tasks. We iterate through the tasks twice: once to calculate the frequencies and find the maximum frequency, and once to count the number of tasks with the maximum frequency. Both iterations take O(N) time.

SPACE COMPLEXITY:
The space complexity is O(1) because the frequency map has a fixed number of unique tasks (26 lowercase letters).
*/

int leastInterval(vector<char>& tasks, int n) {
    int siz = tasks.size();
    unordered_map<char, int> mp;
    for (auto it : tasks)
        mp[it]++;
    int maxfreq = INT_MIN;
    for (auto it : mp)
        maxfreq = max(maxfreq, it.second);
    int ans = (maxfreq - 1) * (n + 1);
    // number of elements having maxfreq
    for (auto it : mp) {
        if (it.second == maxfreq)
            ans++;
    }
    return max(ans, siz);
}

/*
QUESTION:
Given an array of integers nums and a positive integer k, check whether it is possible to divide this array into sets of k consecutive numbers.

Return true if it is possible. Otherwise, return false.

Example:

Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].
*/

/*
APPROACH:
1. First, we check if the array size is divisible by k. If not, it is not possible to divide the array into sets of k consecutive numbers.
2. We use a frequency map mp to count the occurrences of each element in the array.
3. We sort the array nums in ascending order.
4. For each number num in nums, we check if it is still available (mp[num] > 0).
5. If num is available, we iterate from num + 1 to num + k - 1 and check if each number is available in mp as well. If any number is not available, we return false.
6. If all numbers are available, we decrement the counts in mp accordingly.
7. If we reach the end of the loop, it means it is possible to divide the array into sets of k consecutive numbers, and we return true.
*/

/*
COMPLEXITY ANALYSIS:
- Time complexity: O(n log n), where n is the size of the input array nums. The complexity is dominated by the sorting step.
- Space complexity: O(n), to store the frequency map mp.
*/

bool isPossibleDivide(vector<int>& nums, int k) {
    if (nums.size() % k != 0) {
        return false;
    }
    unordered_map<int, int> mp;
    for (auto it : nums)
        mp[it]++;
    sort(nums.begin(), nums.end());

    for (auto num : nums) {
        if (mp[num] > 0) {
            for (int i = num + 1; i < num + k; i++) {
                if (mp[i] == 0)
                    return false;
                mp[i]--;
            }
            mp[num]--;
        }
    }
    return true;
}

/*
QUESTION:
Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and is able to see the 10 most recent tweets in the user's news feed.

APPROACH:
To design the Twitter class, we can use the following data structures:

1. unordered_map<int, vector<int>> following: This map stores the users and the list of users they are following. Each user follows themselves initially.
2. unordered_map<int, deque<pair<int, int>>> posts: This map stores the tweets of each user. Each tweet is represented by a pair of (timestamp, tweetId). We use a deque to maintain the most recent 10 tweets for each user.
3. int time: This variable keeps track of the timestamp for tweets.

The Twitter class provides the following methods:

1. Twitter(): Initializes the Twitter object.
2. void postTweet(int userId, int tweetId): Composes a new tweet with ID tweetId by the user userId. The tweet is added to the posts map with the current timestamp. If the size of the user's tweets exceeds 10, the oldest tweet is removed.
3. vector<int> getNewsFeed(int userId): Retrieves the 10 most recent tweet IDs in the user's news feed. It iterates through the users that the given user follows and adds their tweets to a set. The set is sorted in descending order of timestamps. The first 10 tweets are returned.
4. void follow(int followerId, int followeeId): The user with ID followerId starts following the user with ID followeeId. The followeeId is added to the followerId's following list.
5. void unfollow(int followerId, int followeeId): The user with ID followerId stops following the user with ID followeeId. The followeeId is removed from the followerId's following list.

The code provided implements the Twitter class with the above approach.

TIME COMPLEXITY:
The time complexity of the postTweet method is O(1) for adding a tweet to the user's posts.
The time complexity of the getNewsFeed method is O(F * P * log(P)) where F is the number of users the given user follows and P is the maximum number of posts by any user. The method iterates through the posts of each followed user, which takes O(F * P) time, and sorts the tweets, which takes O(P * log(P)) time.
The time complexity of the follow and unfollow methods is O(1) for adding or removing a user from the following list.

SPACE COMPLEXITY:
The space complexity is O(U + P) where U is the number of users and P is the total number of posts. The posts map stores the tweets of each user, and the size of the posts map is bounded by the number of users. The maximum size of the posts deque for each user is 10.
*/

unordered_map<int, vector<int>> following; // key = userId, value = followeeIds
unordered_map<int, deque<pair<int, int>>> posts; // key = userId, value = posts corresponding to that userId
int time;

Twitter() {
    time = 0;
}

void postTweet(int userId, int tweetId) {
    following[userId].push_back(userId); // each user will follow themselves

    if (posts.find(userId) != posts.end() && posts[userId].size() > 10)
        posts[userId].pop_back();

    posts[userId].push_front({time, tweetId});
    time++;
}

vector<int> getNewsFeed(int userId) {
    vector<int> ans;
    set<pair<int, int>, greater<pair<int, int>>> allposts;
    for (int i = 0; i < following[userId].size(); i++) {
        int followe = following[userId][i];
        for (int i = 0; i < posts[followe].size(); i++) {
            allposts.insert(posts[followe][i]);
        }
    }
    int siz = allposts.size();
    int n = min(10, siz);
    for (auto it = allposts.begin(); it != allposts.end() && n; it++) {
        ans.push_back(it->second);
        n--;
    }
    return ans;
}

void follow(int followerId, int followeeId) {
    following[followerId].push_back(followeeId);
}

void unfollow(int followerId, int followeeId) {
    for (int i = 0; i < following[followerId].size(); i++) {
        if (following[followerId][i] == followeeId) {
            following[followerId].erase(following[followerId].begin() + i);
            return;
        }
    }
}

/*
Question:
There are given N ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to the sum of their lengths. The task is to connect the ropes with the minimum cost. Given an array arr[] containing the lengths of the ropes.

Example:
Input: arr[] = {4, 3, 2, 6}
Output: 29
Explanation: The minimum cost is obtained by connecting ropes in the following order:
1. Connect ropes of length 2 and 3, cost = 2 + 3 = 5, resulting array = {4, 5, 6}
2. Connect ropes of length 4 and 5, cost = 4 + 5 = 9, resulting array = {9, 6}
3. Connect ropes of length 6 and 9, cost = 6 + 9 = 15, resulting array = {15}
Total cost = 5 + 9 + 15 = 29

Approach:
1. Use a priority queue (min heap) to store the lengths of the ropes.
2. Push all the rope lengths into the priority queue.
3. While the priority queue has more than one element:
   - Extract the two smallest ropes from the priority queue.
   - Add their lengths together to get the cost.
   - Push the sum back into the priority queue.
   - Update the total cost.
4. Return the total cost as the minimum cost of connecting the ropes.

Complexity Analysis:
- Time complexity: O(n log n), where n is the number of ropes. Inserting and extracting elements from the priority queue take O(log n) time, and the loop runs for (n-1) iterations.
- Space complexity: O(n) to store the rope lengths in the priority queue.

Code:
*/

long long connectRopes(int* arr, int n)
{
    long long ans = 0;
    priority_queue<int, vector<int>, greater<int>> pq;

    // Push all rope lengths into the priority queue
    for (int i = 0; i < n; i++) {
        pq.push(arr[i]);
    }

    // Connect ropes until only one rope remains
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        int sum = a + b;
        ans += sum;

        // Push the sum back into the priority queue if there are more than one rope remaining
        if (!pq.empty()) {
            pq.push(sum);
        }
    }

    return ans;
}

/*
Question:
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.

Example:
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

Approach:
- Use a min heap (priority queue) to store the k largest elements.
- Initialize the min heap with the first k elements from the stream (nums) in the constructor.
- For each subsequent element in the stream, add it to the min heap.
- If the size of the min heap exceeds k, remove the smallest element.
- The top element of the min heap represents the kth largest element.

Complexity Analysis:
- The time complexity of adding an element is O(log k) due to the insertion and removal operations in the min heap.
- The space complexity is O(k) to store the k largest elements in the min heap.

Code:
*/

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

public:
    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        for (int i = 0; i < nums.size(); i++) {
            pq.push(nums[i]);
            if (pq.size() > k) {
                pq.pop();
            }
        }
    }

    int add(int val) {
        pq.push(val);//* this is amazing to use
        if (pq.size() > k) {
            pq.pop();
        }
        return pq.top();
    }
};

/*
Question:
Given two integer arrays A and B of size N each. A sum combination is made by adding one element from array A and another element from array B. Return the maximum K valid distinct sum combinations from all the possible sum combinations. Output array must be sorted in non-increasing order.

Example:
Input:
N = 2
K = 2
A[] = {3, 2}
B[] = {1, 4}
Output: {7, 6}
Explanation: 
7 -> (A: 3) + (B: 4)
6 -> (A: 2) + (B: 4)
*/

/*
Approach:
1. Sort arrays A and B in non-increasing order.
2. Initialize a min-heap (priority_queue) to store the sum combinations.
3. Iterate over each element in array A.
4. For each element in A, iterate over each element in array B.
5. Calculate the sum of the current pair (A[i] + B[j]).
6. If the heap size is less than K, push the sum into the heap.
7. If the heap size is already K and the current sum is greater than the smallest element in the heap, pop the smallest element and push the current sum into the heap.
8. After iterating over all elements, the heap will contain the K maximum valid sum combinations in non-increasing order.
9. Store the elements of the heap in a vector and return it as the result.

COMPLEXITY ANALYSIS:-
TIME COMPLEXITY - 
Sorting the arrays A and B takes O(N log N) time.
Building the max heap takes O(N) time.
Extracting the maximum sum K times takes O(K log N) time.
Overall, the time complexity of the solution is O(N log N + K log N).
CODE:-
*/

vector<int> maxCombinations(int N, int K, vector<int> &A, vector<int> &B) {
    priority_queue<pair<int,pair<int,int>>> pq;
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    for(int i=0;i<N;i++){
        pq.push({A[i]+B[N-1],{i,N-1}});
    }
    vector<int> ans;
    while(!pq.empty() && K--)
    {
        auto it=pq.top();
        pq.pop();
        int data=it.first;
        int x=it.second.first;
        int y=it.second.second;
        ans.push_back(data);
        if(y!=0){
            pq.push({A[x]+B[y-1],{x,y-1}});
        }
    }
    return ans;
}

/*
Question:
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.
*/

/*
Approach:
1. Use two priority queues: a max heap to store the smaller half of the numbers and a min heap to store the larger half of the numbers.
2. When adding a new number:
   - If the max heap is empty or the number is smaller than the top element of the max heap, push it into the max heap.
   - Otherwise, push it into the min heap.
   - Balance the heaps by transferring the top element of the larger heap to the smaller heap if the size difference between the heaps exceeds 1.
3. When finding the median:
   - If the sizes of the heaps are equal, calculate the average of the top elements of both heaps.
   - Otherwise, return the top element of the heap with a larger size.
Complexity Analysis:

The time complexity for adding a number to the MedianFinder is O(log N), where N is the total number of elements added so far. This is because we need to maintain the two heaps and balance them if necessary, which takes logarithmic time.
The time complexity for finding the median using the findMedian() function is O(1). This is because we directly access the top elements of the heaps, which takes constant time.
The space complexity is O(N), where N is the total number of elements added. This is because we need to store the elements in the two priority queues.

CODE:-

*/

public:
    MedianFinder() {}

    void addNum(int num) {
        if (maxpq.empty() || num < maxpq.top())
            maxpq.push(num);
        else
            minpq.push(num);

        // Balancing the heaps
        int a = maxpq.size();
        int b = minpq.size();
        if (abs(a - b) > 1) {
            if (a > b) {
                int temp = maxpq.top();
                maxpq.pop();
                minpq.push(temp);
            }
            else {
                int temp = minpq.top();
                minpq.pop();
                maxpq.push(temp);
            }
        }
    }

    double findMedian() {
        int a = maxpq.size();
        int b = minpq.size();
        if (a == b)
            return (static_cast<double>(maxpq.top() + minpq.top()) / 2);
        if (a > b)
            return maxpq.top();
        return minpq.top();
    }
};

/*
Question:
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
*/

/*
Approach:
1. Create a frequency map to count the occurrences of each element in the array.
2. Use a min heap to store the k most frequent elements based on their frequencies.
3. Iterate through the frequency map and push elements into the min heap.
4. If the size of the min heap exceeds k, remove the element with the lowest frequency.
5. Finally, extract the elements from the min heap and return them in reverse order to get the k most frequent elements.
*/

/*
Complexity Analysis:
- The time complexity is O(N log K), where N is the size of the input array nums. Building the frequency map takes O(N) time, and inserting and removing elements from the min heap take O(log K) time, which is done for each element in nums.
- The space complexity is O(N) to store the frequency map and O(K) for the min heap, resulting in a total of O(N + K) space.

CODE:-
*/

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> mp;
    for (auto it : nums)
        mp[it]++;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (auto it : mp) {
        pq.push({ it.second, it.first });
        if (pq.size() > k)
            pq.pop();
    }

    vector<int> ans;
    while (!pq.empty()) {
        ans.push_back(pq.top().second);
        pq.pop();
    }

    reverse(ans.begin(), ans.end());
    return ans;
}