Delete and Earn - Practice Coding Problems

Delete and Earn - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: 6

💡 Note: Delete 4 to earn 4 points (removes 3). Then delete 2 to earn 2 points. Total: 4 + 2 = 6

Example 2 — Multiple Same Values

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

› Output: 9

💡 Note: Delete all 3's to earn 3×3=9 points (removes all 2's and 4's). This is better than taking 2's and 4's for 2×2+4=8 points

Example 3 — Single Element

$ Input: nums = [1]

› Output: 1

💡 Note: Only one element, so delete it to earn 1 point

Constraints

1 ≤ nums.length ≤ 2×10⁴
1 ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with numbers that can be deleted for points

Delete Rule

Deleting nums[i] removes all nums[i]±1 values

Maximize Points

Choose optimal deletion sequence for maximum total

Key Takeaway

🎯 Key Insight: Transform to House Robber by grouping same numbers - adjacent values can't both be taken

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to transform this into a House Robber problem by counting frequencies of each unique number. Since taking a number eliminates adjacent values, we can't take consecutive numbers. Best approach is frequency count + DP. Time: O(n log k), Space: O(k) where k is unique numbers.

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(k)	O(k)	Top-down recursion with caching to avoid recomputation
Recursive Backtracking	O(2ⁿ)	O(n)	Try every possible combination of elements to delete
Frequency Count + Dynamic Programming	O(n log n)	O(k)	Count frequencies, then solve as House Robber problem

Memoized Recursion — Algorithm Steps

Create frequency map of numbers
Use recursion: for each index, max(take + recurse(next_valid), skip + recurse(next))
Memoize results using index as key

Visualization

Tap to expand

Step-by-Step Walkthrough

Recursive Choices

For each number: take (skip adjacent) or skip

Memoization

Cache results to avoid recomputing same states

Optimal Path

Return maximum points from all cached decisions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NUMS 10000
#define HASH_SIZE 10007

static int count[20001];
static int uniqueNums[MAX_NUMS];
static int uniqueCount;
static int memo[MAX_NUMS];
static int memoSet[MAX_NUMS];

int dp(int index) {
    if (index >= uniqueCount) return 0;
    
    if (memoSet[index]) return memo[index];
    
    int num = uniqueNums[index];
    // Skip current number
    int skip = dp(index + 1);
    
    // Take current number
    int take = num * count[num + 10000];
    int nextIndex = index + 1;
    // Skip adjacent numbers
    while (nextIndex < uniqueCount && uniqueNums[nextIndex] <= num + 1) {
        nextIndex++;
    }
    take += dp(nextIndex);
    
    int result = (skip > take) ? skip : take;
    memo[index] = result;
    memoSet[index] = 1;
    return result;
}

int solution(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    
    memset(count, 0, sizeof(count));
    memset(memoSet, 0, sizeof(memoSet));
    uniqueCount = 0;
    
    // Count frequencies
    for (int i = 0; i < numsSize; i++) {
        count[nums[i] + 10000]++;
    }
    
    // Get unique numbers
    for (int i = 0; i < 20001; i++) {
        if (count[i] > 0) {
            uniqueNums[uniqueCount++] = i - 10000;
        }
    }
    
    return dp(0);
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    int nums[MAX_NUMS];
    int numsSize = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL && numsSize < MAX_NUMS) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k)

Each of k unique numbers is processed once due to memoization

✓ Linear Growth

Space Complexity

O(k)

Memoization table and recursion stack, both size k where k is unique numbers

✓ Linear Space

158.0K Views

Medium Frequency

~25 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler