5 lines C++ code, compute the area directly, no use of x and y location.


  • 0
    O
    class Solution {
    public:
        int minArea(vector<vector<char>>& image, int x, int y) {
            int left = INT_MAX, right = INT_MIN, up = INT_MAX, down = INT_MIN, N = image.size(), M = image[0].size();
            for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (image[i][j] == '1') {
                left = min(left, j); right = max(right, j); up = min(up, i); down = max(down, i);
            }
            return (down - up + 1) * (right - left + 1);
        }
    };

  • 0
    O

    By the way, what's point of giving us x and y location?

    No matter which location we got the answer is always the same, cause all the '1' s are connected.

    Actually I didn't got the point of this problem but my code got AC anyway.


  • 1

    The point of x and y is that we can use them to do something faster than full brute force.


  • 0
    O

    Oh yah thanks very much.


  • 1

    I think the author should give large test cases which make the (x, y) information useful. For example m = n = 10000 with 10000 black cells in it.


  • 0
    Y

    you did not get the point of this problem.
    In average case, this problem can be solved in O(n). Your method is square.


Log in to reply
 

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