How do you solve Delete and Earn on LeetCode?

Delete and Earn (LeetCode #740) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n + k), where k is the maximum number in nums. time complexity and O(k) space complexity. Key insight: Taking all instances of a number is optimal when choosing that number.

What is the brute force solution for Delete and Earn?

The brute force approach for Delete and Earn is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves exploring all possible combinations of deletions, calculating the points earned for each combination. This is simple but inefficient, as it checks every possible way to delete numbers. The optimal Optimal Solution approach improves this to O(n + k), where k is the maximum number in nums..

What algorithm or data structure is used to solve Delete and Earn?

Delete and Earn uses the following concepts: Array, Hash Table, Dynamic Programming. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Delete and Earn?

Clearly explain your thought process and how you arrived at the solution. Discuss edge cases, such as when the input array is empty or has only one element. Practice explaining dynamic programming concepts, as they often come up in interviews.

What are common mistakes when solving Delete and Earn?

Not considering the frequency of numbers. Confusing the problem with simpler variations that don't require adjacent deletions.

#740

Delete and Earn

Medium

ArrayHash TableDynamic ProgrammingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n + k), where k is the maximum number in nums.
Space	O(1)	O(k)

💡

Intuition

Time O(n + k), where k is the maximum number in nums.Space O(k)

Instead of exploring all subsets, we can use dynamic programming to keep track of the maximum points we can earn by either taking or skipping each number. This reduces the problem to a linear scan of the numbers.

⚙️

Algorithm

3 steps

1Step 1: Count the frequency of each number in the input array.
2Step 2: Create a points array where points[i] = i * frequency of i.
3Step 3: Use dynamic programming to calculate the maximum points by deciding whether to take or skip each number based on the previous calculations.

solution.py12 lines

1def delete_and_earn(nums):
2    if not nums:
3        return 0
4    max_num = max(nums)
5    points = [0] * (max_num + 1)
6    for num in nums:
7        points[num] += num
8    earn = [0] * (max_num + 1)
9    earn[1] = points[1]
10    for i in range(2, max_num + 1):
11        earn[i] = max(earn[i - 1], earn[i - 2] + points[i])
12    return earn[max_num]

ℹ

Complexity note: The time complexity is linear because we only traverse the nums array and the points array, while the space complexity is determined by the maximum number in the input array.

1Taking all instances of a number is optimal when choosing that number.
2Dynamic programming helps in making optimal choices based on previous states.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.