algorithm/List/dynamic_array_largest_submatrix.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[문제]  \n",
    "#array #greedy #sorting #matrix  \n",
    "![algorithm-problem.png](../../img/algorithm-231126-01.png)  \n",
    "link: https://leetcode.com/problems/largest-submatrix-with-rearrangements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "풀이"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "\n",
    "        # Calculate heights for each column\n",
    "        for i in range(1, row):\n",
    "            for j in range(col):\n",
    "                if matrix[i][j] == 1:\n",
    "                    matrix[i][j] += matrix[i - 1][j]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(row):\n",
    "            # Sort the heights in ascending order\n",
    "            matrix[i].sort()\n",
    "\n",
    "            # Iterate through the sorted heights\n",
    "            for j in range(col):\n",
    "                height = matrix[i][j]\n",
    "                width = col - j\n",
    "                res = max(res, height * width)\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}