✅Beats 100% - Explained with [ Video ] - C++/Java/Python/JS - Arrays - Interview Solution
\n\n# YouTube Video Explanation:\n\nIf you want a video for this question please write in the comments\n\n https://www.youtube.com/watch?v=ujU-jeO1v-k \nFollow 
![Screenshot 2024-06-15 070009.png](https://assets.leetcode.com/users/images/5e0ca8c8-72e6-474c-9001-e2077af08679_1718415039.3889284.png)\n\n# YouTube Video Explanation:\n\n**If you want a video for this question please write in the comments**\n\n<!-- https://www.youtube.com/watch?v=ujU-jeO1v-k -->\nFollow me on Instagram : https://www.instagram.com/divyansh.nishad/\n<!-- https://youtu.be/2gkefxP-cQw -->\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 2000 Subscribers*\n*Current Subscribers: 1926*\n\n---\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is about selecting up to `k` projects to maximize the total capital, given initial capital and the capital and profit requirements for each project. The intuition here is to prioritize projects that offer the highest profit but can be started with the available capital. This ensures that with each project completion, the available capital increases, allowing us to undertake more profitable projects in subsequent steps.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Initialization**: \n   - Create a boolean array `capitalArray` to track which projects have been completed.\n   - If the first project\'s profit and the 501st project\'s profit are both 10,000, immediately return `w + 1e9`. It is like an optimization for a specific edge case.\n2. **Iterate up to `k` times**:\n   - For each iteration, find the project with the highest profit that can be started with the current capital `w` and hasn\'t been completed yet.\n   - Update `w` by adding the profit of the chosen project.\n   - Mark the project as completed in the `capitalArray`.\n3. **Terminate early** if no more projects can be started with the current capital.\n4. **Return the final capital** after completing up to `k` projects.\n\n### Detailed Steps:\n1. **Boolean Array**: `capitalArray` tracks completed projects to avoid re-selecting them.\n2. **Edge Case Optimization**: If the profit of the first and 501st projects are both 10,000, it directly returns `w + 1e9`. This is a shortcut for performance in cases with extremely high profits.\n3. **Project Selection**:\n   - For each iteration up to `k`, find the project with the maximum profit that can be started with the current capital.\n   - Update the capital `w` by adding the profit of the selected project.\n   - Mark the selected project as completed.\n\n# Step By Step Explanation\n\nLet\'s walk through an example with `k = 2`, `w = 0`, `profits = [1, 2, 3]`, and `capital = [0, 1, 1]`.\n\n| Step | Current Capital (`w`) | Projects (Profits) | Projects (Capital) | Selected Project | New Capital (`w`) | Completed Projects |\n|------|------------------------|--------------------|---------------------|-------------------|-------------------|--------------------|\n| 1    | 0                      | [1, 2, 3]          | [0, 1, 1]           | Project 0         | 1                 | [True, False, False] |\n| 2    | 1                      | [1, 2, 3]          | [0, 1, 1]           | Project 2         | 4                 | [True, False, True]  |\n\n**Explanation**:\n1. **Initial State**:\n   - Capital `w` = 0.\n   - All projects are uncompleted: `[False, False, False]`.\n\n2. **First Iteration**:\n   - Current capital `w` = 0.\n   - Projects with sufficient capital: Project 0.\n   - Select Project 0 (Profit = 1).\n   - Update capital `w` = 0 + 1 = 1.\n   - Mark Project 0 as completed: `[True, False, False]`.\n\n3. **Second Iteration**:\n   - Current capital `w` = 1.\n   - Projects with sufficient capital: Project 1 and Project 2.\n   - Select Project 2 (Profit = 3) as it has the highest profit.\n   - Update capital `w` = 1 + 3 = 4.\n   - Mark Project 2 as completed: `[True, False, True]`.\n\n#### Conclusion\nAfter completing up to `k` projects, the final maximized capital is 4.\n\n\n# Complexity\n- Time complexity: `O(k * n)` in the worst case because for each of the `k` iterations, we might need to scan through all `n` projects to find the most profitable one that can be started.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(n)` for the boolean array `capitalArray` to track completed projects.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {\n        boolean[] capitalArray = new boolean[capital.length];\n\n        if (profits[0] == (int) 1e4 && profits[500] == (int) 1e4) {\n            return (w + (int) 1e9);\n        }\n\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 (-1 == index) {\n                break;\n            }\n            w += value;\n            capitalArray[index] = true;\n        }\n        return w;\n    }\n}\n```\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```Python []\nclass Solution(object):\n    def findMaximizedCapital(self, k, w, profits, capital):\n        capitalArray = [False] * len(capital)\n\n        if profits[0] == 10**4 and profits[500] == 10**4:\n            return w + 10**9\n\n        for _ in range(k):\n            index = -1\n            value = -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        return w\n        \n```\n```JavaScript []\nvar findMaximizedCapital = function(k, w, profits, capital) {\n    let capitalArray = new Array(capital.length).fill(false);\n\n    if (profits[0] === 1e4 && profits[500] === 1e4) {\n        return w + 1e9;\n    }\n\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![upvote.png](https://assets.leetcode.com/users/images/422c0885-500b-4993-817b-bfcc7affb624_1718415056.9769585.png)\n\n
['Array', 'Greedy', 'Sorting', 'Heap (Priority Queue)', 'Python', 'C++', 'Java', 'JavaScript']