Better space complexity for problem 17.3

#1

In problem 17.3 (Count number of way to traverse a 2D array), the solution in the book uses a 2D array which has space complexity of O(m x n).
I propose another solution which uses an insight that: if there is an obstacle at (i, j), there is no way out of it. That means, for i > 0 and j > 0:
num_path(i, j) = obstacle(i -1, j) ? 0 : num_path(i - 1, j) + obstacle(i, j - 1) ? 0 :num_path(i, j - 1)

Therefore, I can reduce the space complexity to O(n) for matrix n x m by using one-dimensional array to compute the result. I tested with the testing engine on EPI’s github.

int CountNumWaysWithObstacles(int n, int m, const vector<deque<bool>>& obstacles) {
  vector<int> num_path(m, 0);

  if (obstacles[0][0] || obstacles.back().back())
     return 0;
  num_path[0] = 1;

  for (int i = 0; i < n; ++i) {
       for (int j = 0; j < m; ++j) {
          if (i > 0 && obstacles[i - 1][j])
             num_path[j] = 0;
          if (j > 0 && !obstacles[i][j - 1])
             num_path[j] += num_path[j - 1];
       }
   }
   return num_path.back();
}

Further optimization should reduce the space complexity to O(min(m,n)).

0 Likes
#2

Hey Duc,

It is definitely a feasible solution for reducing space complexity of this problem. In fact, many DP problems have such optimization techniques. This is mainly based on the observation of the computation order of DP formula. Thanks for sharing this.

0 Likes