loading

740. Delete and Earn — Step-by-Step Visualization

mediumLeetCode #740ArrayHash TableDynamic Programming

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]`, earn `nums[i]` points, and **delete every** element equal to `nums[i] - 1` and `nums[i] + 1`. Return the **maximum** number of points you can earn. **Example 1:** Input: `nums = [3,4,2]` Output: `6` Explanation: Delete 4 (earn 4), then delete 3 (earn 2). Total = 6. **Example 2:** Input: `nums = [2,2,3,3,3,4]` Output: `9` Explanation: Delete 3 three times (earn 9). 2 and 4 are deleted.

Algorithm Pattern

House Robber on a value array

Key Idea

Build a `points` array where `points[v]` = v × (count of v in nums). Then run House Robber on `points` — taking value v means you can't take v-1 or v+1, just like robbing adjacent houses.

Step-by-Step Approach

  1. Find max value in nums. Create points[0..max] = 0.
  2. For each num: points[num] += num.
  3. Run House Robber on points: prev2, prev1 = 0, 0.
  4. For each p in points: prev2, prev1 = prev1, max(prev1, prev2 + p).
  5. Return prev1.

Common Gotchas

  • You don't need to sort nums. The points array is already indexed by value.
  • The House Robber reduction works because choosing value v forbids v±1, exactly like non-adjacent houses.

Related Problems

← All problems