Scenario:
On a checkerboard of size MxN, there are red and green pieces.
Each square on the board may contain any number of pieces, of any color. (We can have 5 pieces - 3 green and 2 red in the same square, or for e.g. green green, or red red, or whatever number)
I'm looking for an axis-aligned rectangle on the board with as many green pieces as possible.
However, the rectangle may not contain more than a given number of red pieces.
One corner of the rectangle must be (0,0).
Example:
Board size is 6x4, red pieces are marked "x", green pieces are marked "o".
+-+-+-+-+-+-+ 3 | | | |o|x|o| +-+-+-+-+-+-+ 2 |o| |x| | |o| +-+-+-+-+-+-+ 1 |o| |o| |o|x| +-+-+-+-+-+-+ 0 | |o| |x| |x| +-+-+-+-+-+-+ 0 1 2 3 4 5
If we allow 2 red pieces, then (4,2) is an optimal solution, because the area between (0,0) and (4,2) contains 5 green pieces and 2 red pieces. No point with up to 2 red pieces contains more than 5 green pieces. (3,3) is also an optimal solution.
If we allow 3 red pieces, then (4,3) is the only optimal solution, with 6 green pieces.
I'm given:
- the board size,
- the coordinates of all green and red pieces,
- the number of allowed red pieces ("maxRed")
Goal: For any given "maxRed", the class should be able to calculate coordinates (x,y) such that the axis-aligned rectangle between (0,0) and (x,y) contains at most "maxRed" red pieces, and the number of green pieces is maximal.
My Question:
Solving this by traversing all the possible matrices (in order to find the largest triangle) with maximum green points and the given maximum red points is clearly inefficient, I'm trying to find a way to find that without using brute-force.
Some intuition:
I thought looking at the closet maximum red points that are allowed to be in the rectangle (if maxRed = 2, then closest two red points) from the origin (0,0)
, and then checking all the possible 'extensions' of the rectangle from that points (just width, just height, width & height, and so on..) which is also not so efficient I believe (in worst case scenario it's inefficient).
Then I thought maybe if maxRed equals to 2 and we found the closest two red points, then we can check where is the 3rd maxRed (if it doesn't exist the return the whole matrix as rectangle), and somehow search 'less' the number of options - still need to think of all the cases (the 3rd point can be on top that current rectangle, or from the left of it, or in diagonal) and if it's from e.g. the top of it, then there may be a case that I can extend it in width - and maybe not (because maybe there's another red points from the right of it). but you get the idea, somehow find an algorithm which isn't brute-force and as efficient as possible.
Question 2: Also another interesting question I'd like to know how to approach: How would you solve the problem if the coordinates were defined as "float", meaning that the board has no grid on it. Now you are required to return the best floating point (x,y) coordinates, such that the area between (0,0) and (x,y) contains at most "maxRed" red pieces and the number of green pieces is maximal. How would you find it, and what would the complexity be?
Another in-depth intuition:
Edge cases: if redpoints in the map are less than 2, return rectangle of all the matrix.
Then, We start by creating our rectangle cover the closet two red points. (for e.g. our rectangle will extend to y = 3, and x = 2) cover all that area.
Then we check what's the closet y axis of our red points which is bigger than our current rectangle's y (which is y=3), and what's the closet x axis of our red points which is bigger than our current rectangle's x (which is x=2), the closet x and y can also come from the same 3rd red point, it doesn't have to be from two different red points.
In that way we can see 'how far' we can extend our rectangle.
Then, in step 3, we will try iteratively go up (i+1) if possible, and check all the extensions of j, then go i+2 and check all the j..
4.1 then go right (j+1) if possible of course, and check all the i, then keep going j+2, and so on..
and return the highest rectangle we could build - and we won't check too many i, and j's in the process.
But that's not enough,
because there's an edge case like in the 'Case 2'
which there there're 2 red points in the same spot, so we will have to carefully check if the second farthest red point (it's farther if it's x or y or both are bigger than the first closet red point obviously) has another red point in it, if it does have in total two red points in the same cell, then we extend until its x or y - and from there keep extending up/down.
(we can see if its in diagonal or just from the right or just from the top) if it's from the right of the first red point (meaning x is bigger than our current x - only in x axis) then we can check how far we can extend top - by looking at the list of red points if we have on top of us red points, if not then we extend till the end immediately, and same approach if the 2nd red point in on top of us, we can check how far to extend to the right.
and if the 2nd red point is in diagonal of us (like in the usage example) then we check how far we can extend to the left only, and how far we can extend to top only, and see what's better for us in regard of searching for more green points.
This solution should work I guess, and give about O(1) Time complexity I guess.