Delete and Earn — House Robber on Frequency Array
Sanjeev SharmaAdvertisement
Problem
Choosing nums[i] adds nums[i] points but removes all occurrences of nums[i]-1 and nums[i]+1. Maximize total points.
Approach — Reduce to House Robber
Build earn[v] = v * freq[v]. Adjacent values conflict → can't pick both earn[v] and earn[v+1]. → House Robber on earn array.
Time: O(n + max_val) | Space: O(max_val)
Solutions
Python
class Solution:
def deleteAndEarn(self, nums: list[int]) -> int:
max_val=max(nums)
earn=[0]*(max_val+1)
for n in nums: earn[n]+=n
prev2=prev1=0
for e in earn: prev2,prev1=prev1,max(prev1,prev2+e)
return prev1
C++
class Solution {
public:
int deleteAndEarn(vector<int>& nums){
int mx=*max_element(nums.begin(),nums.end());
vector<int> earn(mx+1,0);
for(int n:nums) earn[n]+=n;
int prev2=0,prev1=0;
for(int e:earn){int c=max(prev1,prev2+e);prev2=prev1;prev1=c;}
return prev1;
}
};
Complexity
- Time: O(n + M) where M = max value | Space: O(M)
Advertisement
