✅ 100% | ✅ Super Easy & Clean Code | ✅ All 3 Approaches | ✅ Made Coding Fun
Approach 1 : Reverse Sort\n\n# Intuition\nReverse sort the happiness array and make a variable to keep the sum of the max happiness. Now go through the first k 
# Approach 1 : Reverse Sort\n\n# Intuition\nReverse sort the happiness array and make a variable to keep the sum of the max happiness. Now go through the first k elements and each time it will be deducted by i, (i= 0, 1, ... k-1).\n\n# Complexity\n- Time complexity:\nn be the length of the happiness array.\n$$O(nlogn)$$\n\n- Space complexity:\n n be the length of the happiness array.\n$$O(n)$$\n\n# Code\n```\nclass Solution {\n    public long maximumHappinessSum(int[] happiness, int k) {\n        \n        int n = happiness.length;\n        List<Integer> happinessList = new ArrayList<>();\n        \n        for (int i = 0 ; i < n ; i++) happinessList.add(happiness[i]);\n        \n        Collections.sort(happinessList, (a, b) -> (b - a));\n        \n        long maxHappiness = 0;\n        \n        for (int i = 0 ; i < k ; i++) {\n            maxHappiness += Math.max(happinessList.get(i)-i, 0);\n        }\n        \n        return maxHappiness;\n    }\n}\n```\n\n# Approach 2 : Priority Queue (Max Heap)\n\n# Intuition\nCreate a max heap by using priority queue and make a variable to keep the sum of the max happiness. Now go through the first k elements and each time it will be deducted by i, (i= 0, 1, ... k-1).\n\n# Complexity\n- Time complexity:\nn be the length of the happiness array.\n$$O(nlogn + klogn)$$, building priority queue takes nlogn and each iteration we are popping one element which taken logk so for k element klogk\n\n- Space complexity:\n n be the length of the happiness array.\n$$O(n)$$\n\n# Code\n```\nclass Solution {\n    public long maximumHappinessSum(int[] happiness, int k) {\n        \n        int n = happiness.length;\n        PriorityQueue<Integer> maxheap = new PriorityQueue<>((x, y) -> (y-x));\n        \n        for (int i = 0 ; i < n ; i++) maxheap.add(happiness[i]);\n        \n        long maxHappiness = 0;\n        \n        for (int i = 0 ; i < k ; i++) {\n            maxHappiness += Math.max(maxheap.poll()-i, 0);\n        }\n        \n        return maxHappiness;\n    }\n}\n```\n\n# Approach 3 : Sort\n\n# Intuition\nSort the happiness array and make a variable to keep the sum of the max happiness. Now go through the last k elements and each time it will be deducted by itr, (itr= 0, 1, ... k-1).\n\n# Complexity\n- Time complexity:\nn be the length of the happiness array.\n$$O(nlogn)$$\n\n- Space complexity:\n n be the length of the happiness array.\n$$O(n)$$\n\n# Code\n```\nclass Solution {\n    public long maximumHappinessSum(int[] happiness, int k) {\n\n        int n = happiness.length;\n        Arrays.sort(happiness);\n\n        int itr = 0, updatedValue = 0;\n        \n        long maxHappiness = 0;  \n        \n        for(int i = n-1 ; i >= n-k ; i--)\n        {\n            updatedValue = happiness[i] - itr;\n            \n            if(updatedValue > 0)\n            {\n                maxHappiness += updatedValue;\n            }\n            \n            itr++;\n        }\n        \n        return maxHappiness;\n    }\n}\n```\n\n# Submission Screenshot : \n![image](https://assets.leetcode.com/users/images/cdd9a03d-eb16-449c-8d4c-33e17ce3b1eb_1715227787.7727091.png)\n\n![image](https://assets.leetcode.com/users/images/c596e620-2790-4834-9cf6-835bba52878a_1715221893.0728772.jpeg)\n
['Array', 'Greedy', 'Sorting', 'Heap (Priority Queue)', 'Java']