LeetCode Entry

1727. Largest Submatrix With Rearrangements

26.11.2023 medium 2023 kotlin

Max area of 1 submatrix after sorting columns optimally

1727. Largest Submatrix With Rearrangements medium blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/417

Problem TLDR

Max area of 1 submatrix after sorting columns optimally

Intuition

Use hint :( Ok, if we store the heights of the columns we can analyze each row independently, by choosing the largest heights first. The area will be height * width, where width will be the current position: image.png

image.png

Approach

We can reuse the matrix, but don’t do this in a production code without a warning.

Complexity

  • Time complexity: \(O(nmlog(m))\)

  • Space complexity: \(O(1)\)

Code


  fun largestSubmatrix(matrix: Array<IntArray>): Int {
    for (y in 1..<matrix.size)
      for (x in 0..<matrix[y].size)
        if (matrix[y][x] > 0)
          matrix[y][x] += matrix[y - 1][x]
    var max = 0
    for (row in matrix) {
      row.sort()
      for (x in row.lastIndex downTo 0)
        max = max(max, row[x] * (row.size - x))
    }
    return max
  }