Delete and Earn Solution in C++

Explore More Solutions:

Problem Description

Ah, the classic “Delete and Earn” problem! Imagine you’re at a party, and there’s a buffet table filled with delicious food. You can either eat a dish or remove it from the table, but if you eat a dish, you can’t eat the dish next to it. Sounds like a fun night, right? Well, that’s exactly what this problem is about, but instead of food, we’re dealing with numbers.

You’re given an array of integers, and for each integer, you can either “earn” its value by taking it or “delete” it and all its neighbors. The goal? Maximize your earnings! So, if you have a plate of numbers like [3, 4, 2], you can either take 3 and 2 (earning 5) or take 4 (earning 4). Tough choices, huh?

Code Solution


class Solution {
 public:
  int deleteAndEarn(vector& nums) {
    vector bucket(10001);
    for (const int num : nums)
      bucket[num] += num;

    int prev1 = 0;
    int prev2 = 0;

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

    return prev1;
  }
};

Approach Explanation

The approach here is akin to the “House Robber” problem. We create a bucket array to accumulate the total value of each number. For each number, we decide whether to “take” it (adding its value to our total) or “skip” it (keeping our previous total). This is done using dynamic programming, where we keep track of the maximum earnings we can achieve up to each number.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n + m)
Space Complexity	O(m)

Real-World Example

Let’s say you’re at a yard sale, and you see a bunch of items priced at various amounts. You can either buy an item or skip it, but if you buy a lawn chair for $50, you can’t buy the garden gnome next to it for $30. You want to maximize your spending without going broke! This is exactly what the “Delete and Earn” problem is about—making the best choices to maximize your total earnings.