# Delete and Earn
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/delete-and-earn)
Canonical: https://scaleengineer.com/dsa/problems/delete-and-earn
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Hash Table
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Citadel](https://scaleengineer.com/companies/citadel), [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## Problem
You are given an integer array `nums`. You want to maximize the number of points you get by performing the following operation any number of times:

* Pick any `nums[i]` and delete it to earn `nums[i]` points. Afterwards, you must delete **every** element equal to `nums[i] - 1` and **every** element equal to `nums[i] + 1`.

Return _the **maximum number of points** you can earn by applying the above operation some number of times_.

**Example 1:**

**Input:** nums = [3,4,2]
**Output:** 6
**Explanation:** You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.

**Example 2:**

**Input:** nums = [2,2,3,3,3,4]
**Output:** 9
**Explanation:** You can perform the following operations:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
- Delete a 3 again to earn 3 points. nums = [3].
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.

**Constraints:**

* `1 <= nums.length <= 2 * 104`
* `1 <= nums[i] <= 104`

# Approaches
## Top-Down Dynamic Programming with Memoization
This approach transforms the problem into a variation of the classic "House Robber" problem. We first process the input array to calculate the total points obtainable for each number. Then, we use a recursive function with memoization to decide whether to "rob" (take the points for) each number `i` or not. If we take `i`, we cannot take `i-1`.
**Time:** `O(N + M)`, where `N` is the length of `nums` and `M` is the maximum value in `nums`. `O(N)` to build the `points` array and `O(M)` for the recursive calls, as each state `rob(i)` is computed only once. · **Space:** `O(M)`. We need `O(M)` space for the `points` array, `O(M)` for the `memo` array, and `O(M)` for the recursion stack in the worst case, where `M` is the maximum value in `nums`.
**Pros:** Conceptually straightforward, directly translating the recurrence relation into code.; Guaranteed to find the optimal solution.
**Cons:** Can lead to a `StackOverflowError` for very large `M` if the recursion depth limit is exceeded (not an issue with the given constraints).; Slightly higher overhead compared to the iterative bottom-up approach due to function calls.
### Explanation
First, we need to aggregate the points for each number. Since taking a number `x` means we should take all occurrences of `x`, the total points for `x` is `x * count(x)`. We can use an array, let's call it `points`, to store these aggregated values. The size of this array will be determined by the maximum value in the `nums` array.
Let `maxNum` be the maximum value in `nums`. We create `points` array of size `maxNum + 1`. We iterate through `nums`, and for each `num`, we update `points[num] += num`.
Now, the problem is equivalent to: given the `points` array, find the maximum sum of elements such that no two chosen elements are adjacent. This is the House Robber problem.
We define a recursive function, say `maxPoints(i)`, which computes the maximum points we can earn from numbers up to `i`.
For each number `i`, we have two choices:
1.  **Take `i`**: We earn `points[i]`. Since we take `i`, we cannot take `i-1`. The maximum points we could have earned before that is `maxPoints(i-2)`. So, total points = `points[i] + maxPoints(i-2)`.
2.  **Skip `i`**: We earn 0 points from `i`. The maximum points we can earn is whatever we could get from numbers up to `i-1`, which is `maxPoints(i-1)`.
The recurrence relation is `maxPoints(i) = max(points[i] + maxPoints(i-2), maxPoints(i-1))`.
To avoid recomputing the same subproblems, we use a memoization table (an array `memo`) to store the results of `maxPoints(i)`.
The final answer is `maxPoints(maxNum)`.
```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    private int[] memo;
    private int[] points;

    public int deleteAndEarn(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int maxNum = 0;
        for (int num : nums) {
            maxNum = Math.max(maxNum, num);
        }

        points = new int[maxNum + 1];
        for (int num : nums) {
            points[num] += num;
        }

        memo = new int[maxNum + 1];
        for (int i = 0; i <= maxNum; i++) {
            memo[i] = -1;
        }

        return rob(maxNum);
    }

    private int rob(int i) {
        if (i < 0) {
            return 0;
        }
        if (i == 0) {
            return points[0];
        }
        if (memo[i] != -1) {
            return memo[i];
        }

        int take = points[i] + rob(i - 2);
        int skip = rob(i - 1);

        memo[i] = Math.max(take, skip);
        return memo[i];
    }
}
```
### Algorithm
- Find the maximum number `maxNum` in the input array `nums`.
- Create an array `points` of size `maxNum + 1` to store the total points for each number.
- Iterate through `nums` and populate the `points` array: `points[num] += num`.
- Create a memoization array `memo` of the same size, initialized to an indicator value (e.g., -1).
- Implement a recursive function `rob(i)` that calculates the maximum points up to number `i`.
- In `rob(i)`:
    - Handle base cases: if `i < 0`, return 0.
    - If `memo[i]` is already computed, return it.
    - Otherwise, compute `max(points[i] + rob(i-2), rob(i-1))`, store it in `memo[i]`, and return it.
- The final result is the value of `rob(maxNum)`.

## Bottom-Up Dynamic Programming
This approach is an iterative version of the top-down DP. Instead of using recursion, we build a DP table from the bottom up. We calculate the maximum points for each number `i` based on the already computed values for `i-1` and `i-2`. This avoids recursion and is generally more efficient in practice.
**Time:** `O(N + M)`, where `N` is the length of `nums` and `M` is the maximum value. `O(N)` for building `points` and `O(M)` for the DP loop. · **Space:** `O(M)`. We need `O(M)` for the `points` array and `O(M)` for the `dp` array, where `M` is the maximum value in `nums`.
**Pros:** Avoids recursion, eliminating the risk of stack overflow and reducing function call overhead.; Typically faster than the memoized recursion approach.; The logic is clear and easy to follow.
**Cons:** Uses `O(M)` extra space for the DP table, which can be optimized.
### Explanation
The preprocessing step is the same: we create a `points` array that aggregates the total points for each number. Let `maxNum` be the maximum value in `nums`.
We create a DP array, `dp`, of size `maxNum + 1`. `dp[i]` will store the maximum points that can be earned by considering numbers from 0 to `i`.
We initialize the base cases for the DP table:
- `dp[0] = points[0]` (which is 0 since numbers are positive).
- `dp[1] = max(points[0], points[1])`. Since `points[0]` is 0, this simplifies to `dp[1] = points[1]`.
We then iterate from `i = 2` up to `maxNum`. In each iteration, we apply the same recurrence relation as in the top-down approach:
- `dp[i] = max(dp[i-1], dp[i-2] + points[i])`
- `dp[i-1]` represents the case where we *skip* number `i`.
- `dp[i-2] + points[i]` represents the case where we *take* number `i`.
After the loop completes, `dp[maxNum]` will hold the maximum points that can be earned from all the numbers, which is our final answer.
```java
class Solution {
    public int deleteAndEarn(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int maxNum = 0;
        for (int num : nums) {
            maxNum = Math.max(maxNum, num);
        }

        int[] points = new int[maxNum + 1];
        for (int num : nums) {
            points[num] += num;
        }

        if (maxNum == 0) return 0;
        if (maxNum == 1) return points[1];

        int[] dp = new int[maxNum + 1];
        dp[0] = 0;
        dp[1] = points[1];

        for (int i = 2; i <= maxNum; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + points[i]);
        }

        return dp[maxNum];
    }
}
```
### Algorithm
- Find the maximum number `maxNum` in `nums`.
- Create and populate the `points` array of size `maxNum + 1` where `points[i]` is the sum of all numbers equal to `i`.
- Create a `dp` array of size `maxNum + 1`.
- Initialize the base cases: `dp[0] = 0` and `dp[1] = points[1]`.
- Iterate from `i = 2` to `maxNum`:
    - Calculate `dp[i]` using the formula: `dp[i] = max(dp[i-1], dp[i-2] + points[i])`.
- The result is `dp[maxNum]`.

## Space-Optimized Bottom-Up Dynamic Programming
This is the most efficient approach. It builds upon the bottom-up DP but recognizes that to compute `dp[i]`, we only need the results for `dp[i-1]` and `dp[i-2]`. Therefore, we can get rid of the `dp` array and use just two variables to keep track of the previous two maximums, reducing the space complexity for the DP calculation to `O(1)`.
**Time:** `O(N + M)`, where `N` is the length of `nums` and `M` is the maximum value. The complexity is identical to the previous DP approaches. · **Space:** `O(M)`. Although the DP calculation itself is `O(1)`, we still need the `points` array of size `O(M)`, where `M` is the maximum value in `nums`. This is the most space-efficient solution.
**Pros:** Most space-efficient solution.; Retains the time efficiency of the standard bottom-up DP approach.; Simple to implement.
**Cons:** The logic with `prev` and `prev2` might be slightly less intuitive at first glance compared to using a full DP array.
### Explanation
The preprocessing step of creating the `points` array remains the same.
Instead of a full `dp` array, we use two integer variables:
- `prev`: to store the maximum points up to `i-1` (equivalent to `dp[i-1]`)
- `prev2`: to store the maximum points up to `i-2` (equivalent to `dp[i-2]`)
We initialize these variables based on the base cases:
- `prev2 = 0` (representing the max points before considering any number, or `dp[-1]`)
- `prev = points[1]` (representing `dp[1]`, as `dp[0]` is 0).
We then iterate from `i = 2` up to `maxNum`. In each iteration:
- We calculate the `current` max points for number `i`: `current = max(prev, prev2 + points[i])`.
- We then update our variables for the next iteration: `prev2` becomes the old `prev`, and `prev` becomes the `current` value we just calculated.
After the loop, `prev` will hold the final answer, which is the maximum points earnable up to `maxNum`.
```java
class Solution {
    public int deleteAndEarn(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int maxNum = 0;
        for (int num : nums) {
            maxNum = Math.max(maxNum, num);
        }

        int[] points = new int[maxNum + 1];
        for (int num : nums) {
            points[num] += num;
        }

        if (maxNum == 0) return 0;

        int prev2 = 0; // Corresponds to dp[i-2]
        int prev = points[1]; // Corresponds to dp[i-1]

        for (int i = 2; i <= maxNum; i++) {
            int current = Math.max(prev, prev2 + points[i]);
            prev2 = prev;
            prev = current;
        }

        return prev;
    }
}
```
### Algorithm
- Find the maximum number `maxNum` in `nums`.
- Create and populate the `points` array of size `maxNum + 1`.
- Initialize two variables: `prev2 = 0` and `prev = points[1]`.
- Iterate from `i = 2` to `maxNum`:
    - Calculate `current = max(prev, prev2 + points[i])`.
    - Update `prev2 = prev`.
    - Update `prev = current`.
- After the loop, `prev` contains the maximum possible points. Return `prev`.

# Solutions
### Java

```java
select [ i ] = nonSelect [ i - 1 ] + sums [ i ]; nonSelect [ i ] = Math . max ( select [ i - 1 ], nonSelect [ i - 1 ]);
```

### CPP

```cpp
class Solution {
public:
  int deleteAndEarn(vector<int> &nums) {
    vector<int> vals(10010);
    for (int &num : nums) {
      vals[num] += num;
    }
    return rob(vals);
  }
  int rob(vector<int> &nums) {
    int a = 0, b = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
      int c = max(nums[i] + a, b);
      a = b;
      b = c;
    }
    return b;
  }
};

```

### Python

```python
class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int: mx = - inf for num in nums: mx = max(mx, num) total = [0] * (mx + 1) for num in nums: total[num] += num first = total[0] second = max(total[0], total[1]) for i in range(2, mx + 1): cur = max(first + total[i], second) first = second second = cur return second

```