Start learning free

LESSON 91 OF 410 · CONDITIONAL STATEMENTS - CHALLENGES

Interval Intersection in Python: Check Two Closed Intervals in O(1)

Practice Read the full explanation

Given two closed intervals [A1, B1] and [A2, B2], check and return if the two intervals intersect each other.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

Two closed intervals are said to intersect if they have common numbers, i.e. that appear in both intervals.

Example 1:

Input: A1 = 1, B1 = 6, A2 = 3, B2 = 8
Output: True

Example 2:

Input: A1 = 1, B1 = 4, A2 = 4, B2 = 6
Output: True

Example 3:

Input: A1 = 1, B1 = 8, A2 = 4, B2 = 6
Output: True

Example 4:

Input: A1 = 4, B1 = 6, A2 = 1, B2 = 3
Output: False

Note:

Your algorithm should run in O(1) time and use O(1) extra space.


Hints:

Instead of thinking about when the intervals intersect each other, it's easier to think about when they do not intersect each other.

The intervals do not intersect each other when one of them is "to the left" of the other one i.e. B1 < A2 or B2 < A1.

We can write an if statement checking if B1 < A2 or B2 < A1. If so, we return False. Otherwise, we return True.

You can implement this using no else statements. You can even implement it in one line using only one return.
STEP 1 OF 1
    Ctrl + Enter to check

    PYTHON · CONDITIONAL STATEMENTS - CHALLENGES

    Interval Intersection in Python, explained

    Problem overview

    The method intersect(self, A1, B1, A2, B2) receives two closed intervals, [A1, B1] and [A2, B2]. It returns True if the intervals share at least one number and False if they do not. "Closed" means the end points belong to the interval, so [1, 4] includes both 1 and 4.

    Take the examples. [1, 6] and [3, 8] overlap on 3 to 6, so the answer is True. [1, 4] and [4, 6] share only the number 4, which is enough, so the answer is True. [1, 8] contains [4, 6] completely, so the answer is True. [4, 6] and [1, 3] have nothing in common, so the answer is False.

    Approach: find the cases that do not overlap

    There are many ways two intervals can overlap: partially from the left, partially from the right, one inside the other, both equal. Checking each one is easy to get wrong. There are only two ways they can fail to overlap:

    • The first interval ends before the second starts: B1 < A2.
    • The second interval ends before the first starts: B2 < A1.

    If neither is true, the intervals must overlap, so the answer is the negation of "one is entirely to the left of the other".

    The comparisons are strict (<, not <=). When B1 == A2 the intervals touch at one number, and for closed intervals a shared end point counts as an intersection. With <= the example [1, 4] and [4, 6] would wrongly come out as False.

    Step by step

    1. Write the "misses" condition. B1 < A2 or B2 < A1 is true exactly when one interval lies entirely to the left of the other.
    2. Put it in parentheses and negate it with not. Without the parentheses, not would apply only to the first comparison.
    3. Return the result directly. The expression already evaluates to True or False, so no if/else is needed.

    The solution in Python

    class Solution:
    def intersect(self, A1: int, B1: int, A2: int, B2: int) -> bool:
        return not (B1 < A2 or B2 < A1)

    A few Python details:

    • Comparison operators already produce a bool, and or and not keep it that way, so the single return replaces an if that returns False and a second return of True.
    • or short-circuits: if B1 < A2 is true, the second comparison is never evaluated.
    • not binds more loosely than comparison operators but more tightly than or, which is why the parentheses matter: not B1 < A2 or B2 < A1 would mean (not (B1 < A2)) or (B2 < A1), a different condition.

    An equivalent form

    Applying De Morgan's laws, not (P or Q) becomes (not P) and (not Q), and the negation of < is >=. So the same test can be written as A2 <= B1 and A1 <= B2: each interval starts no later than the other one ends. Both forms return identical answers for every input.

    Complexity

    • Time: O(1). At most two comparisons, whatever the values are.
    • Space: O(1). No extra variables.

    Edge cases and common mistakes

    • Touching end points. [1, 3] and [3, 5] intersect at 3, and the strict comparisons give True.
    • Single-point intervals. [2, 2] against [2, 2] is True, while [2, 2] against [3, 3] is False.
    • Order of the two intervals. The result is the same if you swap them: intersect(5, 7, 1, 3) and intersect(1, 3, 5, 7) both return False. That is why the condition checks both directions.
    • Checking only one direction. Testing just B1 < A2 misses the case where the second interval is on the left, like [4, 6] and [1, 3].
    • Using and where or belongs. The intervals miss each other when either condition holds, not when both hold.

    Testing

    s = Solution()
print(s.intersect(1, 6, 3, 8))  # True
print(s.intersect(1, 4, 4, 6))  # True
print(s.intersect(1, 8, 4, 6))  # True
print(s.intersect(4, 6, 1, 3))  # False
print(s.intersect(1, 3, 5, 7))  # False

    Since the comparisons work on any numbers, the same method handles floats: intersect(1.5, 2.5, 2.5, 3) is True.

    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free