TheRealSamuel/LeetCodeProblem
0572
1{2 "id": 2818,3 "name": "maximum_strictly_increasing_cells_in_a_matrix",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/maximum-strictly-increasing-cells-in-a-matrix/",6 "date": "2023-05-21 00:00:00",7 "task_description": "Given a **1-indexed** `m x n` integer matrix `mat`, you can select any cell in the matrix as your **starting cell**. From the starting cell, you can move to any other cell **in the** **same row or column**, but only if the value of the destination cell is **strictly greater** than the value of the current cell. You can repeat this process as many times as possible, moving from cell to cell until you can no longer make any moves. Your task is to find the **maximum number of cells** that you can visit in the matrix by starting from some cell. Return _an integer denoting the maximum number of cells that can be visited._ **Example 1:** **** ``` **Input:** mat = [[3,1],[3,4]] **Output:** 2 **Explanation:** The image shows how we can visit 2 cells starting from row 1, column 2. It can be shown that we cannot visit more than 2 cells no matter where we start from, so the answer is 2. ``` **Example 2:** **** ``` **Input:** mat = [[1,1],[1,1]] **Output:** 1 **Explanation:** Since the cells must be strictly increasing, we can only visit one cell in this example. ``` **Example 3:** **** ``` **Input:** mat = [[3,1,6],[-9,5,7]] **Output:** 4 **Explanation:** The image above shows how we can visit 4 cells starting from row 2, column 1. It can be shown that we cannot visit more than 4 cells no matter where we start from, so the answer is 4. ``` **Constraints:** `m == mat.length ` `n == mat[i].length ` `1 <= m, n <= 105` `1 <= m * n <= 105` `-105 <= mat[i][j] <= 105`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "mat = [[3,1],[3,4]]",12 "output": "2 "13 },14 {15 "label": "Example 2",16 "input": "mat = [[1,1],[1,1]]",17 "output": "1 "18 },19 {20 "label": "Example 3",21 "input": "mat = [[3,1,6],[-9,5,7]]",22 "output": "4 "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 [29 48839,30 88852,31 -86671,32 79614,33 -63546,34 -50554,35 -82424,36 -81373,37 -76118,38 -68724,39 -54955,40 -35152,41 -15865,42 -50075,43 -45436,44 46470,45 -47319,46 585,47 9438,48 95290,49 99522,50 16649,51 -80846,52 -18749,53 8054,54 -40617,55 -59344,56 77423,57 54752,58 -13795,59 -84166,60 -90840,61 86742,62 74863,63 63187,64 -14283,65 -11977,66 97546,67 84110,68 93403,69 -44677,70 -52628,71 -30616,72 571,73 -17847,74 79351,75 28299,76 71517,77 4085,78 2764,79 -40097,80 -68105,81 -81956,82 24902,83 -7489,84 -11859,85 11021,86 33210,87 -48217,88 42858,89 -48875,90 99017,91 -67902,92 90569,93 -93753,94 2865,95 -31067,96 4652,97 -38948,98 92876,99 -42215,100 -52133,101 22762,102 33139,103 89537,104 -50268,105 -59521,106 -55963,107 14505,108 77165,109 30122,110 -67819,111 30071,112 -86685,113 -47934,114 13454,115 93599,116 94935,117 -93161,118 -38710,119 -61769,120 95106,121 67109,122 -89516,123 10555,124 85968,125 63478,126 481127 ],128 [129 63380,130 -78343,131 -62747,132 51154,133 -84907,134 92995,135 39195,136 5018,137 9722,138 89549,139 -25288,140 -64389,141 54944,142 56998,143 69174,144 64251,145 85835,146 15375,147 -35241,148 77439,149 -57316,150 -89949,151 80141,152 -76610,153 -27078,154 -2976,155 -8289,156 69601,157 -92334,158 -3857,159 24149,160 -64475,161 79000,162 -67612,163 19165,164 -625,165 -16784,166 -98257,167 70527,168 3972,169 -8114,170 50759,171 59806,172 -16962,173 -55636,174 46964,175 9593,176 -62965,177 -19372,178 -90913,179 91647,180 -20252,181 51767,182 -88731,183 -97195,184 -67421,185 3213,186 22522,187 -88177,188 -45077,189 -93946,190 -26547,191 59528,192 80796,193 -45439,194 -45196,195 31840,196 96959,197 91843,198 -89524,199 -38741,200 39878,201 -44070,202 86018,203 -25515,204 69753,205 -89372,206 -20890,207 -64377,208 77014,209 -34835,210 93232,211 -75841,212 -86973,213 -99963,214 8247,215 -3702,216 79992,217 51866,218 -25564,219 -35221,220 41904,221 -50183,222 -11266,223 46988,224 66817,225 -80190,226 88394227 ],228 [229 -15386,230 28155,231 7013,232 -68066,233 -86485,234 87667,235 44092,236 24964,237 -43280,238 45077,239 -82715,240 -30144,241 90411,242 -23108,243 -74863,244 -98167,245 13182,246 -6805,247 -72722,248 69984,249 21573,250 71658,251 10546,252 53898,253 -96339,254 -84000,255 -30000,256 38770,257 -1886,258 -6899,259 65528,260 11262,261 8035,262 63544,263 35321,264 98011,265 18301,266 -30739,267 58143,268 -19790,269 -56902,270 94662,271 -35887,272 46661,273 83889,274 -79333,275 -77494,276 20654,277 16593,278 97813,279 62979,280 -22076,281 23243,282 61591,283 -43150,284 -748,285 94892,286 -18859,287 86735,288 -52388,289 48442,290 41346,291 -55240,292 -76224,293 -59624,294 99476,295 -42568,296 82512,297 -60174,298 -36850,299 -13438,300 -65356,301 -41325,302 37832,303 -33946,304 8056,305 62897,306 86876,307 -58067,308 -26870,309 -32232,310 -35722,311 51621,312 58332,313 -78341,314 -15033,315 -34929,316 83170,317 -78263,318 74241,319 -11979,320 -55704,321 42700,322 -33488,323 -14146,324 66350,325 78985,326 6618327 ],328 [329 97084,330 39908,331 40554,332 -9811,333 83127,334 -48825,335 -313,336 -59881,337 -70624,338 82532,339 -72032,340 88885,341 -15361,342 88932,343 29151,344 -91277,345 -25797,346 62352,347 33036,348 -7408,349 -58310,350 35317,351 43065,352 -95427,353 -11451,354 -57370,355 87663,356 64241,357 -13387,358 -22328,359 47449,360 17058,361 83057,362 -97016,363 27121,364 22666,365 15820,366 -17679,367 74491,368 84663,369 -87941,370 46918,371 39858,372 -86962,373 -20803,374 -70182,375 16047,376 62322,377 -49373,378 31796,379 13386,380 51801,381 49019,382 -47231,383 13870,384 57704,385 22239,386 10084,387 67158,388 -60839,389 -21304,390 -50038,391 21856,392 57248,393 -66599,394 -55368,395 -17762,396 -65048,397 -79965,398 19824,399 -38150,400 15628,401 -75549,402 -31698,403 24044,404 -27170,405 -4565,406 -97525,407 44698,408 -76928,409 -33207,410 -16061,411 46654,412 90140,413 70463,414 58399,415 -76591,416 94527,417 82680,418 27067,419 19791,420 55214,421 -66387,422 20514,423 34039,424 14718,425 -29437,426 83913427 ],428 [429 -55687,430 24854,431 -92902,432 77734,433 20806,434 31904,435 -30013,436 29293,437 -76168,438 94313,439 97301,440 61011,441 -47271,442 -32912,443 -44059,444 -9801,445 62954,446 -74393,447 84515,448 -51194,449 -18493,450 42072,451 -91478,452 -28303,453 -76493,454 -62027,455 55301,456 -74053,457 23107,458 -63998,459 87908,460 97495,461 21175,462 -90869,463 -8172,464 -27124,465 -51439,466 94354,467 71399,468 55613,469 83400,470 -41349,471 -44091,472 80266,473 -19065,474 -47188,475 2140,476 -98136,477 -87284,478 -29574,479 -42541,480 13436,481 -83210,482 75007,483 88481,484 -99473,485 76861,486 63516,487 -8152,488 73161,489 -32005,490 -68105,491 -51078,492 33817,493 -71856,494 -98429,495 13363,496 -39590,497 17230,498 -10222,499 -926,500 -6301,501 -34849,502 72653,503 26531,504 94982,505 45629,506 -70960,507 -53182,508 -98657,509 -89914,510 49682,511 -978,512 88384,513 9720,514 72390,515 -36819,516 53736,517 -25043,518 -2621,519 50329,520 -40751,521 -70556,522 -10651,523 -73178,524 -8633,525 -29713,526 -10048527 ],528 [529 -31424,530 99295,531 -28649,532 90091,533 34277,534 -94546,535 81023,536 74065,537 94474,538 -36122,539 76403,540 -65209,541 -68486,542 25480,543 -98349,544 -24476,545 85885,546 32042,547 -71172,548 -33882,549 -70095,550 -49521,551 76494,552 -18204,553 23143,554 -44541,555 53561,556 -76637,557 56511,558 -52063,559 99439,560 69990,561 16501,562 60150,563 16725,564 81170,565 -49532,566 -33610,567 89399,568 23244,569 69995,570 -77305,571 65544,572 -79374,573 -36179,574 67093,575 91374,576 29806,577 10620,578 52838,579 -95470,580 81525,581 -91156,582 22076,583 -93242,584 -40668,585 40124,586 -31712,587 -44051,588 12205,589 91626,590 38077,591 46111,592 760,593 -68796,594 -53698,595 -24805,596 38317,597 67646,598 87959,599 -65946,600 9225,601 -39873,602 99330,603 408,604 -98127,605 -89883,606 -49779,607 31705,608 1869,609 -401,610 47071,611 22546,612 -82416,613 -17396,614 -58274,615 -86407,616 1400,617 46528,618 59760,619 99063,620 -74735,621 46411,622 73410,623 -96746,624 -28793,625 67236,626 67480627 ],628 [629 -14459,630 46567,631 -88039,632 39427,633 93536,634 5823,635 42353,636 41808,637 -81212,638 -77969,639 93148,640 76149,641 -86426,642 -58443,643 94609,644 -33900,645 -28845,646 -42835,647 -76028,648 -45549,649 -68687,650 84659,651 -60181,652 86894,653 89756,654 13710,655 -44463,656 -75560,657 -31387,658 91688,659 -72265,660 28186,661 -44200,662 42125,663 19875,664 -98430,665 13150,666 -9257,667 28435,668 78502,669 16256,670 7691,671 -80087,672 27028,673 98617,674 -33977,675 -14348,676 -2270,677 -83147,678 -66511,679 51207,680 9356,681 -91882,682 28598,683 -22258,684 1550,685 10759,686 -16910,687 -29821,688 -67570,689 -20450,690 -42759,691 -61654,692 -64085,693 11714,694 5121,695 -45716,696 76626,697 -97423,698 52750,699 -90259,700 -71951,701 10489,702 -35372,703 5150,704 523,705 -20299,706 54639,707 -53015,708 -90719,709 61600,710 -80632,711 11826,712 48070,713 -76908,714 -88380,715 -20442,716 23646,717 33846,718 76754,719 64836,720 -48958,721 35249,722 85684,723 -80965,724 -81083,725 55774,726 93289727 ],728 [729 51529,730 22752,731 19177,732 -46709,733 -90332,734 -57129,735 57607,736 82343,737 42552,738 -7137,739 -59530,740 -57953,741 34595,742 1670,743 54858,744 87340,745 99210,746 5239,747 -58733,748 56823,749 95079,750 76273,751 -33314,752 24854,753 -77072,754 -77996,755 -66848,756 -98229,757 -47226,758 -39363,759 6154,760 -1741,761 84977,762 -90969,763 82438,764 -18204,765 58600,766 -52704,767 14989,768 82128,769 -23832,770 -35727,771 83378,772 40990,773 -73289,774 24447,775 96301,776 -63637,777 -61345,778 -2738,779 95898,780 17643,781 57556,782 88727,783 -87491,784 -63042,785 50131,786 -37340,787 20025,788 -97011,789 -66408,790 4656,791 -51362,792 80310,793 -23760,794 -57219,795 -4347,796 52411,797 31488,798 -4840,799 -4163,800 57147,801 -65530,802 -28813,803 -16322,804 21962,805 7100,806 21836,807 43973,808 -81182,809 3,810 32178,811 -6051,812 49129,813 -80294,814 1218,815 7118,816 19470,817 97940,818 27492,819 22741,820 76766,821 -46743,822 33001,823 50646,824 -38640,825 -97858,826 85872827 ],828 [829 -15115,830 -95947,831 -43214,832 -68347,833 -85784,834 -89565,835 69274,836 -9117,837 53718,838 -39121,839 44920,840 18303,841 92001,842 53164,843 -83631,844 -56131,845 79134,846 66130,847 -13393,848 -60592,849 85463,850 -92925,851 -91703,852 59286,853 30392,854 85126,855 -33098,856 32061,857 -92304,858 96369,859 43519,860 80082,861 -4046,862 -12512,863 -15099,864 35129,865 19257,866 27659,867 -29044,868 61594,869 -78190,870 92242,871 4697,872 61571,873 24533,874 25342,875 -86829,876 35221,877 -30502,878 35572,879 10148,880 -74030,881 85347,882 -6908,883 29172,884 -83782,885 -13511,886 -63044,887 -3817,888 -10809,889 -53544,890 -17127,891 -12750,892 -43311,893 -81723,894 99167,895 -29335,896 -47235,897 25698,898 -26611,899 -30717,900 63901,901 -63212,902 -69096,903 -21703,904 31177,905 16096,906 27049,907 7548,908 30489,909 -75777,910 -47432,911 -40298,912 -44565,913 -11898,914 13620,915 52163,916 44261,917 77019,918 -96973,919 14967,920 -68181,921 -59388,922 -66486,923 -4574,924 -36428,925 67502,926 18136927 ],928 [929 85632,930 -2554,931 20457,932 -97823,933 55683,934 59321,935 -80002,936 -7556,937 34240,938 -36722,939 -48249,940 -63964,941 67804,942 44844,943 -67192,944 -68916,945 -41163,946 76258,947 -88944,948 79813,949 27848,950 34018,951 65988,952 -41082,953 88937,954 -39291,955 33835,956 6312,957 21797,958 43319,959 79015,960 82890,961 -45744,962 36417,963 47798,964 43431,965 72447,966 -94366,967 -20302,968 23543,969 -94895,970 18413,971 85232,972 -35676,973 48262,974 35975,975 -25241,976 -40416,977 99722,978 62842,979 -98927,980 -15304,981 -30995,982 59123,983 -89022,984 -11160,985 42482,986 -7550,987 88101,988 -70118,989 30656,990 -21055,991 -94266,992 -15435,993 -50119,994 5396,995 -91707,996 71167,997 32154,998 -60218,999 29412,1000 25930,1001 -83587,1002 46930,1003 42133,1004 -34052,1005 -96696,1006 67830,1007 -74930,1008 38485,1009 89551,1010 71435,1011 -90563,1012 -84901,1013 29951,1014 48897,1015 -25030,1016 14963,1017 36362,1018 85815,1019 11763,1020 -69341,1021 35796,1022 73259,1023 -22693,1024 22633,1025 -61948,1026 305311027 ],1028 [1029 17592,1030 86239,1031 -44097,1032 -75497,1033 21071,1034 -99295,1035 -77345,1036 -56099,1037 18678,1038 34438,1039 13107,1040 49194,1041 -31235,1042 -89181,1043 -54030,1044 55943,1045 -67003,1046 -19330,1047 1199,1048 -27669,1049 -64862,1050 -94053,1051 55487,1052 -2948,1053 48707,1054 -80467,1055 39172,1056 -43237,1057 14548,1058 -28189,1059 85982,1060 11154,1061 -73654,1062 98519,1063 25297,1064 -69330,1065 64001,1066 -8335,1067 48529,1068 -6053,1069 -19629,1070 15802,1071 6953,1072 80151,1073 -12571,1074 65126,1075 -39129,1076 11748,1077 72564,1078 -69528,1079 -39123,1080 307,1081 -63171,1082 98206,1083 8207,1084 -37413,1085 -28955,1086 -79618,1087 -32956,1088 -657,1089 53139,1090 94984,1091 -89516,1092 -7393,1093 -87205,1094 68799,1095 -81053,1096 -47880,1097 24218,1098 -30462,1099 -90668,1100 54217,1101 42001,1102 8517,1103 -65221,1104 67975,1105 74138,1106 33885,1107 47772,1108 -19878,1109 21226,1110 -61591,1111 17860,1112 56623,1113 92194,1114 46983,1115 19918,1116 -5591,1117 11515,1118 -22582,1119 -22637,1120 -97326,1121 90387,1122 -54861,1123 -94308,1124 61896,1125 6782,1126 747361127 ],1128 [1129 -45760,1130 -18691,1131 302,1132 -74325,1133 53089,1134 17077,1135 6302,1136 82661,1137 24908,1138 -99,1139 -29958,1140 -40192,1141 11767,1142 -48322,1143 65208,1144 -32488,1145 -52484,1146 15494,1147 -36319,1148 79015,1149 -85312,1150 71484,1151 25634,1152 79880,1153 29912,1154 63121,1155 88568,1156 -95374,1157 75577,1158 90902,1159 51640,1160 83096,1161 12003,1162 88565,1163 -81081,1164 2618,1165 10747,1166 -48771,1167 97120,1168 14305,1169 71385,1170 99996,1171 49389,1172 -58398,1173 -59086,1174 85748,1175 6675,1176 33301,1177 7749,1178 -60326,1179 -78708,1180 21567,1181 6681,1182 35084,1183 41746,1184 56396,1185 -52364,1186 -4127,1187 91101,1188 84586,1189 25762,1190 61088,1191 37838,1192 -15766,1193 -9192,1194 42345,1195 -55246,1196 -77035,1197 19068,1198 93433,1199 95550,1200 -77334,