2

I have a 2d array of objects, if the object has the property of clicked set to true, then it should be considered as "1" otherwise "0". These are blocks that are selected. I need to check if the selected boxes form a single rectangle. What is the best way to go about this?

0

3 Answers 3

5

High-level:

  • Keep track of the outer-most 1s.
  • Count all the 1s.
  • If the count equals the area encased by the outer-most 1s, we have a rectangle.

Pseudo-code:

left = width + 1
right = 0
top = height + 1
bottom = 0
count = 0

for x = 1 to width
for y = 1 to height
  if grid[x][y] == 1
    left   = min(left  , x)
    right  = max(right , x)
    top    = min(top   , y)
    bottom = max(bottom, y)
    count++

if count > 0 and count == (right-left+1)*(bottom-top+1)
  print "We have a rectangle!"
else
  print "We don't have a rectangle!"
4
  • 1
    use this, it's a lot easier than my solution.
    – flyx
    Apr 12, 2013 at 8:09
  • The beauty of this solution is admirable.
    – Philip
    Apr 12, 2013 at 10:04
  • Please , correct me if I am wrong but should it be min (left, Y) and max (right , Y ) instead of X ?
    – Ram K
    May 15, 2017 at 20:14
  • 1
    @Koba Fixed, thanks. (top and bottom are related to y, not left and right, at least according to the implementation) May 15, 2017 at 20:22
0

You could solve it like that:

  • Search for the first element which is 1
  • walk horizontal to the right, then down, then left, then up
  • if you came back to the origin, you have a rectangle
  • then ensure that all the other elements are 0.

This algorithm is O(n^2) and works if you only allow one rectangle. If you have multiple rectangles it gets complicated..

2
  • 1
    and what if the rectangle has to be filled? Apr 12, 2013 at 8:02
  • @DeanHarber: then use Dukelings algorithm
    – duedl0r
    Apr 12, 2013 at 8:08
0

I'd do something like this (pseudocode):

// your 2d-array / matrix (N is the number of lines, M the number of columns)
m[N][M] = ...

// x coord of top left object containing 1
baseM = -1
baseFound = false
// expected width of rectangle
width = 0
widthLocked = false

// this is set to true after we started recognizing a rectangle and encounter
// a row where the object expected to be 1 in order to extend the rectangle
// is 0.
heightExceeded = false

// loop over matrix
for i = 1 to N: // lines
    // at the beginning of a line, if we already found a base, lock the width
    // (it cannot be larger than the number of 1s in the row of the base)
    if baseFound: widthLocked = true

    for j = 1 to M: // columns
        if m[i][j] == 1:
            if not baseFound:
                baseM = j, baseFound = true
                width = 1
            else:
                if j < baseM:
                    // not in rectangle in negative x direction
                    return false
                if heightExceeded:
                    // not in rectangle in y direction
                    return false
                if widthLocked:
                    // not in rectangle in positive x direction
                    if j - baseM >= width: return false
                 else:
                    width = j - baseM
        elseif baseFound:
            if widthLocked:
                // check if we left the rectangle and memorize it
                if j == baseM: heightExceeded = true
                if not heightExceeded:
                    // check if object in rectangle is 0
                    if j > baseM && j < baseM + width: return false
if baseFound:
    return true
else:
    // what is the expected result if no rectangle has been found?
    return ?

Runs in O(n). Beware of bugs.

Note: Most programming languages have 0-based arrays, so you may need to loop i from 0 to N - 1, same for j.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.