118 — Rectangle Overlap

এই note-টা interview-ঘরানার একটা ক্লাসিক। দুটো আয়তক্ষেত্র (rectangle) পরস্পরকে ছোঁয় কি না — শুনতে সহজ, কিন্তু সরাসরি ভাবতে গেলে case-এর জঙ্গল (একটা বাঁয়ে, ডানে, উপরে, কোণায়...)। আজ শিখব একটা সুন্দর উল্টো-চিন্তার কৌশল — "কখন overlap করে না" জিজ্ঞেস করলে পুরো ব্যাপারটা চারটা সরল শর্তে নেমে আসে। আর ভেতরের সত্যটা আরও মিষ্টি: 2D-র এই প্রশ্ন আসলে দুটো 1D interval overlap।

Source

• Original source: LeetCode — Rectangle Overlap
• Platform: LeetCode — https://leetcode.com/problems/rectangle-overlap/
• Topic: Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
• Difficulty: Medium
• Pattern: interval logic
• Basic idea inherited from: — (স্বাধীন শাখা; এটা cross product নয়, per-axis interval-এর গল্প)

1. Problem in simple words

দুটো axis-aligned rectangle দেওয়া (মানে বাহুগুলো x আর y অক্ষের সমান্তরাল, কাত করা নয়)। প্রতিটা rectangle বোঝানো হয় চারটা সংখ্যায় — (x1, y1, x2, y2), যেখানে (x1, y1) নিচ-বাঁ কোণ আর (x2, y2) উপর-ডান কোণ।

বলতে হবে এই দুটো rectangle overlap করে কি না — মানে এদের সাধারণ একটা এলাকা (positive area) আছে কি না। (শুধু ধার বা কোণ ছুঁলে সেটা overlap ধরব কি না, সেটা সংজ্ঞার ব্যাপার — আমরা LeetCode-এর মতো "positive area লাগবে" ধরব, তাই শুধু ছোঁয়া overlap নয়।)

2. What is the math idea?

মূল idea per-axis interval overlap, আর একটা সুন্দর negation trick।

সরাসরি না ভেবে উল্টো জিজ্ঞেস করি — কখন overlap করে না? একটা rectangle যদি পুরোপুরি অন্যটার বাঁয়ে, বা ডানে, বা উপরে, বা নিচে থাকে:

overlap করে না যদি:
  A.x2 <= B.x1   (A পুরো B-র বাঁয়ে)   OR
  B.x2 <= A.x1   (A পুরো B-র ডানে)    OR
  A.y2 <= B.y1   (A পুরো B-র নিচে)    OR
  B.y2 <= A.y1   (A পুরো B-র উপরে)

overlap করে  =  not (উপরের কোনোটা)

গভীর সত্য: এটা আসলে দুটো 1D interval overlap — x-অক্ষে interval দুটো overlap করে এবং y-অক্ষে interval দুটো overlap করে, তবেই rectangle overlap। 2D প্রশ্ন দুটো স্বাধীন 1D প্রশ্নে ভেঙে গেল।

3. Which basic idea does this inherit from?

এটা এই level-এর একটা স্বাধীন শাখা — cross product/orientation-এর পরিবারে নয় (তাই "inherited from: —")।

এর শিকড় বরং আরও সাধারণ একটা ধারণায়: interval overlap — "দুটো range কি ছেদ করে?" এটা sorting/greedy (Level 8) আর পরে interval scheduling-জাতীয় problem-এ বারবার ফিরবে। এখানে আমরা সেই 1D ধারণাটাকে দুটো অক্ষে আলাদা করে প্রয়োগ করছি। তাই এই problem মনে রাখার আসল মূল্য — "কঠিন 2D-কে স্বাধীন 1D-তে ভাঙো" এই decomposition-চিন্তাটা।

4. Real-life analogy

ভাবো দুটো জানালার পর্দা (rectangular) — তুমি জানতে চাও এরা একে অপরকে ঢেকে দেয় (overlap) কি না।

সরাসরি ভাবতে গেলে অনেক অবস্থা। চালাকি: আলাদা করে ভাবো। প্রথমে শুধু আনুভূমিক দিকে দেখো — পর্দা দুটোর x-পরিসর কি একে অপরকে ছোঁয়, নাকি একটা পুরো বাঁয়ে আরেকটা পুরো ডানে? তারপর শুধু উল্লম্ব দিকে একই প্রশ্ন — y-পরিসর কি ওভারল্যাপ করে? দুই দিকেই "হ্যাঁ ওভারল্যাপ" হলে তবেই পর্দা দুটো সত্যিকারের একটা অংশ একসাথে ঢাকছে। যেকোনো এক দিকে আলাদা থাকলেই — overlap নেই।

5. Visual explanation

overlap তখনই, যখন x-interval আর y-interval দুটোই ছেদ করে:

