LeetCode 883 - Projection Area of 3D Shapes

https://leetcode.com/problems/projection-area-of-3d-shapes/

On a N * N grid, we place some 1 * 1 * 1 cubes that are axis-aligned with the x, y, and z axes.

Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).

Now we view the projection of these cubes onto the xy, yz, and zx planes.

A projection is like a shadow, that maps our 3 dimensional figure to a 2 dimensional plane. 

Here, we are viewing the "shadow" when looking at the cubes from the top, the front, and the side.

Return the total area of all three projections.

Example 1:

Input: [[2]]
Output: 5

Example 2:

Input: [[1,2],[3,4]]
Output: 17
Explanation: 
Here are the three projections ("shadows") of the shape made with each axis-aligned plane.

From the top, the shadow made by the shape will be 1 square for each non-zero value.

From the side, the shadow made by the shape will be the largest value for each row in the grid.

From the front, the shadow made by the shape will be the largest value for each column in the grid.

Example

With the example [[1,2],[3,4]]:

• The shadow from the top will be 4, since there are four non-zero values in the grid;
• The shadow from the side will be 2 + 4, since the maximum value of the first row is 2, and the maximum value of the second row is 4;
• The shadow from the front will be 3 + 4, since the maximum value of the first column is 3, and the maximum value of the second column is 4.

  public int projectionArea(int[][] grid) {

    int N = grid.length;

    int ans = 0;

    for (int i = 0; i < N; ++i) {

      int bestRow = 0; // largest of grid[i][j]

      int bestCol = 0; // largest of grid[j][i]

      for (int j = 0; j < N; ++j) {

        if (grid[i][j] > 0)

          ans++; // top shadow

        bestRow = Math.max(bestRow, grid[i][j]);

        bestCol = Math.max(bestCol, grid[j][i]);

      }

      ans += bestRow + bestCol;

    }

    return ans;

  }

https://leetcode.com/problems/projection-area-of-3d-shapes/discuss/156771/11-line-1-pass-Java-code-and-explanation-of-the-problem-time-O(N-2)-space-O(1).

Note: for a N * N grid, i & j limits are both grid.length.

1. get max out of grid [j] [i] (j = 0 ~ grid.length), the projection in x direction (on y-z plane)
2. get max out of grid[i][j] (j = 0 ~ grid.length), the projection in y direction (on x-z plane)

    public int projectionArea(int[][] grid) {
        int z = 0, x = 0, y = 0;
        for (int i = 0; i < grid.length; ++i) {
            int mx = 0, my = 0; // max of x & y values.
            for (int j = 0; j < grid.length; ++j) {
                mx = Math.max(mx, grid[j][i]); // see above 1
                my = Math.max(my, grid[i][j]); // see above 2
                if (grid[i][j] > 0) { ++z; } // only the cell with positive value has a projection area of size 1 in z direction (on x-y plane). 
            }
            x += mx; y += my; // x & y projection accumulation.
        }
        return x + y + z;
    }

https://leetcode.com/problems/projection-area-of-3d-shapes/discuss/156726/C%2B%2BJavaPython-Straight-Forward

    public int projectionArea(int[][] grid) {
        int res = 0, n = grid.length;
        for (int i = 0, v = 0; i < n; ++i, res += v, v = 0)
            for (int j = 0; j < n; ++j)
                v = Math.max(v, grid[i][j]);
        for (int j = 0, v = 0; j < n; ++j, res += v, v = 0)
            for (int i = 0; i < n; ++i)
                v = Math.max(v, grid[i][j]);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] > 0) res++;
        return res;
    }