generated from threeal/project-starter
-
Notifications
You must be signed in to change notification settings - Fork 1
/
solution.cpp
65 lines (60 loc) · 1.75 KB
/
solution.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// We will do a brute force search here to find the maximum area of the submatrix.
// But before that, we need to adjust each element of the matrix so it contains
// 1 + the number of the above elements whose value is 1.
//
// Given the example input:
//
// [ 0 0 1 ]
// [ 1 1 1 ]
// [ 1 0 1 ]
//
// We will adjust it to be:
//
// [ 0 0 1 ]
// [ 1 1 2 ]
// [ 2 0 3 ]
//
// And then we can just iterate each row to find the maximum area.
// To calculate each row, we can sort the row first from highest to lowest
// and then calculate the area by multiplying the element value with the element index + 1.
//
// Given the second row of the adjusted example matrix:
//
// [ 1 2 2 ]
//
// We can sort it to be:
//
// [ 2 2 1 ]
//
// And we can just choose the largest area as follows:
//
// 2 * 1 = 2
// 2 * 2 = 4 (largest)
// 1 * 3 = 3
#include <algorithm>
#include <vector>
class Solution {
public:
int largestSubmatrix(std::vector<std::vector<int>>& matrix) {
// Adjust each element of the matrix so it contains
// 1 + the number of the above elements whose value is 1.
for (std::size_t y = 1; y < matrix.size(); ++y) {
for (std::size_t x = 0; x < matrix[y].size(); ++x) {
if (matrix[y][x] == 0) continue;
matrix[y][x] = matrix[y - 1][x] + 1;
}
}
// Do brute force search here to calculate the maximum area.
int maxArea = 0;
for (auto& rows : matrix) {
// Sort values in the row from highest to lowest.
sort(rows.begin(), rows.end(), std::greater<int>());
// Find the largest area from values in the row.
for (std::size_t i = 0; i < rows.size(); ++i) {
if (rows[i] == 0) break;
maxArea = std::max<int>(maxArea, (i + 1) * rows[i]);
}
}
return maxArea;
}
};