740. Delete and Earn LeetCode Solution

In this guide, you will get 740. Delete and Earn LeetCode Solution with the best time and space complexity. The solution to Delete and Earn problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Delete and Earn solution in C++
Delete and Earn solution in Java
Delete and Earn solution in Python
Additional Resources

740. Delete and Earn LeetCode Solution image

Problem Statement of Delete and Earn

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 * 104
1 <= nums[i] <= 104

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(10001) = O(1)

740. Delete and Earn LeetCode Solution in C++

class Solution {
 public:
  int deleteAndEarn(vector<int>& nums) {
    // Reduce to 198. House Robber
    vector<int> bucket(10001);

    for (const int num : nums)
      bucket[num] += num;

    int prev1 = 0;
    int prev2 = 0;

    for (const int num : bucket) {
      const int dp = max(prev1, prev2 + num);
      prev2 = prev1;
      prev1 = dp;
    }

    return prev1;
  }
};
/* code provided by PROGIEZ */

740. Delete and Earn LeetCode Solution in Java

class Solution {
  public int deleteAndEarn(int[] nums) {
    // Reduce to 198. House Robber
    int[] bucket = new int[10001];

    for (final int num : nums)
      bucket[num] += num;

    int prev1 = 0;
    int prev2 = 0;

    for (final int num : bucket) {
      final int dp = Math.max(prev1, prev2 + num);
      prev2 = prev1;
      prev1 = dp;
    }

    return prev1;
  }
}
// code provided by PROGIEZ