We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Delete and Earn

Number: 740

Difficulty: Medium

Paid? No

Companies: Amazon, TikTok, Accenture, Google, Microsoft, Citadel, Meesho, Apple, Adobe, Bloomberg, Turvo, Akuna Capital

Problem Description

Given an integer array nums, you want to maximize the number of points by repeatedly performing the following operation: choose any number nums[i], earn points equal to nums[i], and then delete all elements equal to nums[i] - 1 and nums[i] + 1. Return the maximum points you can achieve.

Key Insights

  • Transform the problem by aggregating points for each unique number, similar to grouping.
  • Realize that if you earn points from number x, you cannot earn points from x-1 and x+1.
  • The problem resembles the House Robber problem where adjacent houses (numbers) cannot be robbed (taken).
  • Use dynamic programming to decide whether to take or skip each unique number.

Space and Time Complexity

Time Complexity: O(max + n) where max is the maximum number in nums (since we iterate through a frequency array up to max) and n is the length of nums. Space Complexity: O(max) for the frequency and dp arrays.

Solution

The solution begins by using a hash table (or frequency array) to compute the total points that can be earned from each unique number (i.e., points = number * frequency). Then, we convert the problem to one similar to the House Robber problem: for each number i, decide to either take dp[i-2] plus the current total points at i or skip i and take dp[i-1]. This decision is captured in the recurrence relation dp[i] = max(dp[i-1], dp[i-2] + total[i]). Finally, return dp[max_num] as the result.

Code Solutions

# Python solution for Delete and Earn

def deleteAndEarn(nums):
    # Step 1: Build frequency dictionary
    points = {}
    for num in nums:
        if num in points:
            points[num] += num
        else:
            points[num] = num

    # Step 2: Find the maximum number in nums to define the dp array size
    max_num = max(nums)
    
    # Step 3: Initialize dp array where dp[i] represents maximum points up to i
    dp = [0] * (max_num + 1)
    dp[0] = 0
    dp[1] = points.get(1, 0)
    
    # Step 4: Fill dp using recurrence relation
    for i in range(2, max_num + 1):
        dp[i] = max(dp[i-1], dp[i-2] + points.get(i, 0))
        
    # Final answer is maximum points at the maximum number
    return dp[max_num]

# Example usage:
print(deleteAndEarn([3,4,2]))  # Output: 6
← Back to All Questions