overlap করে:                 overlap করে না (A পুরো বাঁয়ে):
y                            y
4 +-----+                    4 +---+
  |  A  +--+                   | A |   +---+
3 |  +--+B |     3            3 +---+   | B |
  +--+--+--+--- x               +-------+---+--- x
     x: [1,3]∩[2,4]=[2,3] ✓        x: A.x2=2 <= B.x1=3 -> আলাদা ✗
     y: [3,4]∩... ✓                মানে এক axis-এই আলাদা -> overlap নেই

interval-এর ছবি (x-অক্ষ):
A:  [---------]
B:        [---------]
         overlap = [এই অংশ]   <- positive মাপ -> x-axis overlap ✓

লক্ষ করো — দ্বিতীয় ছবিতে A আর B হয়তো y-তে কাছাকাছি, কিন্তু x-অক্ষে A পুরো বাঁয়ে (A.x2 <= B.x1)। একটা অক্ষে আলাদা হলেই গোটা rectangle আলাদা।

6. Example input and output

A (x1,y1,x2,y2)    B (x1,y1,x2,y2)    overlap?
-------------------------------------------------
(0,0,2,2)          (1,1,3,3)          True   (কোণায় কোণায় ঢুকেছে)
(0,0,2,2)          (2,2,4,4)          False  (শুধু কোণ ছোঁয়, positive area নেই)
(0,0,4,4)          (1,1,2,2)          True   (B পুরো A-র ভেতরে)
(0,0,2,2)          (3,0,5,2)          False  (A পুরো B-র বাঁয়ে, x-এ ফাঁক)
(0,0,2,2)          (0,3,2,5)          False  (A পুরো B-র নিচে, y-এ ফাঁক)
(0,0,3,3)          (2,2,5,5)          True   (অংশত মিলেছে)

খেয়াল করো দ্বিতীয় case: rectangle দুটো শুধু একটা কোণ (2,2)-তে ছোঁয় — সাধারণ এলাকা শূন্য (একটা বিন্দু), তাই positive-area সংজ্ঞায় overlap নয়। এটাই touching বনাম overlapping-এর সূক্ষ্ম পার্থক্য।

7. Brute force thinking

প্রথমে যা মাথায় আসে — সব "কখন overlap করে" case সরাসরি গোনা, বা আরও স্থূলভাবে: ছোট ছোট ঘরে ভেঙে দেখা কোনো ঘর দুজনের মধ্যেই পড়ে কি না:

def overlap_brute(A, B):
    # প্রতিটা integer unit-cell দেখি — কোনোটা কি দুটোতেই আছে?
    ax1, ay1, ax2, ay2 = A
    bx1, by1, bx2, by2 = B
    for x in range(ax1, ax2):           # unit cell [x, x+1)
        for y in range(ay1, ay2):
            in_b = bx1 <= x < bx2 and by1 <= y < by2
            if in_b:
                return True
    return False

এটা integer rectangle-এ ঠিক উত্তর দেয় (positive area থাকলে অন্তত একটা unit cell শেয়ার হবে), কিন্তু rectangle বড় হলে ভয়াবহ ধীর, আর float coordinate-এ একদমই চলে না।

8. Why brute force may be slow

unit-cell scan-এর খরচ rectangle-এর ক্ষেত্রফলের সমান:

A = 1000 x 1000 হলে:
  brute force: প্রায় 1,000,000 cell scan      (ধীর, O(area))
  interval way: 4টা তুলনা                      (চোখের নিমেষে, O(1))

আর float coordinate (যেমন 1.5, 2.7) হলে unit-cell ধারণাই ভেঙে পড়ে।

মূল শিক্ষা: rectangle overlap একটা নির্ণায়ক (geometric) প্রশ্ন — সীমানার সংখ্যা কয়টা তুলনা করলেই উত্তর; ভেতরের প্রতিটা ঘর গোনা বিশাল অপচয়।

9. Better thinking

মূল insight: overlap করে না-কে সংজ্ঞায়িত করা সহজ — একটা পুরো বাঁয়ে/ডানে/উপরে/নিচে। তাই:

def overlap(A, B):
    no = (A[2] <= B[0] or B[2] <= A[0] or
          A[3] <= B[1] or B[3] <= A[1])
    return not no

চারটা সরল তুলনা, তারপর not। আর এটা ঠিক per-axis interval overlap — x-interval [A.x1, A.x2] আর [B.x1, B.x2] ছেদ করে, এবং y-interval-ও ছেদ করে। <= ব্যবহার করছি মানে শুধু ধার ছোঁয়াকে overlap ধরছি না (positive area লাগবে)।

10. Thinking tweak

আসল "আহা!": কঠিন প্রশ্নটা সরাসরি না ভেবে তার negation ভাবো — "কখন overlap করে?" এর জায়গায় "কখন overlap করে না?" — পরেরটার মাত্র চারটা পরিষ্কার case।

