740. Delete and Earn

LeetCode 740: Delete and Earn Solution & Explanation

Problem Overview

TL;DR: Transform the input array into a frequency-sum array where indices represent numbers and values represent total points, then apply the "House Robber" dynamic programming logic to maximize the sum of non-adjacent elements.

The Delete and Earn problem asks us to maximize points gained from an integer array nums. The core mechanic is that if we pick a number x to earn x points, we must delete all instances of x-1 and x+1 from the array. This creates a constraint where choosing a value prevents us from choosing its immediate numerical neighbors. This problem, LeetCode 740, is a classic example of reducing a complex selection problem into a standard sequence optimization problem.

Brute Force Approach for Delete and Earn

The naive approach attempts to simulate the game process directly. We can use recursion to explore every possible decision at every step. For each unique number present in the remaining array, we branch into two paths:

1. Delete and Earn: Take the current number x, add x * count(x) to the score, remove x, x-1, and x-1, and recurse on the remaining set.
2. Skip: Ignore x for now (though in a pure simulation, "skipping" is implicit by choosing a different number first).

A more structured brute force would look like this:

Function MaxPoints(available_numbers):
    If available_numbers is empty: return 0
    
    max_score = 0
    For each unique number x in available_numbers:
        current_gain = x * count(x)
        remaining = available_numbers without x, x-1, x+1
        max_score = max(max_score, current_gain + MaxPoints(remaining))
    
    Return max_score

Complexity Analysis

The time complexity is roughly O(2^N) or worse, depending on the implementation. The branching factor is high because we can potentially start with any unique number.

• Why it fails: The constraints state nums.length up to $2 \times 10^4$. An exponential solution will immediately hit a Time Limit Exceeded (TLE) error. Furthermore, this approach repeatedly solves the same subproblems (e.g., the optimal way to clear a subset of numbers is calculated multiple times).

Algorithm Strategy: DP - 1D Array (Fibonacci Style)

