Easy Java Solution | Priority Queue | Greedy | Beats 100💯✅
Find Maximized Capital\n\n## Problem Statement\n\nThe function findMaximizedCapital is designed to maximize the capital by selecting up to k projects from a lis
# Find Maximized Capital\n\n## Problem Statement\n\nThe function `findMaximizedCapital` is designed to maximize the capital by selecting up to `k` projects from a list of available projects, where each project has an associated profit and capital requirement. Given initial capital `w`, the function returns the maximum capital that can be achieved after completing up to `k` projects.\n\n## Intuition and Approach\n\nThe problem can be broken down into two main scenarios based on the initial capital `w`:\n\n1. **Scenario 1: Sufficient Initial Capital (`w >= maxCapital`)**:\n   - If the initial capital `w` is greater than or equal to the highest capital required among all projects, you can directly select up to `k` projects with the highest profits.\n   - Use a max-heap to always get the project with the highest profit. Add profits to the heap and maintain only the top `k` highest profits.\n\n2. **Scenario 2: Insufficient Initial Capital (`w < maxCapital`)**:\n   - If the initial capital `w` is less than the highest capital requirement, you must carefully select projects you can afford and iteratively increase your capital.\n   - For each of the `k` iterations, find the project with the highest profit that can be funded with the current capital `w`.\n   - Once a project is selected, its profit is added to the capital, and the project is marked as done by setting its capital requirement to a very high value to prevent it from being selected again.\n\n## Algorithm Steps\n\n1. **Determine Maximum Capital**:\n   - Iterate through the `capital` array to find the highest capital requirement (`maxCapital`).\n\n2. **Sufficient Capital Case**:\n   - If `w >= maxCapital`, use a max-heap to store the `profits`.\n   - Add all profits to the heap and keep only the top `k` values.\n   - Sum up these values and add them to `w`.\n\n3. **Insufficient Capital Case**:\n   - Iterate up to `k` times to select the best project that can be funded with the current `w`.\n   - In each iteration, find the project with the highest profit whose capital requirement is less than or equal to `w`.\n   - Update `w` by adding the selected project\'s profit and mark the project as done by setting its capital to a very high value.\n\n## Time Complexity\n\n- **Sufficient Capital Case**: \n  - Finding `maxCapital` takes `O(n)`.\n  - Adding elements to the max-heap takes `O(n log k)`, where `n` is the number of projects, and `k` is the number of projects that can be selected.\n  - The overall time complexity is `O(n + n log k)` which simplifies to `O(n log k)`.\n\n- **Insufficient Capital Case**:\n  - The outer loop runs up to `k` times, and each time, it finds the maximum profit from the available projects, which takes `O(n)`.\n  - Therefore, the time complexity is `O(kn)`.\n\n- The worst-case time complexity is `O(kn)` since `k` could be up to `n` in the worst scenario.\n\n## Space Complexity\n\n- **Sufficient Capital Case**:\n  - The max-heap requires `O(k)` space to store the highest `k` profits.\n\n- **Insufficient Capital Case**:\n  - The space complexity is `O(1)` excluding the input data as we only use a few additional variables.\n\n- Overall, the space complexity is `O(k)` due to the use of the max-heap in the sufficient capital case.\n\n## Usage\n\nTo use the `findMaximizedCapital` function, create an instance of the `Solution` class and call the method with parameters `k`, `w`, `profits`, and `capital`.\n\n```java\nSolution solution = new Solution();\nint maxCapital = solution.findMaximizedCapital(k, w, profits, capital);\n```\n\n\n\n\n\n\n# Code\n```\nclass Solution {\n    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {\n       int maxCapital = 0;\n        for(int i = 0 ; i < capital.length ; i++){\n            maxCapital = Math.max(capital[i] , maxCapital);\n        }\n        \n        if(w >= maxCapital){\n            PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {\n                @Override\n                public int compare(Integer a, Integer b) {\n                    return a - b;\n                }\n            });\n            for(int p : profits){\n                maxHeap.add(p);\n                if(maxHeap.size()>k)  maxHeap.poll();\n            }\n            for(int h: maxHeap) w+=h;\n            return w;\n        }\n        \n        \n        int index ; \n        int n = profits.length;\n        for(int i = 0 ; i < Math.min(k , n) ; i++){\n            index = -1;\n            for(int j = 0 ; j<n ; ++j){\n                 if (w >= capital[j] && (index == -1 || profits[index] < profits[j])){\n                     index = j;\n                 }\n            }\n            if(index==-1) break;\n            w+=profits[index];\n            capital[index] = Integer.MAX_VALUE;\n        }\n        return w;\n    }\n}\n```
['Array', 'Math', 'Greedy', 'Heap (Priority Queue)', 'Java']