আর দ্বিতীয়, সমান গুরুত্বপূর্ণ tweak — 2D-কে দুটো স্বাধীন 1D-তে ভাঙো। rectangle overlap = (x-interval overlap) AND (y-interval overlap)। এই "axis-এ আলাদা করে ভাবো" চিন্তাটা bounding-box, collision detection, sweep line — সর্বত্র ফিরবে। মনে রাখো: কঠিন আকার প্রায়ই সরল projection-এর যোগফল।

11. Step-by-step dry run

চলো A = (0,0,2,2), B = (1,1,3,3) — overlap করে কি না:

1. শুরু: A নিচ-বাঁ (0,0) উপর-ডান (2,2); B নিচ-বাঁ (1,1) উপর-ডান (3,3)
2. A[2] <= B[0]? 2 <= 1? না (A ডানে যথেষ্ট ছড়িয়ে)
3. B[2] <= A[0]? 3 <= 0? না
4. A[3] <= B[1]? 2 <= 1? না (A উপরে যথেষ্ট ওঠে)
5. B[3] <= A[1]? 3 <= 0? না
6. no = না OR না OR না OR না = False
7. return not False = True → overlap করে ✓ (কোণায় কোণায় ঢুকেছে)

এবার শুধু-কোণ-ছোঁয়া A=(0,0,2,2), B=(2,2,4,4):

A[2] <= B[0]?  2 <= 2?  হ্যাঁ!  -> no = True  -> return False
মানে A ঠিক B-র বাঁয়ে শেষ হয়েছে যেখানে B শুরু; positive overlap নেই।

12. Python solution

def overlap(A, B):
    """দুটো rectangle (x1,y1,x2,y2) overlap করে কি না (positive area লাগবে)।
    negation trick: একটা পুরো বাঁয়ে/ডানে/উপরে/নিচে থাকলে overlap নেই।"""
    no_overlap = (A[2] <= B[0] or   # A পুরো B-র বাঁয়ে
                  B[2] <= A[0] or   # A পুরো B-র ডানে
                  A[3] <= B[1] or   # A পুরো B-র নিচে
                  B[3] <= A[1])     # A পুরো B-র উপরে
    return not no_overlap


def interval_overlap(a1, a2, b1, b2):
    """1D version: interval [a1,a2] আর [b1,b2] positive overlap করে কি?"""
    return a1 < b2 and b1 < a2


def overlap_via_intervals(A, B):
    """একই উত্তর, কিন্তু পরিষ্কারভাবে দুটো 1D check হিসেবে।"""
    x_ok = interval_overlap(A[0], A[2], B[0], B[2])
    y_ok = interval_overlap(A[1], A[3], B[1], B[3])
    return x_ok and y_ok


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert overlap((0, 0, 2, 2), (1, 1, 3, 3)) is True      # কোণায় ঢুকেছে
assert overlap((0, 0, 2, 2), (2, 2, 4, 4)) is False     # শুধু কোণ ছোঁয়
assert overlap((0, 0, 4, 4), (1, 1, 2, 2)) is True      # B ভেতরে
assert overlap((0, 0, 2, 2), (3, 0, 5, 2)) is False     # x-এ ফাঁক
assert overlap((0, 0, 2, 2), (0, 3, 2, 5)) is False     # y-এ ফাঁক
assert overlap((0, 0, 3, 3), (2, 2, 5, 5)) is True      # অংশত

# দুই পদ্ধতি একই উত্তর দেয় কি না
for A, B in [((0,0,2,2),(1,1,3,3)), ((0,0,2,2),(2,2,4,4)),
             ((0,0,2,2),(3,0,5,2)), ((0,0,4,4),(1,1,2,2))]:
    assert overlap(A, B) == overlap_via_intervals(A, B)

assert interval_overlap(1, 3, 2, 4) is True    # [1,3] ∩ [2,4]
assert interval_overlap(1, 2, 2, 4) is False   # শুধু 2-তে ছোঁয়

print(overlap((0, 0, 2, 2), (1, 1, 3, 3)))     # True
print(overlap((0, 0, 2, 2), (2, 2, 4, 4)))     # False
print(overlap_via_intervals((0, 0, 3, 3), (2, 2, 5, 5)))  # True
print("সব test pass!")

13. Line-by-line explanation

def overlap(A, B):
    no_overlap = (A[2] <= B[0] or B[2] <= A[0] or
                  A[3] <= B[1] or B[3] <= A[1])
    return not no_overlap

A[2] হলো A-র ডান প্রান্ত (x2), B[0] হলো B-র বাঁ প্রান্ত (x1)। A[2] <= B[0] মানে A পুরো B-র বাঁয়ে। চারটা শর্তের যেকোনোটা সত্যি হলে overlap নেই। not দিয়ে উল্টে আসল উত্তর। <= মানে শুধু ধার ছোঁয়াকে overlap ধরছি না।

