Day 21: 100 Days of DSA

Welcome to Day 2 of my 100 Days of DSA challenge! Today, I solved five problems focused on arrays. Here's a quick look at the questions I tackled and how I approached them 🤖✨ Check out my GitHub repository for all my solutions and progress. Let’s keep learning!

A Heap is a complete binary tree data structure that satisfies the heap property: for every node, the value of its children is greater than or equal to its own value. Heaps can be implemented using priority queues and arrays, today I’ll be implementing them using arrays.

1. Implement a max heap and min heap from scratch using arrays.

1. The Heap class supports both min and max heaps using a flag (isMinHeap).

2. The insert function maintains the heap property by bubbling up newly inserted elements.

3. The extractTop removes and returns the root element, maintaining the heap property by heapifying.

#include <iostream>
#include <vector>
using namespace std;

class Heap {
    vector<int> heap;
    bool isMinHeap;

public:
    Heap(bool minHeap = false) : isMinHeap(minHeap) {}

    void insert(int val) {
        heap.push_back(val);
        int idx = heap.size() - 1;
        int parent = (idx - 1) / 2;
        while (idx > 0 && compare(heap[idx], heap[parent])) {
            swap(heap[idx], heap[parent]);
            idx = parent;
            parent = (idx - 1) / 2;
        }
    }

    int extractTop() {
        if (heap.empty()) return -1;
        int top = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        heapify(0);
        return top;
    }

    void display() {
        for (int val : heap) cout << val << " ";
        cout << endl;
    }

private:
    bool compare(int child, int parent) {
        return isMinHeap ? child < parent : child > parent;
    }

    void heapify(int idx) {
        int left = 2 * idx + 1, right = 2 * idx + 2, extreme = idx;
        if (left < heap.size() && compare(heap[left], heap[extreme])) extreme = left;
        if (right < heap.size() && compare(heap[right], heap[extreme])) extreme = right;
        if (extreme != idx) {
            swap(heap[idx], heap[extreme]);
            heapify(extreme);
        }
    }
};

int main() {
    Heap maxHeap(false), minHeap(true);
    vector<int> values = {10, 20, 5, 6, 1, 8};

    for (int val : values) {
        maxHeap.insert(val);
        minHeap.insert(val);
    }

    cout << "Max Heap: ";
    maxHeap.display();

    cout << "Min Heap: ";
    minHeap.display();

    return 0;
}

Output:

2. Solve the "k largest elements in an array" problem using a min heap.

• A min heap of size k is used to keep track of the k largest elements.

• Elements smaller than the root of the heap are discarded to ensure only the largest elements remain.

  Code:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<int> kLargestElements(vector<int>& arr, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap;

    for (int val : arr) {
        minHeap.push(val);
        if (minHeap.size() > k) minHeap.pop();
    }

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

int main() {
    vector<int> arr = {1, 23, 12, 9, 30, 2, 50};
    int k = 3;

    vector<int> result = kLargestElements(arr, k);
    cout << "K largest elements are: ";
    for (int val : result) cout << val << " ";
    cout << endl;

    return 0;
}

Output:

3. Solve the "kth smallest element in a matrix" problem using a min heap.

• A min heap stores the smallest elements from each row.

• The root of the heap is repeatedly extracted to track the kth smallest element.

Code:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Element {
    int value, row, col;
    Element(int v, int r, int c) : value(v), row(r), col(c) {}
    bool operator>(const Element& other) const { return value > other.value; }
};

int kthSmallest(vector<vector<int>>& matrix, int k) {
    priority_queue<Element, vector<Element>, greater<Element>> minHeap;

    for (int i = 0; i < matrix.size(); i++) 
        minHeap.emplace(matrix[i][0], i, 0);

    int count = 0, result = -1;
    while (!minHeap.empty()) {
        Element top = minHeap.top();
        minHeap.pop();
        result = top.value;

        if (++count == k) break;

        if (top.col + 1 < matrix[top.row].size()) 
            minHeap.emplace(matrix[top.row][top.col + 1], top.row, top.col + 1);
    }
    return result;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 5, 9},
        {10, 11, 13},
        {12, 13, 15}
    };
    int k = 8;

    cout << "Kth smallest element is: " << kthSmallest(matrix, k) << endl;

    return 0;
}

Output:

4. Solve the "merge k sorted arrays" problem using a heap.

• A min heap tracks the smallest unprocessed element across k arrays.

• Elements are merged by repeatedly extracting the smallest value and pushing the next element from the corresponding array.

Code:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Element {
    int value, arrayIndex, elementIndex;
    Element(int v, int ai, int ei) : value(v), arrayIndex(ai), elementIndex(ei) {}
    bool operator>(const Element& other) const { return value > other.value; }
};

vector<int> mergeKSortedArrays(vector<vector<int>>& arrays) {
    priority_queue<Element, vector<Element>, greater<Element>> minHeap;
    vector<int> result;

    for (int i = 0; i < arrays.size(); i++) 
        if (!arrays[i].empty()) 
            minHeap.emplace(arrays[i][0], i, 0);

    while (!minHeap.empty()) {
        Element top = minHeap.top();
        minHeap.pop();
        result.push_back(top.value);

        if (top.elementIndex + 1 < arrays[top.arrayIndex].size()) 
            minHeap.emplace(arrays[top.arrayIndex][top.elementIndex + 1], top.arrayIndex, top.elementIndex + 1);
    }

    return result;
}

int main() {
    vector<vector<int>> arrays = {
        {1, 5, 9},
        {2, 6, 8},
        {3, 7, 10}
    };

    vector<int> result = mergeKSortedArrays(arrays);
    cout << "Merged array: ";
    for (int val : result) cout << val << " ";
    cout << endl;

    return 0;
}

Output:

5. Solve the "find median from a data stream" problem using two heaps.

1. Two heaps are used:

   • A max heap (maxHeap) to store the smaller half of the numbers.

   • A min heap (minHeap) to store the larger half of the numbers.

2. Balancing the heaps:

   • Ensure the size difference between the heaps is at most 1.

   • Transfer elements between the heaps as needed to maintain balance.

3. Finding the median:

   • If maxHeap has more elements, the median is the top of maxHeap.

   • If both heaps have the same size, the median is the average of the tops of the two heaps.

This approach ensures O(log⁡n)O(\log n)O(logn) insertion time and O(1)O(1)O(1) median retrieval time.

Code:

#include <iostream>
#include <queue>
using namespace std;

class MedianFinder {
    priority_queue<int> maxHeap;                          // Left half of the data (lower values)
    priority_queue<int, vector<int>, greater<int>> minHeap; // Right half of the data (higher values)

public:
    void addNum(int num) {
        if (maxHeap.empty() || num <= maxHeap.top()) {
            maxHeap.push(num);
        } else {
            minHeap.push(num);
        }

        // Balance the heaps
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        } else if (minHeap.size() > maxHeap.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;
        }
    }
};

int main() {
    MedianFinder mf;

    mf.addNum(1);
    mf.addNum(2);
    cout << "Median: " << mf.findMedian() << endl; // Output: 1.5

    mf.addNum(3);
    cout << "Median: " << mf.findMedian() << endl; // Output: 2

    mf.addNum(4);
    cout << "Median: " << mf.findMedian() << endl; // Output: 2.5

    mf.addNum(5);
    cout << "Median: " << mf.findMedian() << endl; // Output: 3

    return 0;
}

Output:

See ya tomorrow :)