For example, given (1, 1, 4, 3) and (3, 2, 4, 5), you should return (3, 2, 2, 2),

For example, given (1, 1, 4, 3) and (1, 5, 1, 1), you should return nil.

Hints:

- How can you describe a rectangle,

- The most right "left coordinate" has to be lesser than the most left "right coordinate",

- The most top "bottom coordinate" has to be lesser than the most bottom "top coordinate".

Solution:

// 1.
struct Rectangle: CustomStringConvertible {
    let leftX: Int
    let bottomY: Int
    let width: Int
    let height: Int

    var description: String {
        return "(\(leftX), \(bottomY), \(width), \(height))"
    }

    var topY: Int {
        return bottomY + height
    }

    var rightX: Int {
        return leftX + width
    }
}

func getIntersection(rect1: Rectangle, rect2: Rectangle) -> Rectangle? {
    // 2.
    let maxLeftX = max(rect1.leftX, rect2.leftX)
    let maxBottomY = max(rect1.bottomY, rect2.bottomY)
    let minTopY = min(rect1.topY, rect2.topY)
    let minRightX = min(rect1.rightX, rect2.rightX)

    if maxLeftX < minRightX && maxBottomY < minTopY {
        // 3.
        return Rectangle(leftX: maxLeftX,
                         bottomY: maxBottomY,
                         width: minRightX - maxLeftX,
                         height: minTopY - maxBottomY)
    } else {
        // 4.
        return nil
    }
}

Explanations:

1. Let's define how to represent a rectangle (leftX, bottomY, width, height), or you could use a CGRect instead.

struct Rectangle: CustomStringConvertible {
  let leftX: Int
  let bottomY: Int
  let width: Int
  let height: Int

2. Let's define common points (maxLeftX, maxBottomY, minTopY, minRightX).

let maxLeftX = max(rect1.leftX, rect2.leftX)
let maxBottomY = max(rect1.bottomY, rect2.bottomY)
let minTopY = min(rect1.topY, rect2.topY)
let minRightX = min(rect1.rightX, rect2.rightX)

3. If the common points make a valid rectangle (the bottom lower than the top and the left lower than the right), return it.

if maxLeftX < minRightX && maxBottomY < minTopY {
  return Rectangle(leftX: maxLeftX,
                   bottomY: maxBottomY,
                   width: minRightX - maxLeftX,
                   height: minTopY - maxBottomY)

4. Otherwise, return nil.

} else {
  return nil
}

Complexity:

Time Complexity: The time complexity is constant O(1),

Space Complexity: The space complexity is constant O(1).

Test-cases:

public func testGetIntersection() {
  let rect1 = Rectangle(leftX: 1, bottomY: 1, width: 4, height: 3)
  let rect2 = Rectangle(leftX: 3, bottomY: 2, width: 4, height: 5)
  let rect3 = Rectangle(leftX: 1, bottomY: 5, width: 1, height: 1)
  assert(getIntersection(rect1: rect1, rect2: rect2)?.description == "(3, 2, 2, 2)", "getIntersection (3, 2, 2, 2) not equal")
  assert(getIntersection(rect1: rect1, rect2: rect3) == nil, "getIntersection nil not equal")
}

Follow-up:

No follow-up question.

<< More Interview Questions | Data Structures and Algorythms >>