We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I started out thinking I could simply go through each good cell and compute the biggest plus I could make with that cell as its center. While doing this, I tracked the largest two areas seen, then finally returned the product of those two values.
This doesn't work for two reasons:
We cannot count two pluses if they have overlapping cells
We have to consider not only the LARGEST plus you can make from a given center, but any possible smaller sized plus.
The second case might happen if you have a 9-area plus and a 13-area plus that overlap. But inside the 13-area plus is a smaller 9-area plus that doesn't overlap with the other 9-area plus. Those two pluses might turn out to be the two largest ones in the grid.
So the approach looks more like this:
Create a pluses array to hold all of the pluses you find.
For each good cell, try to make pluses of size 1, 5, 9, 13, 17, ... etc. using that cell as the center. Each time you find a plus, copy its cell coordinates into a set and save that set in pluses.
You now have a large array of pluses, each one represented as a set of coordinates.
Set a value for the maximum product found so far to zero.
Iterate through every possible pair of pluses. If the product of their lengths is greater than the maximum found so far, check if the pluses are overlapping. (In Python, you can check if two sets overlap by finding their intersection; if they overlap, len(set1 & set2) > 0.) If they don't overlap, update the maximum product found so far.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Ema's Supercomputer
You are viewing a single comment's thread. Return to all comments →
I started out thinking I could simply go through each good cell and compute the biggest plus I could make with that cell as its center. While doing this, I tracked the largest two areas seen, then finally returned the product of those two values.
This doesn't work for two reasons:
The second case might happen if you have a 9-area plus and a 13-area plus that overlap. But inside the 13-area plus is a smaller 9-area plus that doesn't overlap with the other 9-area plus. Those two pluses might turn out to be the two largest ones in the grid.
So the approach looks more like this:
pluses
array to hold all of the pluses you find.pluses
.len(set1 & set2) > 0
.) If they don't overlap, update the maximum product found so far.