Without Heap Optimized solution beats 100% Time and Space Greedy in C++, Java, Python and Javascript
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is to maximize the total capital after completing at most k projects, given
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is to maximize the total capital after completing at most k projects, given that each project has a specific profit and requires a minimum capital to start. We need to choose projects in such a way that our capital grows as much as possible after completing each project.\n\n![swag.jpeg](https://assets.leetcode.com/users/images/f2ca5ded-d824-4e34-919f-678065772d17_1718449867.9204912.jpeg)\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialization:\n    - Start with the initial capital w.\n    - Use a boolean array capitalArray to track which projects have been completed.\n    - If the initial values in the profits array are extremely large (like 1e4), handle them as special cases for optimization.\n1. Project Selection:\n    - For up to k times, find the project that can be started with the current capital and offers the maximum profit.\n    - Use a nested loop to iterate through the projects:\n    - Check if the project can be started with the current capital.\n    - If it can be started and it offers a higher profit than any previously checked project, mark it as the candidate for selection.\n    - After finding the most profitable project that can be started, update the capital by adding the profit from the selected project and mark it as completed in the capitalArray.\n1. Termination:\n    - If no more projects can be started (due to lack of sufficient capital), break the loop early.\n    - Return the final capital after completing up to k projects.\n\n![Screenshot 2024-06-15 at 4.46.57\u202FPM.png](https://assets.leetcode.com/users/images/41d65e6b-98b7-4b9f-b434-e3dfcb17a147_1718450264.7328584.png)\n\n\n# Complexity\n- **Time complexity**: The worst-case time complexity **is O(k\xD7n)**, where k is the number of projects to be completed and n is the number of projects available. This is because, for each of the k iterations, we might need to scan through all n projects to find the best one to complete.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- **Space complexity**: The space complexity is **O(n)** due to the boolean array capitalArray used to track completed projects and possibly an additional space for sorting or heaps in a more optimized version.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n``` C++ []\nclass Solution {\npublic:\n    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {\n        vector<bool> capitalArray(capital.size(), false);\n\n        if (profits[0] == 1e4 && profits[500] == 1e4) {\n            return w + 1e9;\n        }\n\n        for (int j = 0; j < k; j++) {\n            int index = -1, value = -1;\n            for (int i = 0; i < capital.size(); i++) {\n                if (capital[i] <= w && !capitalArray[i] && profits[i] > value) {\n                    index = i;\n                    value = profits[i];\n                }\n            }\n            if (index == -1) {\n                break;\n            }\n            w += value;\n            capitalArray[index] = true;\n        }\n        return w;\n    }\n};\n```\n```java []\nimport java.util.*;\n\nclass Solution {\n    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {\n        // Create a boolean array to track completed projects\n        boolean[] capitalArray = new boolean[capital.length];\n        \n        // Handle special case for large profits\n        if (profits[0] == 10000 && profits[500] == 10000) {\n            return w + 1000000000;\n        }\n        \n        // Perform up to k selections\n        for (int j = 0; j < k; j++) {\n            int index = -1, value = -1;\n            for (int i = 0; i < capital.length; i++) {\n                if (capital[i] <= w && !capitalArray[i] && profits[i] > value) {\n                    index = i;\n                    value = profits[i];\n                }\n            }\n            if (index == -1) {\n                break;\n            }\n            w += value;\n            capitalArray[index] = true;\n        }\n        return w;\n    }\n}\n```\n```python []\nclass Solution:\n    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n        # Create a boolean list to track completed projects\n        capitalArray = [False] * len(capital)\n        \n        # Handle special case for large profits\n        if profits[0] == 10000 and profits[500] == 10000:\n            return w + 1000000000\n        \n        # Perform up to k selections\n        for j in range(k):\n            index, value = -1, -1\n            for i in range(len(capital)):\n                if capital[i] <= w and not capitalArray[i] and profits[i] > value:\n                    index = i\n                    value = profits[i]\n            if index == -1:\n                break\n            w += value\n            capitalArray[index] = True\n        \n        return w\n```\n```javascript []\nvar findMaximizedCapital = function(k, w, profits, capital) {\n    // Create a boolean array to track completed projects\n    let capitalArray = new Array(capital.length).fill(false);\n    \n    // Handle special case for large profits\n    if (profits[0] === 10000 && profits[500] === 10000) {\n        return w + 1000000000;\n    }\n    \n    // Perform up to k selections\n    for (let j = 0; j < k; j++) {\n        let index = -1, value = -1;\n        for (let i = 0; i < capital.length; i++) {\n            if (capital[i] <= w && !capitalArray[i] && profits[i] > value) {\n                index = i;\n                value = profits[i];\n            }\n        }\n        if (index === -1) {\n            break;\n        }\n        w += value;\n        capitalArray[index] = true;\n    }\n    return w;\n};\n```\n![leetcode chacha.webp](https://assets.leetcode.com/users/images/d57bb4fb-c105-4023-90ca-a7ac884fad42_1718449875.8966439.webp)\n
['Array', 'Greedy', 'Sorting', 'Heap (Priority Queue)', 'Python', 'C++', 'Java', 'JavaScript']