Awesome Python 4-liner with explanation - Reduce to House Robbers Question 🌝

• This question can be reduced to the House Robbers question also on LeetCode. Please have a look at it if you haven't seen it before.

Observations:

• The order of `nums` does not matter.
• Once we decide that we want a `num`, we can add all the occurrences of `num` into the total.

We first transform the `nums` array into a `points` array that sums up the total number of points for that particular value. A value of `x` will be assigned to index `x` in `points`.

`nums`: `[2, 2, 3, 3, 3, 4]` (2 appears 2 times, 3 appears 3 times, 4 appears once)
`points`: `[0, 0, 4, 9, 4]` <- This is the gold in each house!

The condition that we cannot pick adjacent values is similar to the House Robber question that we cannot rob adjacent houses. Simply pass `points` into the `rob` function for a quick win 🌝!

- Yangshun

``````class Solution(object):
def rob(self, nums):
prev = curr = 0
for value in nums:
prev, curr = curr, max(prev + value, curr)
return curr

def deleteAndEarn(self, nums):
points = [0] * 10001
for num in nums:
points[num] += num
return self.rob(points)
``````

When `rob` is used directly, it is just 6 lines:

``````class Solution(object):
def deleteAndEarn(self, nums):
points, prev, curr = [0] * 10001, 0, 0
for num in nums:
points[num] += num
for value in points:
prev, curr = curr, max(prev + value, curr)
return curr
``````

Suggested by @ManuelP, it can be further shortened into 4 lines if you use `collections.Counter` and modify the `rob` function:

``````class Solution(object):
def deleteAndEarn(self, nums):
points, prev, curr = collections.Counter(nums), 0, 0
for value in range(10001):
prev, curr = curr, max(prev + value * points[value], curr)
return curr
``````

• Could you please explain this line?

``````prev, curr = curr, max(prev + value, curr)
``````

• @GreatWolf You might find the DP solution easier to understand. If you used a DP array, the formula is:

`dp[i] = max(dp[i - 1], dp[i - 2] + value)`

Essentially saying the max value at an index is the bigger of the (previous value) or (current value at index + previous previous value), because of the non-adjacent constraints.

`prev, curr = curr, max(prev + value, curr)` is just simplifying the DP array because we don't need an entire array, we just need the previous two values.

• ``````def deleteAndEarn(self, nums):
ctr, prev, curr = collections.Counter(nums), 0, 0
for num in range(10001):
prev, curr = curr, max(prev + num * ctr[num], curr)
return curr
``````

Lol, even brute force gets accepted:

``````def deleteAndEarn(self, nums):
prev = curr = 0
for num in nums and range(min(nums), max(nums) + 1):
prev, curr = curr, max(prev + num * nums.count(num), curr)
return curr``````

• @ManuelP Nice! I wanted to use `Counter` initially but then I can't reuse `rob` function so I didn't do that in the end. Very cool approach indeed!

• @yangshun You could do it like this:

``````def deleteAndEarn(self, nums):
ctr = collections.Counter(nums)
return self.rob([num * ctr[num] for num in range(10001)])
``````

But yours is much better.

Very nice to reduce it to an old problem's solution, btw.

• @yangshun Thanks or your explaintion!!! Now I how it works.

• [0, 0, 0, 4, 9, 4]

Minor but should it be:
[0, 0, 4, 9, 4, 0]

• @lalib Thanks for pointing that out, I changed it to `[0, 0, 4, 9, 4]`

• Java Version:

``````class Solution {
public int deleteAndEarn(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
int max_val = 0;
for(int ele:nums){
map.put(ele,map.getOrDefault(ele,0)+1);
max_val = Math.max(max_val,ele);
}

int[][] dp = new int[max_val+1][2];
for(int i=1;i<=max_val;i++){
if(!map.containsKey(i)){
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]);
dp[i][1] = Math.max(dp[i-1][0],dp[i-1][1]);
continue;
}

dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]);
dp[i][1] = dp[i-1][0] + i*map.get(i);

}

return Math.max(dp[max_val][0],dp[max_val][1]);
}
}

``````

• Clean Java version

``````class Solution {
public int deleteAndEarn(int[] nums) {
if(nums == null || nums.length == 0)return 0;
if(nums.length == 1)return nums[0];

int RANGE = 10000;
int[] dp = new int[RANGE + 1];
for(int n : nums)dp[n] += n;

//index 0 house is not used, -> 0
//index 1 is just the value in dp[1]
int max = dp[1];
for(int i = 2; i < RANGE + 1; i ++) {
dp[i] = Math.max(dp[i - 1], dp[i] + dp[i - 2]);
if(dp[i] > max)max = dp[i];
}

return max;
}
}
``````

• I ran your shortest code in 300 ms. I managed a run in 65 ms by stepping through the counter's elements instead of through the array of 10,000 elements (most of which are blank most of the time). The key here is in keeping track if the previous element of the counter is 1 less than the current we're processing (see prevElement value). My solution also scales just fine to larger values of prize points.

``````    def deleteAndEarn(self, nums):
histogram = collections.Counter(nums)
value = valueBack1 = valueBack2 = 0
prevElement = -9999
for element,count in histogram.items():
if prevElement+1 == element:
value = max(valueBack1, valueBack2+element*count)
else:
value = valueBack1 + element*count
valueBack2 = valueBack1
valueBack1 = value
prevElement = element
return value
``````

• @SunnyvaleCA Your code is wrong. You fail for example input `[8, 7]`, returning 15 instead of the correct 8.

• @ManuelP Thanks for that. I'm amazed that my code passed all the tests. My mistake was that I somehow thought histogram.items() was delivering elements in sorted order — I'm a C++ / std::map kind of guy trying to learn python and expecting similar sorted behavior. Anyway, I changed the code from:
`histogram.items()`
to:
`sorted(histogram.items())`

For no apparent reason (other than that the servers are probably not as overloaded), my code scored an even better 56 ms!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.