Problem overview
The method intersect(_ a1: Int, _ b1: Int, _ a2: Int, _ b2: Int) -> Bool in the class Solution receives two closed intervals, [a1, b1] and [a2, b2]. A closed interval includes both of its endpoints. The method returns true when the two intervals share at least one number.
The intervals [1, 6] and [3, 8] overlap on 3 to 6, so the answer is true. [1, 4] and [4, 6] share the single point 4, so the answer is true as well. [1, 8] contains [4, 6] completely, which is also an intersection. [4, 6] and [1, 3] have nothing in common, so the answer is false. The solution must take constant time and constant extra space.
Approach: describe the misses
There are many ways two intervals can overlap: partially from either side, one inside the other, touching at an endpoint. Listing them all is error-prone. There are only two ways they can miss:
- the first interval ends before the second begins:
b1 < a2; - the second interval ends before the first begins:
b2 < a1.
If neither holds, the intervals must overlap. So the answer is the negation of "one of the two misses happens".
The comparisons are strict. If b1 == a2, as in [1, 3] and [3, 5], the intervals share the point 3, so that case must not count as a miss.
Step by step
- Write the two miss conditions:
b1 < a2andb2 < a1. - Join them with
||. Either miss is enough to separate the intervals, so an or is the right connector. Put the result in parentheses. - Negate the group with
!. The parentheses matter:!applies to the whole group, so the result isfalseif either miss holds andtrueotherwise. - Return that value directly. A comparison is already a
Bool, so noifis needed.
The solution in Swift
class Solution {
func intersect(_ a1: Int, _ b1: Int, _ a2: Int, _ b2: Int) -> Bool {
return !(b1 < a2 || b2 < a1)
}
}
Swift details to note:
- Returning a Bool expression. Writing
if cond { return true } else { return false }is longer and does the same thing. - Parentheses with
!. Without them,!b1 < a2doesn't compile, because!would apply to anInt. - Short-circuiting. If
b1 < a2istrue, Swift doesn't evaluate the second comparison. - An equivalent form. By De Morgan's laws,
!(b1 < a2 || b2 < a1)is the same asb1 >= a2 && b2 >= a1: each interval ends at or after the other one starts.
Complexity
Time: O(1). The method does two comparisons whatever the numbers are. Space: O(1). It stores nothing.
Testing
let s = Solution()
print(s.intersect(1, 6, 3, 8))
print(s.intersect(1, 4, 4, 6))
print(s.intersect(1, 8, 4, 6))
print(s.intersect(4, 6, 1, 3))
print(s.intersect(1, 3, 5, 7))
The output is:
true
true
true
false
false
Edge cases and common mistakes
- Touching endpoints. Using
<=in the miss conditions would make[1, 4]and[4, 6]a miss. The comparisons must be strict. - Containment. One interval inside the other is an intersection. Neither miss condition triggers, so the method returns
true. - Order of the arguments. The first interval can be on either side. The two miss conditions are symmetric, so both orders work.
- Using
&&for the misses. Requiring both misses at once can never be true for valid intervals, so the method would always returntrue. - Dropping the parentheses. Only the whole group should be negated.
