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


  • 16

    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
    

  • 0
    G

    Could you please explain this line?

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

  • 0

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


  • 1
    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

  • 0

    @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!


  • 1

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


  • 1
    G

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


  • 1
    L

    @yangshun said in Awesome Python 4-liner with explanation - Reduce to House Robbers Question 🌝:

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

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


  • 0

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


  • 0
    T

    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]);
        }
    }
    
    

  • 1
    X

    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;
        }
    }
    

  • 0
    S

    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
    

  • 1

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


  • 1
    S

    @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!


Log in to reply
 

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