740. Delete And Earn - Explanation

1. Recursion

Intuition

When you pick a number x, you earn all points from every occurrence of x, but you must delete all instances of x - 1 and x + 1. This creates a choice at each distinct value: either take it (and skip the next consecutive value) or skip it. Sorting helps group identical values together, making it easy to sum all occurrences. We recursively explore both choices at each group of identical numbers.

Algorithm

Sort the array to group identical numbers together.
Define a recursive function dfs(i) starting at index i:
- If i is out of bounds, return 0.
- Sum all occurrences of nums[i] and move i past this group.
- Compute the result of skipping this group: dfs(new_i).
- Skip any numbers equal to nums[i] + 1 (they would be deleted if we pick).
- Compute the result of picking this group: pick + dfs(after_skipping).
- Return the maximum of picking vs skipping.
Call dfs(0) and return the result.

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        nums.sort()

        def dfs(i):
            if i >= len(nums):
                return 0

            cur = nums[i]
            pick = 0
            while i < len(nums) and nums[i] == cur:
                pick += nums[i]
                i += 1

            res = dfs(i)
            while i < len(nums) and nums[i] == 1 + cur:
                i += 1

            res = max(res, pick + dfs(i))
            return res

        return dfs(0)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution has overlapping subproblems since we may revisit the same index multiple times. By precomputing the total value for each unique number (sum of all occurrences) and using memoization, we avoid redundant calculations. The problem reduces to: for each unique number, decide whether to take it (earning its total value but skipping the next consecutive number) or skip it.

Algorithm

Build a map where each unique number maps to the sum of all its occurrences.
Extract and sort the unique numbers.
Create a memo array initialized to -1.
Define dfs(i):
- If i is out of bounds, return 0.
- If memo[i] is set, return it.
- Compute the value of taking nums[i]: its total value plus dfs(i + 2) if the next number is consecutive, else dfs(i + 1).
- The result is max(take, dfs(i + 1)).
- Store in memo and return.
Return dfs(0).

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        val = defaultdict(int)
        for num in nums:
            val[num] += num
        nums = sorted(list(set(nums)))
        memo = [-1] * len(nums)

        def dfs(i):
            if i >= len(nums):
                return 0
            if memo[i] != -1:
                return memo[i]

            res = val[nums[i]]
            if i + 1 < len(nums) and nums[i] + 1 == nums[i + 1]:
                res += dfs(i + 2)
            else:
                res += dfs(i + 1)

            res = max(res, dfs(i + 1))
            memo[i] = res
            return res

        return dfs(0)

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Dynamic Programming (Bottom-Up) - I

Intuition

We can convert the top-down solution to bottom-up by processing unique numbers from right to left. At each position, we compute the maximum points achievable from that position onward. If the current and next numbers are consecutive, taking the current means skipping the next; otherwise, we can take the current and continue from the next.

Algorithm

Build a map of each unique number to the sum of all its occurrences.
Extract and sort the unique numbers.
Create a DP array of size n + 1 initialized to 0.
Iterate from the last unique number to the first:
- Compute take as the value of the current number plus dp[i + 2] if the next is consecutive, else dp[i + 1].
- Set dp[i] = max(dp[i + 1], take).
Return dp[0].

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        val = defaultdict(int)
        for num in nums:
            val[num] += num
        nums = sorted(list(set(nums)))

        dp = [0] * (len(nums) + 1)
        for i in range(len(nums) - 1, -1, -1):
            take = val[nums[i]]
            if i + 1 < len(nums) and nums[i + 1] == nums[i] + 1:
                take += dp[i + 2]
            else:
                take += dp[i + 1]
            dp[i] = max(dp[i + 1], take)

        return dp[0]

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

4. Dynamic Programming (Bottom-Up) - II

Intuition

Instead of working with unique sorted numbers, we can use an array indexed by the numbers themselves (0 to max). Each index stores the total points for that number. This transforms the problem into the classic House Robber problem: you cannot take adjacent indices. We iterate backward, and at each position, choose the maximum of skipping it or taking it plus the result two positions ahead.

Algorithm

Find the maximum value m in the array.
Create a DP array of size m + 2 initialized to 0.
For each number in the input, add it to dp[num] (accumulating total points per number).
Iterate from m - 1 down to 1:
- Set dp[i] = max(dp[i + 1], dp[i + 2] + dp[i]).
Return dp[1].

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        m = max(nums)
        dp = [0] * (m + 2)

        for num in nums:
            dp[num] += num
        for i in range(m - 1, 0, -1):
            dp[i] = max(dp[i + 1], dp[i + 2] + dp[i])

        return dp[1]

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity: $O(m)$

Where $m$ is the maximum element in the array and $n$ is the size of the array.

5. Dynamic Programming (Space Optimized)

Intuition

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.

Algorithm

Build a map of each unique number to the sum of all its occurrences.
Sort the unique numbers.
Initialize earn1 = 0 and earn2 = 0 to track the max earnings at the previous two positions.
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.
Return earn2.

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

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$