Leetcode 740: Delete and Earn

Input: The input is an integer array representing the numbers from which you will be selecting elements to delete and earn points.

Example: nums = [5, 6, 4]

Constraints:

• 1 <= nums.length <= 2 * 10^4

• 1 <= nums[i] <= 10^4

Output: Return the maximum number of points you can earn by performing the operation some number of times.

Example: For nums = [5, 6, 4], the output should be 8.

Constraints:

Goal: Maximize the total points earned from deleting elements and ensuring no adjacent elements (nums[i] - 1 or nums[i] + 1) are left.

Steps:

• Count the occurrences of each number in the array.

• Create a dynamic programming array where dp[i] stores the maximum points obtainable by considering numbers from 1 to i.

• For each number, either choose to delete it and earn points or skip it and carry forward the previous maximum.

• Return the final value from the dynamic programming array.

Goal: The input will always satisfy the given constraints, ensuring a manageable number of operations.

Steps:

• 1 <= nums.length <= 2 * 10^4

• 1 <= nums[i] <= 10^4

Assumptions:

• The input array nums will always contain at least one element.

• Input: For nums = [5, 6, 4], the output is 8.

• Explanation: By deleting the number 6 and 4, we maximize our points by choosing the best elements to remove.

Approach: A dynamic programming approach to maximize the total points by efficiently handling adjacent numbers.

Observations:

• This problem can be reduced to a dynamic programming problem where the state depends on whether we take the current element or skip it.

• We can optimize our solution by keeping track of maximum points for each number up to the largest value in the array.

Steps:

• Count the occurrences of each number in the input array.

• Initialize a dynamic programming array where dp[i] holds the maximum points we can earn considering numbers 1 to i.

• Iterate through each number, calculating whether to take or skip it by considering the points from taking it versus the previous maximum points.

• Return the result from the last element of the dynamic programming array.

Empty Inputs:

• The input will always contain at least one element, so no empty array cases will exist.

Large Inputs:

• For large inputs (up to 20,000 elements), the algorithm should efficiently handle the array within the time limits.

Special Values:

• If the array contains only one unique number, the algorithm should return the total points earned by deleting all occurrences of that number.

Constraints:

• The solution must efficiently handle inputs up to the largest constraint.

int deleteAndEarn(vector<int>& nums) {
    int n = 10001;
    vector<int> val(n + 1, 0);
    vector<int> dp (n + 1, 0);
    
    for(int num : nums)
      val[num] += num;
    
    dp[0] = 0;
    dp[1] = val[0];
    for(int i = 1; i < n; i++)
    dp[i + 1] = max(dp[i], dp[i - 1] + val[i]);
    
    return dp[n];
}

1 : Function Definition

int deleteAndEarn(vector<int>& nums) {

Defines the function that solves the problem. It takes an array of integers as input.

2 : Variable Initialization

    int n = 10001;

Initializes a variable `n` to store the size of the `val` and `dp` vectors, based on the maximum possible value in `nums`.

3 : Vector Initialization

    vector<int> val(n + 1, 0);

Creates a vector `val` to store the total points earned for each number.

4 : Vector Initialization

    vector<int> dp (n + 1, 0);

Creates a vector `dp` to store the maximum points that can be earned up to each number.

5 : Loop: Populating `val` vector

    for(int num : nums)

Iterates over each number in `nums` and updates the `val` vector.

6 : Update Operation

      val[num] += num;

Updates the `val` vector by adding the current number to its corresponding index.

7 : Base Case Setup

    dp[0] = 0;

Sets the base case for `dp[0]`, which is 0, representing that no points are earned when no numbers are considered.

8 : Base Case Setup

    dp[1] = val[0];

Sets the base case for `dp[1]` to be the value of `val[0]`, representing that the first number's point value is considered.

9 : Dynamic Programming Iteration

    for(int i = 1; i < n; i++)

Starts the dynamic programming loop to calculate the maximum points that can be earned up to each number.

10 : Dynamic Programming Transition

    dp[i + 1] = max(dp[i], dp[i - 1] + val[i]);

For each number `i`, calculates the maximum points by either taking the points up to `i` or including the points from `i` and skipping `i - 1`.

11 : Return Statement

    return dp[n];

Returns the maximum points that can be earned by considering all numbers.

Best Case: O(n), where n is the number of elements in the array.

Average Case: O(n), as the algorithm only processes each element once.

Worst Case: O(n), as each element is processed only once in a linear scan.

Description: The time complexity is O(n), as we perform a constant amount of work for each element in the array.

Best Case: O(n), as we may need space for both the dynamic programming array and frequency counts.

Worst Case: O(n), due to the space used by the dynamic programming array and frequency count array.

Description: The space complexity is O(n) due to the space needed for the dynamic programming and frequency count arrays.

Leetcode 740: Delete and Earn

Solution to LeetCode 740: Delete and Earn Problem

Explore →