algoadvance

Leetcode 740. Delete and Earn

Problem Statement

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. After deleting it, you must delete every element equal to nums[i] - 1 and nums[i] + 1.

Return the maximum number of points you can earn by applying the above operation.

Example

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.
- Then, delete 2 to earn 2 points.
- 6 total points are earned.

Clarifying Questions

1. Q: Can the array nums be empty? A: No, the constraints ensure that nums has at least one element.

2. Q: What is the range of values for elements in nums? A: Each element in nums is a positive integer within the range [1, 10000].

3. Q: Can there be duplicates in nums? A: Yes, there can be duplicates in nums.

Strategy

1. Frequency Count: Use a map to count the frequency of each number in the array.
2. Transformed Array: Use the frequencies to transform the problem into a simpler one, resembling the “House Robber Problem.”

3. Dynamic Programming Approach: Use dynamic programming to determine the maximum points that can be earned.

   • Let points[i] be the maximum points that can be earned considering elements up to i.
   • If we decide to take i, then we cannot take i-1 (similar to the house robber problem).
   • Use the transformation: earn[i] = i * count[i].

Time Complexity

• Time Complexity: O(n + k) where n is the length of the input array and k is the maximum element in the array (in this case, up to 10000).
• Space Complexity: O(k) due to the additional storage for dynamic programming arrays.

Code

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        unordered_map<int, int> count;
        int maxNum = 0;

        // Count frequency of each number and find max element in nums
        for (int num : nums) {
            count[num]++;
            maxNum = max(maxNum, num);
        }

        // Create the dp array
        vector<int> dp(maxNum + 1, 0);
        for (int i = 1; i <= maxNum; ++i) {
            dp[i] = i * count[i];
        }

        // Apply house robbing DP logic
        for (int i = 2; i <= maxNum; ++i) {
            dp[i] = max(dp[i - 1], dp[i] + dp[i - 2]);
        }

        return dp[maxNum];
    }
};

Explanation

1. We count the frequency of each number in the input array nums using an unordered map count.
2. We determine the maximum number maxNum in nums.
3. We create a DP array dp where dp[i] holds the total points we can earn from taking all instances of i.
4. We then iterate through the array applying the house robber’s logic: either take i and add the result of i-2 or skip i and take the result of i-1.
5. The result is the value of dp[maxNum] which represents the maximum points we can earn.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?