Delete and Earn

How it works

We only need to track the maximum earnings for the previous two positions, similar to the space-optimized House Robber solution. By iterating through sorted unique numbers and maintaining two variables, we can reduce space complexity. When consecutive numbers differ by more than 1, there is no conflict, so we can add the current earnings directly.

Steps

1. Build a map of each unique number to the sum of all its occurrences.
2. Sort the unique numbers.
3. Initialize earn1 = 0 and earn2 = 0 to track the max earnings at the previous two positions.
4. Iterate through the sorted unique numbers:
   • If the current number is consecutive to the previous, we have a choice: earn2 = max(curEarn + earn1, earn2).
   • If not consecutive, we can freely take the current: earn2 = curEarn + earn2.
   • Update earn1 to the old earn2 before modifying.
5. Return earn2.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(n)

Things to watch for

Not Summing All Occurrences

When you pick a number, you earn points from every occurrence of that number in the array. A common mistake is only counting it once instead of summing all instances.

Forgetting to Skip Adjacent Values

When you earn points for a number x, you must delete all instances of x-1 and x+1. This means if you pick a value, you cannot pick the consecutive values. Missing this skip logic leads to incorrect results.

Treating Non-Consecutive Numbers as Adjacent

In the House Robber transformation, only consecutive numbers conflict. If numbers have gaps (e.g., 2 and 5), both can be taken without any penalty. Treating all numbers as adjacent loses points.

from typing import List
from collections import Counter

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        count = Counter(nums)
        nums = sorted(list(set(nums)))

        earn1, earn2 = 0, 0
        for i in range(len(nums)):
            curEarn = nums[i] * count[nums[i]]
            if i > 0 and nums[i] == nums[i - 1] + 1:
                temp = earn2
                earn2 = max(curEarn + earn1, earn2)
                earn1 = temp
            else:
                temp = earn2
                earn2 = curEarn + earn2
                earn1 = temp
        return earn2

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int num : nums) count[num] += num;
        vector<int> uniqueNums;
        for (auto& pair : count) uniqueNums.push_back(pair.first);
        sort(uniqueNums.begin(), uniqueNums.end());

        int earn1 = 0, earn2 = 0;
        for (int i = 0; i < uniqueNums.size(); i++) {
            int curEarn = count[uniqueNums[i]];
            if (i > 0 && uniqueNums[i] == uniqueNums[i - 1] + 1) {
                int temp = earn2;
                earn2 = max(curEarn + earn1, earn2);
                earn1 = temp;
            } else {
                int temp = earn2;
                earn2 = curEarn + earn2;
                earn1 = temp;
            }
        }
        return earn2;
    }
};