Delete and Earn

Easy

💭 Introduction

You’re given an array of integers nums. You can perform the following operation any number of times:

Pick a number x and earn x points.
Then all instances of x-1 and x+1 will be deleted from the array.

Your goal is to maximize the total points earned.

🧩 Problem Statement

LeetCode #740 — Delete and Earn

You are given an integer array nums. You want to maximize the number of points you get by performing operations. In one operation, you can pick any nums[i] and delete it to earn nums[i] points. After deleting it, you must delete every element equal to nums[i] - 1 and nums[i] + 1. Return the maximum number of points you can earn.

🔍 Example 1:

Input: nums = [3,4,2]
Output: 6

Explanation:

Delete 4 to earn 4 points. Consequently, 3 is also deleted. Then, delete 2 to earn 2 points. Total = 4 + 2 = 6.

🔍 Example 2:

Input: nums = [2,2,3,3,3,4]
Output: 9

Explanation:

Delete a 3 to earn 3 points. All 2’s and 4’s are deleted. Delete a 3 again to earn 3 points. Delete a 3 once more to earn 3 points. Total = 3 + 3 + 3 = 9.

🧠 Step 1: Understanding the Problem

At first glance, this problem seems complex. But let’s break it down:

When you pick a number x, you earn x points for each occurrence of x in the array.

For example, if nums = [2,2,3,3,3,4]:

If you pick 3, you earn 3 × 3 = 9 points (three 3’s)
But then all 2’s and 4’s are deleted

This is the key insight: You either take all occurrences of a number or none at all.

🔄 Step 2: Transform to House Robber

Here’s the brilliant transformation:

Count the total points for each unique number
Sort the numbers in ascending order
Now it becomes: “Can I pick adjacent numbers?”

If we pick number x, we can’t pick x-1 or x+1 — just like the House Robber problem where we can’t rob adjacent houses!

Let’s transform nums = [2,2,3,3,3,4]:

Number:  2    3    4
Points:  4    9    4  (2×2, 3×3, 4×1)

Now the question is: maximize points where you can’t pick adjacent numbers.

Sound familiar? It’s House Robber!

⚠️ Step 3: The Naive Recursive Approach

Let’s first create a frequency map and then apply recursion:

def deleteAndEarn(nums):
    from collections import Counter
    count = Counter(nums)
    max_num = max(nums)
    
    def helper(i):
        if i <= 0:
            return 0
        # Either take current number or skip it
        take = i * count[i] + helper(i - 2)
        skip = helper(i - 1)
        return max(take, skip)
    
    return helper(max_num)

This works but has exponential time complexity due to overlapping subproblems.

⏱️ Time Complexity: $O(2^n)$

🚀 Step 4: Top-Down DP (Memoization)

We can cache results to avoid recomputation:

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        from collections import Counter
        count = Counter(nums)
        max_num = max(nums)
        memo = {}
        
        def helper(i):
            if i <= 0:
                return 0
            if i in memo:
                return memo[i]
            
            # Take current number (all occurrences) or skip
            take = i * count[i] + helper(i - 2)
            skip = helper(i - 1)
            memo[i] = max(take, skip)
            
            return memo[i]
        
        return helper(max_num)

Now each subproblem is computed once.

⏱️ Time: $O(n + m)$ where n = length of nums, m = max value in nums

📦 Space: $O(m)$ for memoization

⚙️ Step 5: Bottom-Up DP (Tabulation)

We can build a table from the ground up:

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        from collections import Counter
        count = Counter(nums)
        max_num = max(nums)
        
        if max_num == 0:
            return 0
        
        # dp[i] = max points we can earn considering numbers 0 to i
        dp = [0] * (max_num + 1)
        dp[0] = 0
        dp[1] = count[1]
        
        for i in range(2, max_num + 1):
            # Either take all i's or skip
            take = i * count[i] + dp[i - 2]
            skip = dp[i - 1]
            dp[i] = max(take, skip)
        
        return dp[max_num]

✅ Clean, iterative, and avoids recursion stack overhead.

⏱️ Time: $O(n + m)$

📦 Space: $O(m)$

🧮 Step 6: Space Optimization

Notice that at each step, we only need the previous two states (dp[i-1] and dp[i-2]).

We can reduce the space to $O(1)$ by tracking just two variables:

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        from collections import Counter
        count = Counter(nums)
        max_num = max(nums)
        
        prev2, prev1 = 0, 0
        
        for i in range(max_num + 1):
            # Either take all i's or skip
            take = i * count[i] + prev2
            skip = prev1
            new_val = max(take, skip)
            
            prev2 = prev1
            prev1 = new_val
        
        return prev1

This is the optimal solution — fast, elegant, and space-efficient.

⏱️ Time Complexity: $O(n + m)$ where n = length of nums, m = max value

📦 Space Complexity: $O(n)$ for Counter (can’t avoid this)

🎯 Key Insights

Transform the problem: Convert to a frequency-based problem where you decide whether to take each unique number.
Recognize the pattern: Once transformed, it’s identical to House Robber — you can’t take adjacent values.
Optimization matters: The space-optimized solution is elegant and efficient.
Edge cases: Handle empty arrays and single elements carefully.

📊 Complexity Summary

Approach	Time	Space
Naive Recursion	$O(2^m)$	$O(m)$
Memoization	$O(n + m)$	$O(m)$
Tabulation	$O(n + m)$	$O(m)$
Space Optimized	$O(n + m)$	$O(n)$

Where n = length of nums, m = max value in nums

House Robber - The core pattern
House Robber II - Circular array variant
House Robber III - Tree structure variant