Loading problems...
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.
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:
x, add to the score, remove , , and , and recurse on the remaining set.x * count(x)xx-1x-1x 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:
textFunction 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
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.
nums.length up to . 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).The critical realization required to solve LeetCode 740 is that the order of elements in nums does not matter; only their values and frequencies matter.
x, we should take all instances of x. Taking one instance deletes x-1 and x+1 anyway, so there is no penalty for taking the remaining x's. We can pre-calculate the total value provided by each number: gain[x] = x * count(x).i holds the total points for number i), the "neighbors" x-1 and x+1 become adjacent indices in this new array.x-1 and x+1" translates to: You cannot pick two adjacent elements in the value-based array.This transformation reduces the problem exactly to the House Robber problem. We iterate through numbers from to . At each number i, we have two choices:
i: We gain points[i]. We cannot have taken i-1, so we add this to the max points found up to i-2.i: We gain nothing from i. The max points is simply whatever we achieved up to i-1.Visual Description: Imagine the numbers are houses on a street, ordered by value (). The amount of cash in house is the sum of all 's in the original array. The police are alerted if you rob two adjacent houses ( and ). The recurrence tree visualizes a decision at node branching to node (skip) and node (take).

Data Preparation:
nums to determine the range of our DP array (let's call this maxVal).sums of size maxVal + 1.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.State Definition:
dp[i] represent the maximum points achievable considering only numbers from to .Recurrence Relation:
dp[i], we compare:
i: Value is dp[i-1].i: Value is sums[i] + dp[i-2].dp[i] = max(dp[i-1], dp[i-2] + sums[i]).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).Space Optimization:
dp array. We can maintain two variables, twoBack (representing dp[i-2]) and oneBack (representing dp[i-1]), updating them as we iterate.Consider nums = [2, 2, 3, 3, 3, 4].
Preprocessing:
sums array (indices 0 to 4): [0, 0, 4, 9, 4].
sums[2] = 2 + 2 = 4sums[3] = 3 + 3 + 3 = 9sums[4] = 4Initialization:
twoBack (dp[0]) = 0oneBack (dp[1]) = 0Iteration:
oneBack = 0.sums[2] + twoBack = 4 + 0 = 4.twoBack = 0, oneBack = 4.oneBack = 4.sums[3] + twoBack = 9 + 0 = 9.twoBack = 4, oneBack = 9.oneBack = 9.sums[4] + twoBack = 4 + 4 = 8.twoBack = 9, oneBack = 9.Result: Return oneBack, which is 9.
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.
cpp#include <vector> #include <algorithm> #include <map> using namespace std; class Solution { public: int deleteAndEarn(vector<int>& nums) { int maxVal = 0; for (int num : nums) { maxVal = max(maxVal, num); } // sums[i] stores the total points gained by taking all instances of number i vector<int> sums(maxVal + 1, 0); for (int num : nums) { sums[num] += num; } // Standard Fibonacci-style DP variables int twoBack = 0; // Represents dp[i-2] int oneBack = sums[0]; // Represents dp[i-1] (conceptually dp[0]) // Iterate from 1 to maxVal // Note: For i=1, the logic is max(sums[1] + twoBack, oneBack) // If we treat sums[0] as index 0, loop starts at 1 for (int i = 1; i <= maxVal; ++i) { int current = max(oneBack, twoBack + sums[i]); twoBack = oneBack; oneBack = current; } return oneBack; } };
javaclass Solution { public int deleteAndEarn(int[] nums) { int maxVal = 0; for (int num : nums) { maxVal = Math.max(maxVal, num); } // sums[i] will store i * count(i) int[] sums = new int[maxVal + 1]; for (int num : nums) { sums[num] += num; } // DP Initialization // twoBack represents the max points ending at i-2 // oneBack represents the max points ending at i-1 int twoBack = 0; int oneBack = sums[0]; for (int i = 1; i <= maxVal; i++) { int take = sums[i] + twoBack; int skip = oneBack; int current = Math.max(take, skip); twoBack = oneBack; oneBack = current; } return oneBack; } }
pythonclass Solution: def deleteAndEarn(self, nums: List[int]) -> int: if not nums: return 0 max_val = max(nums) sums = [0] * (max_val + 1) # Precompute total points for each number for num in nums: sums[num] += num two_back = 0 one_back = sums[0] for i in range(1, max_val + 1): # Recurrence: max(skip current, take current + value from i-2) current = max(one_back, two_back + sums[i]) two_back = one_back one_back = current return one_back
Let be the length of nums and be the maximum value in nums (up to 10,000).
Time Complexity: O(N + M)
nums once to build the sums array: .The DP - 1D Array (Fibonacci Style) pattern is highly versatile. Understanding the "skip vs. take" logic allows you to solve several popular interview questions:
dp[i] = dp[i-1] + dp[i-2].Why does the naive recursion TLE?
Why can't we just use a greedy approach?
num * count).Space Complexity: O(M)
sums (frequency points).sums array dominates.[4, 5, 4]. Taking 5 deletes both 4s. ).Why do we need a frequency/sum array?
nums and trying to DP directly on the sorted array without handling gaps.nums is [2, 5], they are adjacent in the array but not numerically adjacent. The constraint only applies to x and x+1. A direct array DP complicates checking for numerical adjacency.