My C++ solution without using x and y. O(1) space and O(mn) time. Not sure no using x and y is decent solution or not


  • 0
    D

    This is my C++ solution with O(1) space and O(mn) time complexity. The amazing part is I didnt use x and y.

    The helper function is to find the range of the width for each row.

    class Solution {
    public:
        int minArea(vector<vector<char>>& image, int x, int y) {
            if (!image.size()) return 0;
            
            int m = image.size();
            int n = image[0].size();
            
            int mnH = m + 1, mxH = -1, mnW = n + 1, mxW = -1;
            
            for (int i = 0; i < m; i++) {
                int maxV = -1, minV = n + 1;
                findRange(image, i, minV, maxV);
                if (maxV != -1 || minV != (n + 1)) {
                    mnH = min(mnH, i);
                    mxH = max(mxH, i);
                    mxW = max(mxW, maxV);
                    mnW = min(mnW, minV);
                }
            }
           
            return (mxH - mnH + 1) * (mxW - mnW + 1); 
            
        }
    private:
        void findRange(vector<vector<char>>& image, int row, int& mn, int& mx) {
            for (int i = 0; i < image[row].size(); i++) {
                if (image[row][i] == '1') {
                    mn = min(mn, i);
                    mx = max(mx, i);
                }
            }
        }
    };
    

Log in to reply
 

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