Start learning free

LESSON 87 OF 348 · CONDITIONAL STATEMENTS - CHALLENGES

Interval Intersection in Kotlin: O(1) Check with ! and ||

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

    KOTLIN · CONDITIONAL STATEMENTS - CHALLENGES

    Interval Intersection in Kotlin, explained

    Problem overview

    A closed interval [a, b] contains every real number x with a <= x <= b, ends included. The function intersect(a1: Int, b1: Int, a2: Int, b2: Int): Boolean in class Solution receives two intervals, [a1, b1] and [a2, b2], and returns true when they share at least one number.

    The examples:

    • [1, 6] and [3, 8] share the numbers 3 to 6, so the answer is true.
    • [1, 4] and [4, 6] share exactly the number 4, so the answer is true.
    • [1, 8] and [4, 6] overlap because the second lies inside the first, so the answer is true.
    • [4, 6] and [1, 3] share nothing, so the answer is false.

    The statement asks for O(1) time and O(1) extra space: a fixed number of comparisons, whatever the size of the numbers.

    Approach: describe the misses, then negate

    There are many ways two intervals can overlap: partly from the left, partly from the right, one inside the other, or touching at a point. Listing them all is tedious. There are only two ways they can fail to overlap, and they are easy to state:

    • The first interval ends before the second begins: b1 < a2.
    • The second interval ends before the first begins: b2 < a1.

    If neither is true, the intervals must overlap. So the answer is the negation of "one of the two misses holds". This works because every interval has its start at most its end, so if neither interval lies entirely to the left of the other, they must share a number.

    Step by step

    1. Write the two miss conditions: b1 < a2 and b2 < a1.
    2. Join them with ||. Either miss is enough to separate the intervals, so the combined condition is true whenever they are disjoint.
    3. Wrap the pair in parentheses and negate it with !. The parentheses make the ! apply to the whole combination. Without them, it would try to negate only the first comparison.
    4. Return the result directly. A condition is already a Boolean, so a single return statement is enough, with no if and no else.

    The solution in Kotlin

    class Solution {
    fun intersect(a1: Int, b1: Int, a2: Int, b2: Int): Boolean {
        return !(b1 < a2 || b2 < a1)
    }
}

    Kotlin details worth knowing:

    • Returning a Boolean expression. Writing if (cond) { return true } else { return false } works but is wordy. The comparison already is the Boolean that the function returns.
    • Strict < on purpose. Intervals that only touch, such as [1, 4] and [4, 6], share the number 4. For them, b1 < a2 is 4 < 4, which is false, so they count as intersecting. Using <= would wrongly report a miss.
    • Short-circuiting. If b1 < a2 is true, Kotlin skips the second comparison. The result is the same either way.
    • Same result by De Morgan. The expression is equivalent to b1 >= a2 && b2 >= a1, which says "each interval ends at or after the other one starts".

    Complexity

    Time: O(1). The function does at most two comparisons and one negation.

    Space: O(1). It creates no collections and keeps no extra data.

    Edge cases and common mistakes

    • Touching ends. [1, 3] and [3, 5] intersect at 3, so the answer is true. This is the case most likely to be wrong with <=.
    • One interval inside the other. [1, 8] and [4, 6] returns true. A check that only compares the ends of one interval against the other would miss this.
    • Order of the intervals. Swapping the two intervals does not change the answer, and the condition is symmetric.
    • Single points. [5, 5] and [5, 5] returns true, and [5, 5] and [6, 6] returns false.
    • Using && for the misses. b1 < a2 && b2 < a1 can never be true for valid intervals, so it would make every pair look like an overlap. The two misses are alternatives, so join them with ||.
    • Forgetting the parentheses. !b1 < a2 || b2 < a1 does not compile, since ! would apply to b1, an Int.

    Testing

    • intersect(1, 6, 3, 8) returns true.
    • intersect(1, 4, 4, 6) returns true.
    • intersect(1, 8, 4, 6) returns true.
    • intersect(4, 6, 1, 3) returns false.
    • intersect(1, 3, 5, 9) returns false.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free