JavaScript | MaxHeap | Clean and Easy | 333ms - 78.72%, 77.1MB - 72.34%
Credits to https://leetcode.com/explore/interview/card/leetcodes-interview-crash-course-data-structures-and-algorithms/709/greedy/4647/ for the solution explana
Credits to https://leetcode.com/explore/interview/card/leetcodes-interview-crash-course-data-structures-and-algorithms/709/greedy/4647/ for the solution explanation.\n\n# Intuition\nGreedily choose the most profitable project that you can afford at each step. Use a heap to keep track of the most profitable project and add projects to the heap as you gain more capital.\n\n# Approach\n\nWe can choose up to k projects. Which ones should we choose? For our first project, out of all the ones we can afford with our initial capital w, we should do the one with the most profit - not only does the answer want the maximum capital, but this also opens the door to the most projects for our second choice. This logic can be applied at every step - we should always choose the project with the most profit out of the projects we can afford.\n\nHow can we figure out which projects we can afford? We can sort the inputs by capital (ascending), and then use a pointer i that stores the index of the most expensive project we can afford. Every time we complete a project and add to w, we can move i forward until i is pointing to a project that costs more than w.\n\nGreat, we know which projects we can afford at each step, but how do we find the maximum? Because we only care about the maximum at any given step, this is perfect for a heap. As we increment i, put the profit of the projects onto a max heap, and at each step, pop from the heap and add the value to w.\n\n# Complexity\n- Time complexity: O((k+n)*log(n)), where n is the number of projects given. \nThe heap\'s max size is n, which means its operations are log(n) in the worst case, and we do k + n operations (k pop operations, n push operations), also the sort at the start costs O(n*log(n)). \n\n- Space complexity: O(n) for the heap\n\n# Code\n```\n/**\n * @param {number} k\n * @param {number} w\n * @param {number[]} profits\n * @param {number[]} capital\n * @return {number}\n */\nvar findMaximizedCapital = function(k, w, profits, capital) {\n    let projects = [];\n    let heap = new MaxHeap();\n\n    for(let i = 0; i < profits.length; i++){\n        projects.push([profits[i], capital[i]]);\n    }\n\n    projects.sort((a, b) => a[1] - b[1]);\n    let x = 0;\n\n    while(projects[x] && projects[x][1] <= w){\n        heap.add(projects[x][0]);\n        x++;\n    }\n\n    while(heap.values.length > 0 && k > 0){\n        w += heap.extractMax();\n        k--;\n\n        while(projects[x] && projects[x][1] <= w){\n            heap.add(projects[x][0]);\n            x++;\n        }\n    }\n\n    return w;\n};\n\n\n/*\nCredits for MaxHeap implemenattion to: https://reginafurness.medium.com/implementing-a-max-heap-in-javascript-b3e2f788390c. \nBut I added the following line to the extractMax() to make it work:      \nif(this.values.length === 1) return this.values.pop();.\n*/\n\nclass MaxHeap {\n    constructor() {\n        this.values = [];\n    }\n\n    // index of the parent node\n    parent(index) {\n        return Math.floor((index - 1) / 2);\n    }\n\n    // index of the left child node\n    leftChild(index) {\n        return (index * 2) + 1;\n    }\n\n    // index of the right child node\n    rightChild(index) {\n        return (index * 2) + 2;\n    }\n\n    // returns true if index is of a node that has no children\n    isLeaf(index) {\n        return (\n            index >= Math.floor(this.values.length / 2) && index <= this.values.length - 1\n        )\n    }\n\n    // swap using ES6 destructuring\n    swap(index1, index2) {\n        [this.values[index1], this.values[index2]] = [this.values[index2], this.values[index1]];\n    }\n\n    heapifyDown(index) {\n        // if the node at index has children\n        if (!this.isLeaf(index)) {\n\n            // get indices of children\n            let leftChildIndex = this.leftChild(index),\n                rightChildIndex = this.rightChild(index),\n\n                // start out largest index at parent index\n                largestIndex = index;\n\n            // if the left child > parent\n            if (this.values[leftChildIndex] > this.values[largestIndex]) {\n                // reassign largest index to left child index\n                largestIndex = leftChildIndex;\n            }\n\n            // if the right child > element at largest index (either parent or left child)\n            if (this.values[rightChildIndex] >= this.values[largestIndex]) {\n                // reassign largest index to right child index\n                largestIndex = rightChildIndex;\n            }\n\n            // if the largest index is not the parent index\n            if (largestIndex !== index) {\n                // swap\n                this.swap(index, largestIndex);\n                // recursively move down the heap\n                this.heapifyDown(largestIndex);\n            }\n        }\n    }\n\n    heapifyUp(index) {\n        let currentIndex = index,\n            parentIndex = this.parent(currentIndex);\n\n        // while we haven\'t reached the root node and the current element is greater than its parent node\n        while (currentIndex > 0 && this.values[currentIndex] > this.values[parentIndex]) {\n            // swap\n            this.swap(currentIndex, parentIndex);\n            // move up the binary heap\n            currentIndex = parentIndex;\n            parentIndex = this.parent(parentIndex);\n        }\n    }\n\n    add(element) {\n        // add element to the end of the heap\n        this.values.push(element);\n        // move element up until it\'s in the correct position\n        this.heapifyUp(this.values.length - 1);\n    }\n\n    // returns value of max without removing\n    peek() {\n        return this.values[0];\n    }\n\n    // removes and returns max element\n    extractMax() {\n        if(this.values.length === 1) return this.values.pop();\n\n        if (this.values.length < 1) return \'heap is empty\';\n\n        // get max and last element\n        const max = this.values[0];\n        const end = this.values.pop();\n        // reassign first element to the last element\n        this.values[0] = end;\n        // heapify down until element is back in its correct position\n        this.heapifyDown(0);\n\n        // return the max\n        return max;\n    }\n\n    buildHeap(array) {\n        this.values = array;\n        // since leaves start at floor(nodes / 2) index, we work from the leaves up the heap\n        for(let i = Math.floor(this.values.length / 2); i >= 0; i--){\n            this.heapifyDown(i);\n        }\n    }\n\n    print() {\n        let i = 0;\n        while (!this.isLeaf(i)) {\n            console.log("PARENT:", this.values[i]);\n            console.log("LEFT CHILD:", this.values[this.leftChild(i)]);\n            console.log("RIGHT CHILD:", this.values[this.rightChild(i)]);\n            i++;\n        }      \n    }\n}\n```
['JavaScript']