š Delete and Earn - The Discovery Journey
The Problem (Quick Glance)ā
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 earnnums[i]points. Afterwards, you must delete every element equal tonums[i] - 1and every element equal tonums[i] + 1.
Return the maximum number of points you can earn by applying the above operation some number of times.
Example 1: nums = [3,4,2]
Input: nums = [3,4,2]
Output: 6
Explanation:
- 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: nums = [2,2,3,3,3,4]
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 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 * 10^41 <= nums[i] <= 10^4
Initial Observations:
- This is a maximization problem - maximize points earned
- Taking number
iforces deletion ofi-1andi+1 - This constraint is similar to House Robber - can't take adjacent houses!
- We can take ALL occurrences of the same number
Let's start solving!
1. My First Approach: Thinking Recursivelyā
My thought process:
"When I see a maximization problem with constraints, I think: this is a decision tree problem.
At each number, I can:
- Take it (earn ALL occurrences, but lose access to adjacent values)
- Skip it (keep access to adjacent values)
This smells like recursion!"
Solution 1: Unoptimized Recursive (Brute Force)ā
class Solution {
public int deleteAndEarn(int[] nums) {
return func(0, 0, nums);
}
int func(int index, int totalVal, int[] nums) {
// Base case
// If we don't have any number left to process, then return totalVal
if (nums.length == 0) {
return totalVal;
}
if (index >= nums.length) {
return totalVal;
}
// Take it - earn ALL occurrences of this number
int currentElement = nums[index];
int earnedPoints = 0;
for (int num : nums) {
if (num == currentElement) {
earnedPoints += num;
}
}
int a = func(0, totalVal + earnedPoints, removeElement(nums, currentElement));
// Leave it
int b = func(index + 1, totalVal, nums);
return Math.max(a, b);
}
// A method for removing all the numbers that are equal to element+1 and element-1
public static int[] removeElement(int[] arr, int element) {
// Count how many elements to keep
int count = 0;
for (int num : arr) {
if (num != element + 1 && num != element - 1 && num != element) {
count++;
}
}
// Create a new array with the correct size
int[] newArr = new int[count];
int idx = 0;
for (int num : arr) {
if (num != element + 1 && num != element - 1 && num != element) {
newArr[idx++] = num;
}
}
return newArr;
}
}
Complexity Analysis:
- Time: Exponential - Creating new arrays and exploring all decisions
- Space: O(nĀ²) - Multiple array copies created
Why This Is Slow:
- Creating new arrays on every recursive call - expensive memory operations
- Recalculating the same subproblems multiple times
- No memoization - can't cache results because we're modifying the array
For nums = [2,2,3,3,3,4]:
- Pure recursion explores all possible decision trees
- Creates multiple copies of modified arrays
- This is extremely inefficient!
My realization: "Wait, I'm creating new arrays repeatedly. There must be a better way to model this problem!"
2. Optimization Round 1: Adding Memoization (Top-Down DP)ā
This section will be added soon! We'll transform this into a proper DP solution by recognizing it's actually House Robber in disguise!
The Key Insight: Instead of modifying arrays, we can:
- Count total points for each number value
- Apply House Robber logic:
dp[i] = Math.max(dp[i-1], dp[i-2] + points[i])
Solution 2: Top-Down DP with Memoizationā
// Coming soon...
3. Optimization Round 2: Going Iterative (Bottom-Up DP)ā
This section will be added soon! We'll build the solution iteratively from smallest values to largest.
The approach:
- Create a
points[]array wherepoints[i]= total points for numberi - Use dynamic programming: for each value, decide to take it or skip it
- Can't take consecutive values (like House Robber)
Solution 3: Bottom-Up DP with Tabulationā
// Coming soon...
4. Final Optimization: Space Optimization (O(1) Space)ā
This section will be added soon! Since we only need the last 2 values, we can optimize to O(1) space.
Solution 4: Space-Optimized Bottom-Upā
// Coming soon...
5. Solution Evolution Summaryā
| Approach | Time | Space | Key Insight |
|---|---|---|---|
| 1. Unoptimized Recursive | Exponential | O(nĀ²) | Establishes the problem structure |
| 2. Top-Down (Memoization) | O(n) | O(n) | Recognize House Robber pattern |
| 3. Bottom-Up (Tabulation) | O(n) | O(n) | Build solution iteratively |
| 4. Space-Optimized | O(n) | O(1) | Only need last 2 values |
6. Deep Dive: Understanding Why This Worksā
We'll explore:
- Why this is House Robber in disguise
- How to transform array problems into value-based DP
- The connection between constraints and state definition
7. Mastery & Key Takeawaysā
7.1 Current Understandingā
This problem teaches us:
- ā Look for hidden patterns - Delete and Earn is actually House Robber!
- ā Transform the problem - Don't work with indices, work with values
- ā Count occurrences - Multiple same numbers can be grouped
- ā
Adjacent constraints - Taking
iblocksi-1andi+1(like adjacent houses)
7.2 The Transformationā
The Key Insight: Instead of thinking about array indices, think about number values!
Original: [3, 4, 2]
ā
Transform to points array:
points[2] = 2 (one occurrence of 2)
points[3] = 3 (one occurrence of 3)
points[4] = 4 (one occurrence of 4)
ā
Now it's House Robber:
Can't take both points[3] and points[4] (adjacent values)
Choose: points[4] + points[2] = 6
We'll add:
- Memoized recursive solution
- Bottom-up DP solution
- Space-optimized solution
- Detailed complexity analysis
- Complete execution traces