Skip to main content

740. Delete and Earn

medium

Pick numbers to maximize their sum, but taking value v deletes every v-1 and v+1. Reduces to House Robber on a value-indexed point array.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1. Return the maximum number of points you can earn by applying the above operation some number of times.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • 1 <= nums[i] <= 10^4

Examples

Example 1

Input
nums = [3,4,2]
Output
6

Explanation: You can perform the following operations: 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

Input
nums = [2,2,3,3,3,4]
Output
9

Explanation: You can perform the following operations: 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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Sum points by value. If you take any copy of v you take all copies (and forfeit v-1 and v+1).

Hint 2

Build points[v] = v * count(v). Now choose a subset of values with no two adjacent values v, v+1.

Hint 3

That is exactly House Robber on the points array indexed by value.

Solution approach

Reveal approach

Convert the multiset into a value-indexed point array. Let max_v = max(nums). Build points[0..max_v] where points[v] = v * count(v). Picking any copy of value v earns points[v] total and forbids v-1 and v+1. The problem reduces to: pick a subset of indices in points[] with no two adjacent, maximizing sum — exactly House Robber. Run the standard two-variable DP: prev2 = 0, prev1 = points[0]; for v in 1..max_v compute curr = max(prev1, prev2 + points[v]) and shift. Return prev1. O(N + V) where V is the max value.

Complexity

Time
O(N + V)
Space
O(V)

Related patterns

  • dynamic-programming
  • bucket
  • house-robber

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Delete and Earn and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →