- we will need to explore every solution space / permutation
- employing memoization via a hash table containing elements and frequencies could help
🤔What Did I Struggle With?
- im not sure how we go about selecting an element (my mind goes to a greedy approach)
- im also not sure about the base case for our dp approach
💡 Explanation of Solution
- Use a hashmap to store the frequency of each value multiplied by the value itself:
freq[x] = x * count of x
- Extract the unique keys (values in `nums`) and sort them. This ensures we handle consecutive numbers properly.
- Use dynamic programming to compute the maximum score, iterating through the sorted keys.
⌛ Complexity Analysis
Time Complexity: O(n + m log m) bound by the sorting of the keys array and the iteration of the input array
Space Complexity: O(m) for the hashmap of unique keys
💻 Implementation of Solution
class Solution {public: int deleteAndEarn(vector<int>& nums) { if(nums.empty()) return 0; // step 1: build the frequency map unordered_map<int, int> freq; for(int num : nums) { freq[num] += num; } // step 2: extract and sort the unique keys in the input array vector<int> keys; for (const auto& pair : freq) { keys.push_back(pair.first); } sort(keys.begin(), keys.end()); // step 3: dynamic programming on sorted keys int prevMax = 0; int currMax = 0; for(int i=0; i < keys.size(); i++) { int points = freq[keys[i]]; if(i > 0 && keys[i] == keys[i-1] + 1) { // if keys[i] is consecutive to keys[i-1], we can't take both int temp = currMax; currMax = max(currMax, prevMax + points); prevMax = temp; } else { // if keys[i] is not consecutive, we can safely take the points int temp = currMax; currMax = currMax + points; prevMax = temp; } } return currMax; }};