Rectangle Overlap

🏠 ⬅️ ➡️

An axis-aligned rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) is the coordinate of its bottom-left corner, and (x2, y2) is the coordinate of its top-right corner. Its top and bottom edges are parallel to the X-axis, and its left and right edges are parallel to the Y-axis.

Two rectangles overlap if the area of their intersection is positive. To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two axis-aligned rectangles rec1 and rec2, return true if they overlap, otherwise return false.

Example 1:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3] Output: true

Example 2:

Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1] Output: false

Example 3:

Input: rec1 = [0,0,1,1], rec2 = [2,2,3,3] Output: false

Constraints:

  • rec1.length == 4
  • rec2.length == 4
  • -109 <= rec1[i], rec2[i] <= 109
  • rec1 and rec2 represent a valid rectangle with a non-zero area.
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
✅ Correct 
program main
    implicit none

    integer :: i, j, k
    logical :: overlap
    real, dimension(4) :: rec1, rec2

    ! Example 1:
    rec1 = [0, 0, 2, 2]
    rec2 = [1, 1, 3, 3]
    overlap = overlap_rectangles(rec1, rec2)
    print '(L1)', overlap

    ! Example 2:
    rec1 = [0, 0, 1, 1]
    rec2 = [1, 0, 2, 1]
    overlap = overlap_rectangles(rec1, rec2)
    print '(L1)', overlap

    ! Example 3:
    rec1 = [0, 0, 1, 1]
    rec2 = [2, 2, 3, 3]
    overlap = overlap_rectangles(rec1, rec2)
    print '(L1)', overlap

contains

    function overlap_rectangles(rec1, rec2) result(overlap)
        implicit none
        real, intent(in) :: rec1(4), rec2(4)
        logical :: overlap
        real :: xmin1, xmax1, ymin1, ymax1, xmin2, xmax2, ymin2, ymax2

        xmin1 = min(rec1(1), rec1(3))
        xmax1 = max(rec1(1), rec1(3))
        ymin1 = min(rec1(2), rec1(4))
        ymax1 = max(rec1(2), rec1(4))
        xmin2 = min(rec2(1), rec2(3))
        xmax2 = max(rec2(1), rec2(3))
        ymin2 = min(rec2(2), rec2(4))
        ymax2 = max(rec2(2), rec2(4))

        overlap = (xmin1 < xmax2 .and. xmax1 > xmin2 .and. &
                   ymin1 < ymax2 .and. ymax1 > ymin2)
    end function overlap_rectangles
end program main
❌ Compiled
❌ Executed
❌ Correct 
module overlap_rectangles
implicit none
contains

function overlap(rec1, rec2) result(overlap)
integer, intent(in) :: rec1(4), rec2(4)
logical :: overlap

! Calculate the intersection area
! If the intersection area is positive, then the rectangles overlap
overlap = (max(rec1(1), rec2(1)) <= min(rec1(3), rec2(3))) .and. &
          (max(rec1(2), rec2(2)) <= min(rec1(4), rec2(4)))

end function overlap

end module overlap_rectangles

program main
use overlap_rectangles
implicit none

! Test cases
integer, parameter :: n_test_cases = 3
integer, parameter :: rec1(4) = [0, 0, 2, 2]
integer, parameter :: rec2(4) = [1, 1, 3, 3]
integer, parameter :: rec3(4) = [0, 0, 1, 1]
integer, parameter :: rec4(4) = [1, 0, 2, 1]
integer, parameter :: rec5(4) = [2, 2, 3, 3]

! Output
logical :: overlap

! Test case 1
overlap = overlap(rec1, rec2)
if (overlap) then
    print *, "Test case 1: True"
else
    print *, "Test case 1: False"
end if

! Test case 2
overlap = overlap(rec3, rec4)
if (overlap) then
    print *, "Test case 2: True"
else
    print *, "Test case 2: False"
end if

! Test case 3
overlap = overlap(rec3, rec5)
if (overlap) then
    print *, "Test case 3: True"
else
    print *, "Test case 3: False"
end if

end program main
🌐 Data from online sources 
def racecar(target: int) -> int:
    memo = {}

    def dp(pos: int, speed: int) -> int:
        if pos == target:
            return 0
        if abs(pos) > 2 * target:
            return float('inf')

        key = (pos, speed)
        if key in memo:
            return memo[key]

        op1 = dp(pos + speed, speed * 2) + 1
        op2 = dp(pos, -speed) + 2

        ans = min(op1, op2)
        memo[key] = ans
        return ans

    return dp(0, 1)

The algorithm for solving this problem consists of a dynamic programming approach. We define a helper function called dp that receives the current position, speed, target and memoization Map.

  1. Starting from position 0 and speed 1, we use the DP function that uses memoization to find the shortest sequence of instructions.
  2. If the current position is equal to the target position, return 0 as no additional operations are needed.
  3. If the absolute value of the current position exceeds twice the target position, we return a large number as the cost of the current path.
  4. We check two operations at each recursive call: accelerating (moving with the current speed) and reversing (changing the sign of the speed). We calculate the cost for each operation, adding 1 for acceleration and 2 for reversing.
  5. We return the minimum cost from these operations and memoize this minimum cost for the current position and speed.
  6. Finally, the algorithm will return the shortest sequence of instructions to reach the target position by adding 1 outside of the DP function.
🌐 Data from online sources 
int racecar(int target) {
    unordered_map<int, unordered_map<int, int>> memo;
    function<int(int, int)> dp = [&](int pos, int speed) {
        if (pos == target) return 0;
        if (abs(pos) > 2 * target) return INT_MAX;

        int &ans = memo[pos][speed];
        if (ans) return ans;

        if (speed == -1) {
            int op1 = dp(pos + speed, 2 * speed) + 1;
            int op2 = dp(pos, -speed) + 2;

            ans = min(op1, op2);
        } else {
            int op1 = dp(pos - speed, -2 * speed) + 1;
            int op2 = dp(pos, -speed) + 2;

            ans = min(op1, op2);
        }

        return ans;
    };

    return dp(0, target) + 1;
}

The algorithm for solving this problem consists of a dynamic programming approach. We define a helper function called dp that receives the current position, speed, target and memoization Map.

  1. Starting from position 0 and speed 1, we use the DP function that uses memoization to find the shortest sequence of instructions.
  2. If the current position is equal to the target position, return 0 as no additional operations are needed.
  3. If the absolute value of the current position exceeds twice the target position, we return a large number as the cost of the current path.
  4. We check two operations at each recursive call: accelerating (moving with the current speed) and reversing (changing the sign of the speed). We calculate the cost for each operation, adding 1 for acceleration and 2 for reversing.
  5. We return the minimum cost from these operations and memoize this minimum cost for the current position and speed.
  6. Finally, the algorithm will return the shortest sequence of instructions to reach the target position by adding 1 outside of the DP function.