Start learning free

LESSON 86 OF 338 · CONDITIONAL STATEMENTS - CHALLENGES

Interval Intersection in Go: O(1) with a Negated Condition

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

    GO · CONDITIONAL STATEMENTS - CHALLENGES

    Interval Intersection in Go, explained

    Problem overview

    The function intersect receives the ends of two closed intervals, [a1, b1] and [a2, b2], and returns true when they share at least one number. "Closed" means the end points belong to the interval, so [1, 4] contains 4.

    The examples show the cases:

    • [1, 6] and [3, 8] overlap on 3 to 6, so the answer is true.
    • [1, 4] and [4, 6] only touch, at the number 4. Because 4 is in both, the answer is true.
    • [1, 8] and [4, 6]: the second sits entirely inside the first, so the answer is true.
    • [4, 6] and [1, 3] are apart, so the answer is false.

    The algorithm must run in O(1) time and use O(1) extra space, so no loop over the numbers in the intervals is allowed.

    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, identical, touching at a point. Listing them all is error-prone. There are only two ways they can fail to overlap:

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

    If neither is true, the intervals must share a number. So the answer is the negation of "one of them is entirely to the left of the other".

    The comparisons are strict (<, not <=), because intervals that touch at a single point do intersect. With b1 = 4 and a2 = 4, the test b1 < a2 is false, so the intervals count as overlapping.

    Step by step

    1. Write the two miss conditions: b1 < a2 and b2 < a1.
    2. Join them with ||. Either one alone is enough for the intervals to be apart, so "or" is the right connective.
    3. Wrap the pair in parentheses and negate it with !. The parentheses make the ! apply to the whole group instead of just the first comparison.
    4. Return the result directly. The expression is already a bool, so no if is needed.

    The solution in Go

    func intersect(a1, b1, a2, b2 int) bool {
    return !(b1 < a2 || b2 < a1)
}

    Checking it against the examples: for 1, 6, 3, 8, 6 < 3 is false and 8 < 1 is false, so the group is false and the negation is true. For 4, 6, 1, 3, 6 < 1 is false but 3 < 4 is true, so the group is true and the function returns false.

    Some Go details:

    • Grouped parameters. a1, b1, a2, b2 int declares all four parameters with type int. It is shorthand for repeating the type on each one.
    • Returning a comparison. A comparison or a logical expression is a value of type bool in Go, so it can be returned directly. Writing if cond { return true } else { return false } is longer and says nothing more.
    • Short-circuiting. If b1 < a2 is true, Go skips the second comparison. It makes no difference here, but it is how || always behaves.
    • The parentheses matter. Without them, !b1 < a2 || ... would try to negate the integer b1, which does not compile.

    Complexity

    The function does at most two comparisons and one negation, so time is O(1). It stores nothing, so extra space is O(1). The size of the intervals doesn't matter, because only their end points are compared.

    Edge cases and common mistakes

    • Touching intervals. intersect(1, 3, 3, 5) returns true. Using <= in the miss conditions would wrongly return false.
    • Single-point intervals. intersect(5, 5, 5, 5) returns true, because both intervals hold exactly the number 5. intersect(5, 5, 6, 6) returns false.
    • Gaps by one. intersect(1, 3, 4, 6) returns false. For integers there is no number between 3 and 4, and the intervals share none.
    • Either order of arguments. The test is symmetric: swapping the two intervals swaps the two comparisons, and the result is the same.
    • Using && for the misses. Requiring both b1 < a2 and b2 < a1 can never succeed for valid intervals, so the function would always return true.
    • Forgetting the parentheses. !b1 < a2 || b2 < a1 does not compile, because ! applies only to b1, which is an integer.

    Testing

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