house-robber: C#, Python, JavaScript, Java

Continuing on the experience of learning the pros/cons for different programming languages, let us try to solve the leetcode problem titled house-robber.

The algorithm is straightforward once you understand it. Essentially, you need to apply dynamic programming technique and dynamically decided on each house whether to take money from the house or leave it in order to maximize the outcome abiding by the condition that you can not take money from 2 consecutive houses.

psuedo code:

    if there is 1 house, take money from it.

    if there are 2 houses, take money from house that has more money

    for ith house, take the higher of the 1. money collected till i-1th house 2. money     collected till i-2th house and money present in ith house

C#

    public int Rob(int[] nums) {

        if(nums == null || nums.Length == 0){

            return 0;

        }

        if(nums.Length == 1){

            return nums[0];

        }

        if(nums.Length == 2){

            return Math.Max(nums[0], nums[1]);

        }

        var dp = new int[nums.Length];

        dp[0] = nums[0];

        dp[1] = Math.Max(nums[1], nums[0]);

        for(int i = 2; i < nums.Length; i++){

            dp[i] = Math.Max(dp[i-1], dp[i-2] + nums[i]);

        }

        return dp[nums.Length - 1];

    }

JavaScript

var rob = function(nums) {

    if(nums === undefined || nums.length == 0){

        return 0;

    }

    if(nums.length == 1){

        return nums[0];

    }

    if(nums.length == 2){

        return Math.max(nums[0], nums[1]);

    }

    const dp = new Array(nums.length);

    dp[0] = nums[0];

    dp[1] = Math.max(nums[0], nums[1]);

    for(let i = 2; i < nums.length; i++){

        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);

    }

    return dp[nums.length - 1];

};

Python

def rob(self, nums: List[int]) -> int:

        if not nums :

            return 0

        length = len(nums)

        if length <= 2 :

            return max(nums)

        dp = [0]*length

        dp[0] = nums[0]

        dp[1] = max(nums[0], nums[1])

        for idx in range(2, length, 1):

            dp[idx] = max(dp[idx - 1], dp[idx - 2] + nums[idx])

        return dp[length - 1]

Java

public int rob(int[] nums) {

        if(nums == null || nums.length == 0){

            return 0;

        }

        if(nums.length == 1){

            return nums[0];

        }

        if(nums.length == 2){

            return Math.max(nums[1], nums[0]);

        }

        int[] dp = new int[nums.length];

        dp[0] = nums[0];

        dp[1] = Math.max(nums[0], nums[1]);

        for(int i = 2; i < nums.length; i++){

            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);

        }

        return dp[nums.length - 1];

    }

Observations:

1. Initializing an array of a certain length is little weird in Python (but intuitive at the same time) where you just multiply [0] n times :)

2. Python code consumes the least lines of code when writing identical code in different languages. It is possible to reduce the lines of code in all languages by getting rid of dp array and using 2 pointers as at every ith position, one is only interested in i-1 and i-2 values. However, i believe python code will still be the most succinct. Take below code for example that swaps 2 variables.

C#, Java, JavaScript

int tmp = val1;

val1 = val2;

val2 = tmp;

Python

val1, val2 = val2, val1