Adrian
BAN USERCreate a quadrant decision tree from the current co-ordinate with depth = n.
While you are constructing the tree, if a branch reached an out of bound condition, increase
deadly branches count by 1. And then move backwards using recursion to construct the next branch and so on. The final count of the bad branches/ the total number of branches is your probability. This is similar to what is used in gaming.
How about constructing a Trie of the dictionary and for every letter in the Set follow the Trie structure of the words. If you found in the trie path a letter that doesn't belong to the set stop and start over again with the next letter with the set. And so on.
This solution is order O(k^2) and its not a function of the size of the dictionary.
In my opinion, we simply build a two dimensional array. Each element of the arrays is a struct (x,y)
- Adrian March 23, 2014X represents the number of consecutive ones in the row
Y represents the number of consecutive ones in the column.
F(i,j) = if A(i,j) is 1 then F(i,j) = F(i-1) + 1 , F(j-1) + 1
Once you hit a zero, you initialize the cell to 0,0
Sample Array for the input:
0,0 0,0 0,0 1,0 0,0
1,1 2,1 3,1 0,0 0,0
1,2 2,2 3,2 4,1 0,0
1,3 2,3 0,0 0,0 0,0
1,4 2,4 0,0 1,1 0,0
And then simply doing another loop in the array, multiply the X*Y coordinates and the largest product is your largest triangle. O(n^2)