Created
May 25, 2017 23:52
-
-
Save kaizokuace/0de74763626861ce791a9b1d57de6a1d to your computer and use it in GitHub Desktop.
Find largest rectangle in metrix of 1 and 0
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| let matrix = [ | |
| [0,0,0,0,0,0,0,0,0,0], | |
| [0,1,1,0,0,0,0,0,0,0], | |
| [0,1,1,0,0,0,0,0,0,0], | |
| [0,1,1,0,0,0,0,0,0,0], | |
| [0,1,1,0,0,0,0,0,0,0], | |
| [0,1,1,0,1,1,1,1,0,0], | |
| [0,1,1,0,1,1,1,1,0,0], | |
| [0,1,1,0,1,1,1,1,0,0], | |
| [0,0,0,0,0,0,0,0,0,0], | |
| [0,0,0,0,0,0,0,0,0,0] | |
| ]; | |
| function findLargestRect(matrix) { | |
| // build output matrix | |
| let out = matrix.map((row, i) => { | |
| return row.map((item, j) => { | |
| if (i > 0) { | |
| if (item == 1){ | |
| matrix[i][j] = matrix[i-1][j] + 1 | |
| return matrix[i][j] | |
| } | |
| else | |
| return item | |
| } | |
| else | |
| return item | |
| }) | |
| }); | |
| // size each row | |
| let sizes = out.map((row, i) => { | |
| let max = Math.max(...row) | |
| return row.reduce((a, b) => b == max ? a + b : a, 0) | |
| }) | |
| // maxRow is also the y2 coordinate | |
| let maxRow = sizes.indexOf(Math.max(...sizes)); | |
| // max value in max row, this is also the height of rect | |
| let max = Math.max(...out[maxRow]); | |
| let {maxLength, endIndex} = longestStreak(out[maxRow], max); | |
| return getRect(maxLength, max, endIndex, maxRow); | |
| } | |
| function longestStreak(arr, number){ | |
| let maxLength = 0, curLength = 0, endIndex = 0 | |
| arr.forEach((item, i) => { | |
| if (item == number) { | |
| curLength++ | |
| if (curLength > maxLength) | |
| maxLength = curLength | |
| if (item != number) | |
| curLength = 0 | |
| endIndex = i | |
| } | |
| }) | |
| return {maxLength, endIndex} | |
| } | |
| function getRect(width, height, x2, y2) { | |
| let x1 = x2 - width + 1; | |
| let y1 = y2 - height + 1; | |
| return {x1, y1, x2, y2} | |
| } | |
| let rect = findLargestRect(matrix); | |
| console.log(rect); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment