# My Java O(n) solution without Math library and coping arrays

• To explain my algorithm, if thief decides to rob house n, the accumulated amount will depends on whether he previously robbed house n - 2 or n - 3, since he cannot rob house n - 1. And it doesn't make sense if he doesn't rob either n - 2 or n - 3, for example, he rob n - 4 instead.

``````n-2 --->
---> n
n-3 --->

public class Solution {
public int rob(int[] num) {
if(num != null) {
if(num.length == 0)
return 0;
if(num.length == 1)
return num[0];
if(num.length == 2)
return (num[0] > num[1]) ? num[0] : num[1];

if(num.length > 2){
//now the num array denotes the max amount the thief could rob so far if this house is chosen to be robbed
num[2] += num[0];
for(int i = 3; i< num.length; i++) {
num[i] += (num[i-2] > num[i-3]) ? num[i-2] : num[i-3];
}
return (num[num.length - 1] > num[num.length - 2]) ? num[num.length - 1] : num[num.length - 2];
}
}
return 0;
}
}``````

• Nice solution. I made this into much harder graph generation/traversal problem.

``````public class Solution{
private class Node{
Node left;
Node right;
int value;
boolean visited = false;
int accumVal;
}

public int rob(int[] num) {
if (num == null) {
return 0;
}
if (num.length == 1) {
return num[0];
}
if (num.length == 2) {
return Math.max(num[0], num[1]);
}

Node n = new Node();
Map<Integer,Node> nodesUsed = new HashMap<Integer,Node>();

buildTree(n, num, 0, nodesUsed);
calculateMax(n,  0);

return n.accumVal;
}

private int calculateMax(Node n, int val){
Node left = n.left;
Node right = n.right;
if (left == null && right == null){
n.accumVal = n.value;
return n.value;
}
int val1 = 0;
int val2 = 0;
if (left!=null){
if (left.visited == false){
val1 = calculateMax(left,  val+n.value);
left.visited = true;
}
else{
val1 = left.accumVal;
}
}
if (right!=null){
if (right.visited == false){
val2 = calculateMax(right, val+n.value);
right.visited = true;
}
else{
val2 = right.accumVal;
}
}
n.accumVal = n.value+Math.max(val1,val2);
return n.accumVal;
}

private void buildTree(Node parent, int[]num, int index, Map<Integer,Node> nodesUsed){
if (num.length-index>1){
int val1 = num[index];
int val2 = num[index+1];

Node node1 = nodesUsed.get(index);
Node node2 = nodesUsed.get(index+1);

boolean justBuilt1 = false;
boolean justBuilt2 = false;
if (node1 == null){
node1 = new Node();
node1.value = val1;
nodesUsed.put(index, node1);
justBuilt1 = true;
}
if (node2 == null){
node2 = new Node();
node2.value = val2;
nodesUsed.put(index+1, node2);
justBuilt2 = true;
}

parent.left=node1;
parent.right=node2;

if (justBuilt1){
buildTree(node1,num, index+2, nodesUsed);
}
if (justBuilt2){
buildTree(node2, num, index+3, nodesUsed);
}

}
else if (num.length-index == 1){
Node n = nodesUsed.get(index);
if (n == null){
int val = num[index];
n = new Node();
n.value = val;
}
parent.left = n;
}
}
}``````

• brilliant solution

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