1. Data Preparation:

   • Find the maximum value inside nums to determine the range of our DP array (let's call this maxVal).
   • Create an array sums of size maxVal + 1.
   • Iterate through nums and populate sums. For every num in nums, add num to sums[num]. Now, sums[i] represents the total points earned if we choose to delete the number i.

2. State Definition:

   • Let dp[i] represent the maximum points achievable considering only numbers from $0$ to $i$.

3. Recurrence Relation:

   • To calculate dp[i], we compare:
     • Skip i: Value is dp[i-1].
     • Take i: Value is sums[i] + dp[i-2].
   • Formula: dp[i] = max(dp[i-1], dp[i-2] + sums[i]).

4. Base Cases:

   • dp[0] = sums[0] (Usually 0, as input constraints say nums[i] >= 1).
   • dp[1] = max(sums[0], sums[1]) (or just sums[1] if 0 is excluded).

5. Space Optimization:

   • Notice that to calculate the current state, we only need the previous two states. We don't need the full dp array. We can maintain two variables, twoBack (representing dp[i-2]) and oneBack (representing dp[i-1]), updating them as we iterate.

Execution Flow

Consider nums = [2, 2, 3, 3, 3, 4].

1. Preprocessing:

   • Max value is 4.
   • sums array (indices 0 to 4): [0, 0, 4, 9, 4].
     • sums[2] = 2 + 2 = 4
     • sums[3] = 3 + 3 + 3 = 9
     • sums[4] = 4

2. Initialization:

   • twoBack (dp[0]) = 0
   • oneBack (dp[1]) = 0

3. Iteration:

   • i = 2:
     • Option A (Skip 2): oneBack = 0.
     • Option B (Take 2): sums[2] + twoBack = 4 + 0 = 4.
     • Max is 4.
     • Update: twoBack = 0, oneBack = 4.
   • i = 3:
     • Option A (Skip 3): oneBack = 4.
     • Option B (Take 3): sums[3] + twoBack = 9 + 0 = 9.
     • Max is 9.
     • Update: twoBack = 4, oneBack = 9.
   • i = 4:
     • Option A (Skip 4): oneBack = 9.
     • Option B (Take 4): sums[4] + twoBack = 4 + 4 = 8.
     • Max is 9.
     • Update: twoBack = 9, oneBack = 9.

4. Result: Return oneBack, which is 9.

Proof of Correctness

The correctness relies on the Optimal Substructure property. For any number i, the optimal solution for the range [0...i] must be derived from the optimal solutions of its sub-problems ([0...i-1] and [0...i-2]).

Since taking number i strictly invalidates i-1 but has no effect on i-2, these two choices (take i or skip i) cover the entire solution space for the added element. By induction, if the base cases are correct (which they are trivially), and the transition logic covers all valid moves while maximizing the local decision, the final result at dp[maxVal] will be the global maximum.

Pattern Reuse Notes

The DP - 1D Array (Fibonacci Style) pattern is highly versatile. Understanding the "skip vs. take" logic allows you to solve several popular interview questions:

• LeetCode 70: Climbing Stairs: The foundational problem. dp[i] = dp[i-1] + dp[i-2].
• LeetCode 198: House Robber: Identical logic to Delete and Earn, but the array is already "linearized" (neighbors are indices).
• LeetCode 213: House Robber II: Same logic, but on a circular array.
• LeetCode 91: Decode Ways: Decisions depend on the validity of taking 1 digit (previous state) or 2 digits (state before previous).

Reference Implementation

C++ Solution for LeetCode 740

1#include <vector>
2#include <algorithm>
3#include <map>
4
5using namespace std;
6
7class Solution {
8public:
9    int deleteAndEarn(vector<int>& nums) {
10        int maxVal = 0;
11        for (int num : nums) {
12            maxVal = max(maxVal, num);
13        }
14
15        // sums[i] stores the total points gained by taking all instances of number i
16        vector<int> sums(maxVal + 1, 0);
17        for (int num : nums) {
18            sums[num] += num;
19        }
20
21        // Standard Fibonacci-style DP variables
22        int twoBack = 0; // Represents dp[i-2]
23        int oneBack = sums[0]; // Represents dp[i-1] (conceptually dp[0])
24
25        // Iterate from 1 to maxVal
26        // Note: For i=1, the logic is max(sums[1] + twoBack, oneBack)
27        // If we treat sums[0] as index 0, loop starts at 1
28        for (int i = 1; i <= maxVal; ++i) {
29            int current = max(oneBack, twoBack + sums[i]);
30            twoBack = oneBack;
31            oneBack = current;
32        }
33
34        return oneBack;
35    }
36};

Java Solution for LeetCode 740

1class Solution {
2    public int deleteAndEarn(int[] nums) {
3        int maxVal = 0;
4        for (int num : nums) {
5            maxVal = Math.max(maxVal, num);
6        }
7
8        // sums[i] will store i * count(i)
9        int[] sums = new int[maxVal + 1];
10        for (int num : nums) {
11            sums[num] += num;
12        }
13
14        // DP Initialization
15        // twoBack represents the max points ending at i-2
16        // oneBack represents the max points ending at i-1
17        int twoBack = 0;
18        int oneBack = sums[0];
19
20        for (int i = 1; i <= maxVal; i++) {
21            int take = sums[i] + twoBack;
22            int skip = oneBack;
23            
24            int current = Math.max(take, skip);
25            
26            twoBack = oneBack;
27            oneBack = current;
28        }
29
30        return oneBack;
31    }
32}

Python Solution for LeetCode 740

1class Solution:
2    def deleteAndEarn(self, nums: List[int]) -> int:
3        if not nums:
4            return 0
5            
6        max_val = max(nums)
7        sums = [0] * (max_val + 1)
8        
9        # Precompute total points for each number
10        for num in nums:
11            sums[num] += num
12            
13        two_back = 0
14        one_back = sums[0]
15        
16        for i in range(1, max_val + 1):
17            # Recurrence: max(skip current, take current + value from i-2)
18            current = max(one_back, two_back + sums[i])
19            two_back = one_back
20            one_back = current
21            
22        return one_back