Is Delete and Earn easy or hard?

Delete and Earn is rated Medium on LeetCode because the main challenge is recognizing the hidden transformation to the House Robber dynamic programming problem. Once that pattern is identified, the implementation becomes a straightforward linear DP.

How to solve Delete and Earn in O(n)?

Aggregate the total score contributed by each number into a points array where points[i] = i multiplied by its frequency. Then apply the House Robber recurrence: dp[i] = max(dp[i-1], dp[i-2] + points[i]). This avoids sorting and processes the values sequentially.

What is the best approach for Delete and Earn?

The best approach converts the problem into the House Robber dynamic programming pattern. First aggregate total points for each value, then run DP where choosing value i prevents choosing i-1 and i+1. Using a points array allows a linear scan and runs in O(n + maxVal) time with O(maxVal) space.

Is Delete and Earn asked at Google/Amazon/Meta?

Delete and Earn appears frequently in technical interview preparation lists and has been reported in interviews at companies like Amazon and Meta. The problem tests recognition of dynamic programming patterns, particularly transforming problems into the House Robber recurrence.

What data structure is used in Delete and Earn?

Common implementations use either a hash map or an array to aggregate the total points for each value. After aggregation, dynamic programming is applied across the values to decide whether to include or skip each number.

What is the time complexity of Delete and Earn?

The optimal solution runs in O(n + maxVal) time using a points array and dynamic programming. Building the points array takes O(n), and the DP scan across values up to the maximum number takes O(maxVal). A map-based version with sorted keys runs in O(n log n).

Delete and Earn Python or Java solution approach?

Both Python and Java implementations typically follow the same two steps: accumulate points for each value and then apply House Robber style DP. Python often uses a list for the points array, while Java implementations frequently use either arrays or a HashMap followed by sorted traversal.

Description Hints 1 Solution Video 19:09

740. Delete and Earn

Medium57.7% acceptance12 companies

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.

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.

Constraints:

1 <= nums.length <= 2 * 10⁴
1 <= nums[i] <= 10⁴

Asked at 12 companies

Morgan Stanley Akuna Capital Accenture Salesforce Meesho Tiktok

Infosys

Google Amazon Microsoft Meta Bloomberg

Topics

Hints open one at a time

Hint 1

If you take a number, you might as well take them all. Keep track of what the value is of the subset of the input with maximum M when you either take or don't take M.

19:09

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution