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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
//
// Challenge
//
// You are given matrix m x n with 0 and 1.
//
// Write a script to find the largest rectangle containing only 1.
// Print 0 if none found.
//
//
// For notes, see the perl solution: ../perl/ch-1.pl
//
//
// A naive implementation would be a for each pair of points see whether
// there's a rectangle with 1s, with the pair of points opposite vertices
// of the array.
//
// If done correctly, that leads to an Omega (l^2 * m^2) algorithm,
// if the size of the input is an l x m matrix. So, Omega (N^2)
// where N = l * m.
//
// But we can do better. We can use an algorithm which runs in
// O (l * m * min (l, m)) time, or O (N sqrt (N)) time, since
// min (l, m) <= sqrt (N).
//
// Assume the matrix is not wider than it is high (otherwise, first
// transpose the matrix -- which can be done in O (l * m) time).
//
// First, we replace every 1 in the matrix with how many 1's (including
// the 1 in the current position) it takes the hit the first 0 below it.
// We can do this in a single pass, working bottom to top.
//
// So, the matrix
//
// 0 1 0 1 1
// 0 1 0 1 1
// 0 1 1 1 1
// 1 0 0 1 1
// 0 0 0 1 1
// 0 0 1 0 0
//
// becomes
//
// 0 3 0 5 5
// 0 2 0 4 4
// 0 1 1 3 3
// 1 0 0 2 2
// 0 0 0 1 1
// 0 0 1 0 0
//
// Then, for each cell (x, y) in the matrix, we scan to the right (in the
// y direction), until we hit a zero (or the end of the row). For each
// cell (x, y + k) in the scan, we keep track of the minimum value in
// points (x, y + m), 0 <= m <= k, as calculated in the step above.
// Let this value be p. Then the maximum sized rectangle we can make
// with the points (x, y) and (x, y + k) as (top) vertices of that
// rectangle is (k + 1) x p.
//
//
// Read STDIN. Split on newlines, then on whitespace, and turn the results
// into numbers.
//
let matrix = require ("fs")
. readFileSync (0) // Read all.
. toString () // Turn it into a string.
. split ("\n") // Split on newlines.
. filter (_ => _ . length) // Filter empty lines.
. map (_ => _ . split (" ") // Split lines on spaces
. map (_ => +_)) // Numify.
;
//
// Check whether all rows are the same size
//
for (let x = 1; x < matrix . length; x ++) {
if (matrix [x] . length != matrix [0] . length) {
process . stderr . write ("Not all rows are equal!\n");
process . exit (1);
}
}
let X = matrix . length;
let Y = matrix [0] . length;
//
// Transpose if the matrix is wider than it is high.
//
let transposed = 0;
if (X < Y) {
matrix = matrix [0] . map ((col, i) => matrix . map (row => row [i]));
[X, Y] = [Y, X];
transposed = 1;
}
//
// Maps the 1s in the matrix to the number of consecutive 1s below
// it (including this 1 itself).
//
for (let x = X - 2; x >= 0; x --) {
for (let y = 0; y < Y; y ++) {
matrix [x] [y] = matrix [x] [y] *
(matrix [x + 1] [y] + 1);
}
}
//
// Iterate over all element of the matrix. For each element which
// isn't 0, scan to the right, keeping track of minimum sequence
// downward. For each point in the scan, find the largest rectangle
// which can be made with these points as corner points.
//
// Remember the best one found.
//
let best = [0, 0];
for (let x = 0; x < X; x ++) {
for (let y = 0; y < Y; y ++) {
if (matrix [x] [y] == 0) {
continue;
}
let min_depth = matrix [x] [y];
if (min_depth > best [0] * best [1]) {
best = [min_depth, 1];
}
for (w = 1; y + w < Y &&
matrix [x] [y + w] > 0; w ++) {
if (matrix [x] [y + w] < min_depth) {
min_depth = matrix [x] [y + w];
}
if (min_depth * (w + 1) > best [0] * best [1]) {
best = [min_depth, w + 1];
}
}
}
}
//
// Print solution.
//
let output = "0";
if (best [0] * best [1] > 1) {
if (transposed) {
best = [best [1], best [0]];
}
let row = [... Array (best [1]) . keys ()] . map (_ => 1) . join (" ");
output = [... Array (best [0]) . keys ()] . map (_ => row) . join ("\n");
}
console . log (output);
|
