Delete and Earn Solution in Java

Problem Description

Ah, the classic dilemma of “Delete and Earn.” Imagine you’re at a party, and there’s a buffet table filled with delicious food. But wait! You can only eat the food if you promise to throw away all the food items that are one step away from your chosen dish. Sounds ridiculous, right? Well, that’s exactly what this problem is about!

In the world of LeetCode, you’re given an array of integers, and your goal is to maximize your earnings by “deleting” numbers. When you delete a number, you earn points equal to that number, but you also have to delete all instances of that number and its immediate neighbors (i.e., the number itself minus one and plus one). So, if you choose to “eat” a 3, you must also throw away all 2s and 4s.

Code Solution

Copy Code

class Solution {
  public int deleteAndEarn(int[] nums) {
    // Reduce to 198. House Robber
    int[] bucket = new int[10001];

    for (final int num : nums)
      bucket[num] += num;

    int prev1 = 0;
    int prev2 = 0;

    for (final int num : bucket) {
      final int dp = Math.max(prev1, prev2 + num);
      prev2 = prev1;
      prev1 = dp;
    }

    return prev1;
  }
}

Approach

The approach taken in the code is quite clever. It transforms the problem into a variation of the “House Robber” problem. Instead of robbing houses, you’re “earning” from numbers. The code creates a “bucket” array to accumulate the total points for each number. Then, it uses dynamic programming to decide whether to “earn” from the current number or skip it, ensuring that you never earn from adjacent numbers.

Time and Space Complexity

Time Complexity: O(n + m), where n is the number of elements in the input array and m is the maximum number in the array (in this case, 10000).

Space Complexity: O(m), due to the bucket array used to store the total points for each number.

Real-World Example

Imagine you’re at a yard sale, and you see a collection of vintage toys. You can buy a toy for $5, but if you buy it, you can’t buy the toys that are priced at $4 and $6. So, you have to strategize your purchases to maximize your collection without breaking the bank. This is essentially what the “Delete and Earn” problem is asking you to do with numbers!