Delete And Earn Leetcode Problem 740 [Python Solution]

It’s time to maximize, Delete And Earn LeetCode problem needs we return the maximum number of points you can earn by applying an operation some number of times.

This problem falls under the category of 1-D Dynamic Programming and is categorized as a medium difficulty problem.

We’ll walk you through the problem, provide an efficient Python solution, explain the reasoning behind our approach, and cover the time and space complexity.

Problem Name: Delete And Earn
Difficulty: Medium
Category: 1-D Dynamic Programming
Companies: Amazon

Problem Overview

Problem Statement

You are given an integer array nums.

Your goal is to maximize the number of points you can earn by performing the following operation any number of times:

Pick any nums[i] and delete it to earn nums[i] points.
Afterward, 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 <= 20,000
1 <= nums[i] <= 10,000

Now, let’s dive into the problem and discuss the approach to solving it.

Understanding the Constraints

Before we delve into the solution, it’s crucial to understand the constraints provided with this problem.

These constraints help us determine the efficiency of our solution and make sure it works well for all possible inputs.

The length of the nums array can be as large as 20,000, which means our solution needs to be efficient to handle such a large input size.
The values in the nums array can range from 1 to 10,000, which gives us insight into the possible input range.

Now, let’s explore the solution to the Delete And Earn problem.

Delete And Earn LeetCode Problem Solution

Approach: Dynamic Programming

We can solve this problem efficiently using dynamic programming.

The idea is to transform the input array and then use dynamic programming to find the maximum points we can earn.

1. Eliminate Duplicates and Count Occurrences

To simplify the problem, we start by eliminating duplicate values in the input array and counting the occurrences of each value.

This is done to ensure that we don’t lose the number of points associated with each value.

We will keep this information in a hash map.

2. Sort the Array

Next, we sort the transformed array.

Sorting is essential because it helps us determine which values are adjacent to each other in terms of their numeric values.

This will be crucial in deciding which values we can include in our calculations.

Now, let’s move on to the dynamic programming part of the solution.

Dynamic Programming (DP) Approach

We’ll use a one-dimensional dynamic programming approach to find the maximum points we can earn.

We’ll create two variables, earn1 and earn2, to represent the maximum points earned from the current and previous values, respectively.

Initialize earn1 and earn2 to 0.
Iterate through the sorted array of values.
For each value, calculate the points we can earn by deleting it and all its adjacent values that are one less or one more than the current value.
Update the earn1 and earn2 variables based on the calculated points.
Continue this process for all values in the array.

Python Code Solution

View on GitHub ➹

class Solution:
    def deleteAndEarn(self, nums):
        if not nums:
            return 0

        # Eliminate duplicates and count occurrences
        count = collections.Counter(nums)
        max_num = max(count.keys())  # Determine the maximum value in the 'count' dictionary
        
        # Create a list to store the earned points for each value
        dp = [0] * (max_num + 1)

        # Initialize dp[1] and dp[2]
        dp[1] = count[1] * 1
        if max_num > 1:
            dp[2] = max(count[1] * 1, count[2] * 2)

        for i in range(3, max_num + 1):
            # Calculate points for the current value
            points = i * count[i]

            # Update dp[i] using the previous values in dp
            dp[i] = max(dp[i - 2] + points, dp[i - 1])

        # Return the maximum points
        return dp[max_num]

This Python code provides an efficient solution to the Delete And Earn problem using dynamic programming.

We eliminate duplicates, sort the array, and then compute the maximum points we can earn.

We consider adjacent values and update earn1 and earn2 accordingly to find the optimal result.

Time and Space Complexity

Let’s analyze the time and space complexity of our solution.

Time Complexity:

The time complexity is dominated by the sorting step, which has a time complexity of O(n log n) due to the use of Python’s built-in sorted function.

The dynamic programming part has a linear time complexity of O(n), where n is the number of unique values in the input array.

Overall, the time complexity is O(n log n).

Space Complexity:

The space complexity is determined by the storage of unique values and their counts, which is represented by the values array and the count hash map.

The space complexity is O(n), where n is the number of unique values in the input array.

Reasoning Behind Our Approach

The key insight in this problem is to recognize that it can be transformed into a dynamic programming problem similar to the “House Robber” problem.

By eliminating duplicates, counting occurrences, and sorting the values, we simplify the problem.

We use dynamic programming to compute the maximum points we can earn while considering adjacent values.

Our approach efficiently handles large input sizes and provides an optimal solution for maximizing points in this scenario.

Conclusion

In this blog post, we tackled the Delete And Earn LeetCode problem, which falls under the category of 1-D Dynamic Programming.

We provided a detailed explanation of the problem, an efficient Python solution, and a breakdown of the time and space complexity.

If you found this post helpful and informative, please like and engage to support our our platform.

If you have any questions, suggestions, or comments, feel free to share them.

Solving algorithmic problems like this one can be a great way to improve your programming skills.

Happy coding!

Question Link: Delete And Earn LeetCode Problem