def interval_overlap(a1, a2, b1, b2):
    return a1 < b2 and b1 < a2

1D-তে দুটো interval positive overlap করে যদি একটা শুরু অন্যটার শেষের আগে আর উল্টোটাও — a1 < b2 and b1 < a2। < মানে শুধু ছোঁয়া যথেষ্ট নয়।

def overlap_via_intervals(A, B):
    x_ok = interval_overlap(A[0], A[2], B[0], B[2])
    y_ok = interval_overlap(A[1], A[3], B[1], B[3])
    return x_ok and y_ok

এটাই decomposition-টা স্পষ্ট দেখায় — x-অক্ষে interval overlap এবং y-অক্ষে interval overlap, তবেই rectangle overlap।

বাকি assert লাইনগুলো — কোণ-ছোঁয়া, ভেতরে-থাকা, ফাঁক, আর দুই পদ্ধতির মিল — সব যাচাই করছে; সব মিললে শেষে সব test pass!।

14. Output walkthrough

চালালে যা ছাপবে:

True
False
True
সব test pass!

প্রথম: (0,0,2,2) আর (1,1,3,3) কোণায় কোণায় ঢুকেছে → True। দ্বিতীয়: (0,0,2,2) আর (2,2,4,4) শুধু কোণ (2,2) ছোঁয়, positive area নেই → False। তৃতীয়: interval পদ্ধতিতেও (0,0,3,3) আর (2,2,5,5) overlap → True। তার আগের সব assert চুপচাপ pass করেছে। সবশেষে সব test pass!।

15. Time complexity

O(1) — চারটা তুলনা (বা দুটো interval check), input-নির্বিশেষে ধ্রুবক। rectangle যত বড়ই হোক, কাজ একই।

16. Space complexity

O(1) — শুধু কয়েকটা bool variable। কোনো বাড়তি data structure নেই।

17. Common mistakes

1. < আর <= মিশিয়ে ফেলা — শুধু ধার/কোণ ছোঁয়াকে overlap ধরবে কি না, সংজ্ঞা না পড়ে ভুল operator; positive area চাইলে negation-এ <= (এখানে যেমন)।
2. সব "করে" case সরাসরি গোনার চেষ্টা — case-এর জঙ্গল; negation ("করে না") চারটা পরিষ্কার শর্তে নামায়।
3. এক অক্ষ ভুলে যাওয়া — শুধু x বা শুধু y দেখলে ভুল; দুটো অক্ষেই overlap লাগবে।
4. কোণ-input ভুল ধরা — (x1,y1) নিচ-বাঁ, (x2,y2) উপর-ডান ধরে নিয়েছি; কেউ width/height বা অন্য কোণ দিলে আগে normalize করো।
5. কাত করা (rotated) rectangle-এ এই trick খাটানো — এটা শুধু axis-aligned-এ; rotated হলে আলাদা (separating axis) দরকার।

18. Harder problems that inherit this idea

• LeetCode — Rectangle Area (https://leetcode.com/problems/rectangle-area/) — দুটো rectangle-এর মিলিত ক্ষেত্রফল; overlap অংশ বাদ দিতে এই interval overlap-ই লাগে।
• LeetCode — Rectangle Area II (https://leetcode.com/problems/rectangle-area-ii/) — অনেক rectangle-এর ইউনিয়ন area (sweep line); ভিত্তি এই 1D interval চিন্তা।
• LeetCode — Meeting Rooms II (https://leetcode.com/problems/meeting-rooms-ii/) — 1D interval overlap-এর সরাসরি সম্প্রসারণ (সময়রেখায়)।

19. Pattern learned

Per-axis interval overlap + negation trick — rectangle overlap = (x-interval overlap) AND (y-interval overlap); আর "করে না"-কে সংজ্ঞায়িত করা সহজ (একটা পুরো বাঁয়ে/ডানে/উপরে/নিচে)। বড় শিক্ষা: কঠিন 2D আকারকে স্বাধীন 1D projection-এ ভাঙো, আর কঠিন শর্ত উল্টে (negation) সরল করো।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "rectangle overlap = প্রতি অক্ষে interval overlap; সহজ উপায় negation — A.x2<=B.x1 or B.x2<=A.x1 or A.y2<=B.y1 or B.y2<=A.y1 হলে overlap নেই, not দিয়ে উল্টাও। 2D-কে দুটো 1D-তে ভাঙো; < vs <= সংজ্ঞা দেখে ঠিক করো।"

পরের ধাপ → 119 — Circle and Point (আবার squared distance — 113-এর জমজ)। সম্পর্কিত → 122 — Rotate Matrix and Coordinates (আরেকটা interview-ঘরানা)।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।