Share my O(1) space O(n^2) time c++ solution


  • 0
    H

    This looks like brute force solution at first sight. After added some boundary checks, the average time can be significantly reduced close to O(n^2). It is Ω(n^2) rather than O(n^2).

    class Solution {
    public:
        int maximalRectangle(vector<vector<char>>& matrix) {
            int m = matrix.size();
            if (m == 0) return 0;
            int n = matrix[0].size();
            int res = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] != 0) {
                        res = max(res, helper(matrix, i, j));
                    }
                    if (res >= (m-i)*(n-j)) break; // no better result exist
                }
                if (res >= (m-i) * n) break; // no better result exist 
            }
            return res;
        }
        
        int helper(vector<vector<char>>& mtx, int row, int col) {
            int max_r = mtx.size();
            int max_c = mtx[0].size();
            int max = 0;
            for (int i = row; i < max_r; i++) {
                for (int j = col; j < max_c; j++) {
                    if (mtx[i][j] == '0') max_c = j; // implicitly break the inner loop
                }
                max = std::max(max, (i-row+1)*(max_c-col));
                if (mtx[i][col] == '0') break; //no better result exist
            }
            return max;
        }
    };
    

  • 0

    Your analysis is wrong, you can't just say O(n^2) and completely ignore m.


  • 0

    Also, assuming you're thinking of quadratic matrices only (i.e., m=n), then it's not O(n^2) but only O(n^4). Just think of a quadratic matrix where the upper left quadrant only contains '1' and the rest of the matrix contains only '0'. Then you'll do full brute force on that quadrant and its size is θ(n^2), so your time is θ(n^4).


Log in to reply
 

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