Microsoft Question: House Robber II

Problem: It is same as previous House Robber problem except here we have one more condition:

• All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. 

Example:

Input: nums = [5,8,6]
Output: 8
Explanation: You cannot rob house 1 (money = 5) and then rob house 3 (money = 6), because they are adjacent houses.

Approach: We will have the same approach as our previous problem with one difference. Here we are going to have two tables instead of one table. One table will store the max money excluding last house and second will store the max money excluding first house. We will fill the Tables in same way we did it in previous problem. 

   IF i != 2

    TableWithLastHouse[i] = MAX(TableWithLastHouse[i - 1], TableWithLastHouse[i - 2] + nums[i]   

   ELSE IF i != nums.Length - 1

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

Ultimately we will take the maximum of TableWithFirstHouse[n - 2] and TableWithLastHouse[n - 1]. 

We can use the same strategy of having 4 variables; 2 variables per table instead of having Tables.

Implementation in C#:

        public static int RobII(int[] nums)

        {

            if (nums?.Length == 0)

            {

                return 0;

            }

            if (nums.Length == 1)

            {

                return nums[0];

            }

            if (nums.Length == 2) 

            {

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

            }

            int prevMaxWithFirstHouse = nums[0]; // Won't include the last house

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

            int prevMaxWithLastHouse = nums[1]; // Won't include the first house

            int currMaxWithLastHouse = Math.Max(nums[1], nums[2]);

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

            {

                if (i != 2)

                {

                    int temp = currMaxWithLastHouse;

                    currMaxWithLastHouse = Math.Max(currMaxWithLastHouse, prevMaxWithLastHouse + nums[i]);

                    prevMaxWithLastHouse = temp;

                }

                if (i != nums.Length - 1)

                {

                    int temp = currMaxWithFirstHouse;

                    currMaxWithFirstHouse = Math.Max(currMaxWithFirstHouse, prevMaxWithFirstHouse + nums[i]);

                    prevMaxWithFirstHouse = temp;

                }

            }

            return Math.Max(currMaxWithFirstHouse, currMaxWithLastHouse);

        }

Complexity: O(n)