Delete And Earn Solution for Accenture

Company: Accenture · Difficulty: Medium · Topics: Array, Dynamic Programming, Hash Table

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. 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.

Key Understanding:

• When you pick a number, you earn points equal to that number
• You must delete all occurrences of (number - 1) and (number + 1)
• You can perform this operation multiple times
• Goal is to maximize total points earned
• This creates a constraint: if you take a number, you cannot take its adjacent numbers

Examples

Example 1:

Input: nums = [3,4,2]

Output: 6

Explanation:

• Step 1: Delete 4 to earn 4 points. Consequently, 3 is also deleted (because 4-1=3).
• Step 2: Delete 2 to earn 2 points. No adjacent numbers to delete.
• Total points = 4 + 2 = 6

Alternative approach:

• If we delete 3 first: earn 3 points, delete 2 and 4
• Then we can only delete 2 (but 2 is already deleted)
• Total points = 3 (less than 6)

Example 2:

Input: nums = [2,2,3,3,3,4]

Output: 9

Explanation:

• Step 1: Delete a single 3 to earn 3 points. All 2's and 4's are also deleted (because 3-1=2 and 3+1=4).
• Step 2: Delete 2 to earn 2 points (if any 2's remain).
• Step 3: Delete 4 to earn 4 points (if any 4's remain).
• Total points = 3 + 2 + 4 = 9

Note: After deleting 3, all 2's and 4's are automatically deleted, so we can't earn additional points from them.

Example 3:

Input: nums = [1,1,1,2,4,5,5,5,6]

Output: 18

Explanation:

• Step 1: Delete 5 to earn 15 points (3 × 5). Delete 4 and 6.
• Step 2: Delete 2 to earn 2 points. Delete 1.
• Step 3: Delete 1 to earn 1 point (if any 1's remain).
• Total points = 15 + 2 + 1 = 18

Intuition

This problem is similar to the "House Robber" problem. The key insight is that if we choose to take a number, we cannot take its adjacent numbers (number-1 and number+1).

Why This Works:

• When you delete a number, you must also delete all adjacent numbers
• This creates a constraint similar to House Robber: you can't take adjacent houses
• The difference is that here we have frequency counts and need to maximize total value

Dynamic Programming Approach:

• Count the frequency of each number
• Sort the unique numbers
• For each number, decide whether to take it or not
• If we take a number, we cannot take adjacent numbers
• Use DP to find the maximum points

Approach

Approach 1: Dynamic Programming with Full Array

Algorithm:

1. Count frequency of each number in the array

2. Create a frequency array where freq[i] = count of number i

3. Use DP: dp[i] = max(dp[i-1], dp[i-2] + freq[i] * i)

4. Return dp[max_number]

Why This Works:

• dp[i] represents the maximum points we can earn using numbers from 1 to i
• At each step, we choose between:
• Taking the current number i: dp[i-2] + freq[i] * i
• Skipping the current number: dp[i-1]

Approach 2: Optimized DP with Two Variables

Algorithm:

1. Count frequency of each number

2. Use two variables (prev2, prev1) to track previous states

3. Iterate through all possible numbers (1 to max_number)

4. Update maximum points using the same DP formula

Approach 3: Recursive with Memoization

Algorithm:

1. Count frequency of each number

2. Use recursive function with memoization

3. For each number, try taking it or skipping it

4. Return the maximum of both choices

Dry Run

Let's trace through Example 1: nums = [3,4,2]

Step-by-Step Process:

1. Count frequencies:

• freq[2] = 1, freq[3] = 1, freq[4] = 1

2. DP Array:

• dp[0] = 0 (no numbers)
• dp[1] = 0 (no 1's in array)
• dp[2] = max(dp[1], dp[0] + freq[2] * 2) = max(0, 0 + 1 * 2) = 2
• dp[3] = max(dp[2], dp[1] + freq[3] * 3) = max(2, 0 + 1 * 3) = 3
• dp[4] = max(dp[3], dp[2] + freq[4] * 4) = max(3, 2 + 1 * 4) = 6

3. Result: dp[4] = 6

Optimized Approach:

• prev2 = 0, prev1 = 0
• For i = 2: current = max(0, 0 + 2) = 2; prev2 = 0, prev1 = 2
• For i = 3: current = max(2, 0 + 3) = 3; prev2 = 2, prev1 = 3
• For i = 4: current = max(3, 2 + 4) = 6; prev2 = 3, prev1 = 6

Key Insights

1. House Robber Analogy: This is essentially House Robber with frequency counts

2. Adjacent Constraint: Taking a number prevents taking adjacent numbers

3. Frequency Multiplication: Total value = frequency × number

4. Optimal Substructure: Solution for range [1...i] depends on [1...i-1] and [1...i-2]

5. Greedy Won't Work: Always taking the largest number doesn't guarantee optimal solution

Edge Cases

1. Empty Array: Return 0

2. Single Element: Return the value of that element

3. All Same Numbers: Return count × number

4. Consecutive Numbers: Only one can be chosen

5. Large Numbers: Handle efficiently with optimized DP

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: Optimized Dynamic Programming (Best)

Time Complexity: O(n + M) where n is array length and M is max number

Space Complexity: O(1) - Constant extra space

Solution 2: Full DP Array

Time Complexity: O(n + M)

Space Complexity: O(M) - DP array size

Solution 3: Recursive with Memoization

Time Complexity: O(n + M)

Space Complexity: O(M) - Memoization array

More Accenture coding questions