Walkthrough of the general algorithm
Just my notes of a walkthrough of the general algorithm people used to solve this question, hope this helps\n\n\n\t/\n     * 1. Precalculate the # of consecutiv
Just my notes of a walkthrough of the general algorithm people used to solve this question, hope this helps\n\n\n\t/**\n     * 1. Precalculate the # of consecutive ones (vertically) in the matrix,\n     *    --> which we are actually calculating the height of each column/histogram\n     *\n     * [0,0,1]      [0,0,1]\n     * [1,1,1] -->  [1,1,2]\n     * [1,0,1]      [2,0,3]\n     *\n     * 2. Sort each row in decreasing order (Theoretically)\n     *    We need to do this, so that we are ensuring the taller\n     *    histograms are always before the shorter ones, which\n     *    allows us to calculate the area later as (current height) * (current width)\n     *                             Row 0:    Row 1:      Row 2:\n     * [0,0,1]      [0,0,1]       [1,0,0]   [0,0,1]     [1,0,0]\n     * [1,1,1] -->  [1,1,2]  -->  [2,1,1]   [1,1,2]     [2,1,1]\n     * [1,0,1]      [2,0,3]       [3,0,2]   [2,0,3]     [3,2,0]\n     *\n     * And actually, we don\'t need to sort the entire matrix everytime when we\n     * sort a single row. We can just sort the single row to get the largest submatrix\n     * as if the entire matrix is sorted, because we are able to calculate the largest matrix\n     * with the information from that singly sorted row.\n     *\n     * For example, if we only sort row 2 (last row):\n     *                           Row 2:\n     * [0,0,1]      [0,0,1]     [0,0,1]\n     * [1,1,1] -->  [1,1,2]     [1,1,2]\n     * [1,0,1]      [2,0,3] --> [3,2,0]\n     *\n     * At row=2, col=0,\n     *      --> we know there are 3 consecutive \'1\'s vertically from the top\n     *      --> there is a submatrix/rectangle of (height=3) * (width=1)=3\n     * At row=2, col=1,\n     *      --> we know there are 2 consecutive \'1\'s vertically from the top\n     *      --> there is a submatrix/rectangle of (height=2) * (width=2)=4\n     *          --> which you may notice, width=(col+1)\n     * At row=2, col=2\n     *      --> we know there are 0 consecutive \'1\'s vertically from the top\n     *      --> there is a submatrix/rectangle of (height=0) * (width=3)=0\n     *\n     * Let\'s go back and sort just row 0, and row 1\n     *                           Row 0:\n     * [0,0,1]      [0,0,1] --> [1,0,0]\n     * [1,1,1] -->  [1,1,2]     [1,1,2]\n     * [1,0,1]      [2,0,3]     [2,0,3]\n     * - At row=0, col=0,\n     *      --> we know there is only 1 consecutive \'1\'s vertically from the top\n     *      --> there is a submatrix/rectangle of (height=1)*(width=1)=1\n     * - At row=0, col=1 & col=2\n     *      --> we know there are 0 consecutive \'1\' vertically from the top\n     *      --> there are submatrix/rectangle of (height=0)*(width=2,3)=0 for both\n     *\n     *                           Row 1:\n     * [0,0,1]      [0,0,1]     [0,0,1]\n     * [1,1,1] -->  [1,1,2] --> [2,1,1]\n     * [1,0,1]      [2,0,3]     [2,0,3]\n     * - At row=1, col=0\n     *      --> we know there are 2 consecutive \'1\'s vertically from the top\n     *      --> there is a submatrix/rectangle of (height=2)*(width=1)=2\n     * - At row=1, col=0\n     *      --> we know there is only 1 consecutive \'1\'s vertically from the top\n     *      --> there is a submatrix/rectangle of (height=1)*(width=2)=2\n     * - At row=1, col=1,\n     *      --> we know there is only 1 consecutive \'1\'s vertically from the top\n     *      --> there is a submatrix/rectangle of (height=1)*(width=3)=3\n     *\n     */
[]