MediumNo. 0740
Delete and Earn — LeetCode 740 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Array, Hash Table, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The 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.
Example
- Input
- nums = [3,4,2]
- Output
- 6
- Explanation
- You can perform the following operations:
Python solution
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
mx = -inf
for num in nums:
mx = max(mx, num)
total = [0] * (mx + 1)
for num in nums:
total[num] += num
first = total[0]
second = max(total[0], total[1])
for i in range(2, mx + 1):
cur = max(first + total[i], second)
first = second
second = cur
return secondComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 740. Delete and Earn is filed here because LeetCode tags it Dynamic Programming, which is the vocabulary this hub collects.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0139 | Word Break | Medium |
| 0140 | Word Break II | Hard |
| 0691 | Stickers to Spell Word | Hard |
| 0792 | Number of Matching Subsequences | Medium |
| 0823 | Binary Trees With Factors | Medium |
| 0873 | Length of Longest Fibonacci Subsequence | Medium |
Frequently asked questions
- How hard is LeetCode 740. Delete and Earn?
LeetCode 740. Delete and Earn is rated Medium on LeetCode.
- What is the time complexity of LeetCode 740. Delete and Earn?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 740. Delete and Earn?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 740. Delete and Earn cover?
LeetCode 740. Delete and Earn is tagged Array, Hash Table and Dynamic Programming on LeetCode.