bohanl
BAN USERA dynamic programming approach..
public static int count(boolean[][] T) {
if (T == null || T[0] == null)
return 0;
int m = T.length;
int n = T[0].length;
int[][] C = new int[m][n];
// set up initial conditions
C[0][0] = T[0][0] ? 1 : 0;
for (int i = 1; i < m; i++) {
C[i][0] = C[i-1][0];
if (T[i][0] && !T[i-1][0])
C[i][0] += 1;
}
for (int j = 1; j < n; j++) {
C[0][j] = C[0][j-1];
if (T[0][j] && !T[0][j-1])
C[0][j] += 1;
}
// iterations
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
int up = C[i-1][j];
int left = C[i][j-1];
C[i][j] = up > left ? up : left;
if (!T[i-1][j] && !T[i][j-1])
C[i][j] += 1;
}
}
return C[m-1][n-1];
}
Assuming array A and a number b, take another array C where C[i] = b - A[i]. ----> O(n)
- bohanl January 27, 2013Add elements in A into a hash table ----> O(n)
traverse through array C to see if any of elements is contained in the hash table ---> O(n)
This should be O(n)