Problem overview
The method intersect receives two closed intervals as four numbers: a1 and b1 for the first, a2 and b2 for the second. In each interval the start is not greater than the end. A closed interval [a, b] contains every number x with a <= x <= b, endpoints included. The method returns true when some number belongs to both intervals, and false otherwise.
Examples: [1, 6] and [3, 8] share the numbers from 3 to 6, so the answer is true. [1, 4] and [4, 6] share exactly the number 4, so the answer is true as well. [1, 8] contains [4, 6] entirely, so the answer is true. [4, 6] and [1, 3] share nothing, so the answer is false.
The task asks for O(1) time and O(1) extra space, so the answer must come from a fixed number of comparisons and no loops over the numbers inside the intervals.
Approach: count the ways to miss
Overlaps come in many shapes: partial from the left, partial from the right, one inside the other, touching at a point. Listing them all is error-prone. Misses are easier, because there are only two:
- The first interval lies entirely to the left of the second:
b1 < a2. - The second interval lies entirely to the left of the first:
b2 < a1.
If neither happens, the intervals must overlap. So the method asks "did they miss?" and returns the opposite. Checking the examples: for [4, 6] and [1, 3], b2 < a1 is 3 < 4, which is true, so the answer is false. For [1, 4] and [4, 6], 4 < 4 is false and 6 < 1 is false, so the answer is true.
Step by step
- Write the two miss conditions:
b1 < a2andb2 < a1. - Join them with
||inside parentheses. The result istrueif either interval is entirely to the left of the other. The parentheses matter, because the next step negates the whole group. - Negate the group with
!and return it in a singlereturn. The result isfalseif either miss holds andtrueotherwise.
The comparisons are strict (<, not <=). Intervals like [1, 3] and [3, 5] share the point 3, so touching counts as intersecting. With <=, the touching case would be wrongly reported as a miss.
The solution in TypeScript
class Solution {
intersect(a1: number, b1: number, a2: number, b2: number): boolean {
return !(b1 < a2 || b2 < a1);
}
}
Points about the TypeScript:
- Comparisons produce booleans.
b1 < a2is already aboolean, so noifis needed. Writingif (...) { return false; } else { return true; }would give the same answers but say the same thing in more lines. - Operator precedence.
!binds tighter than||. Without the parentheses,!b1 < a2 || ...would negate onlyb1, which is a number, and then compare the resulting boolean witha2. The compiler would report that comparison as an error, but the real mistake is the missing parentheses. - The annotations are erased.
numberandbooleanguide the compiler only, and the JavaScript that tsc writes does not check them.
Complexity
The method evaluates at most two comparisons, whatever the numbers are. It takes O(1) time and uses no extra memory beyond the four parameters, so O(1) space. The length of the intervals doesn't matter, because the code never visits the numbers between the endpoints.
Edge cases and common mistakes
- Touching endpoints.
[1, 4]and[4, 6]intersect, as does any pair that shares only an endpoint. Use strict<for the miss tests. - Containment. In
[1, 8]and[4, 6], neither endpoint test triggers, so the method returnstrue. Solutions that only compare start points with end points of one interval often forget this case. - Order of the arguments. The parameters are
a1, b1, a2, b2, so the two intervals are the pairs (a1, b1) and (a2, b2). Mixing up which number belongs to which interval flips results silently. - Single points. An interval like
[5, 5]is allowed, since it satisfiesa <= b.intersect(5, 5, 5, 5)istrue. - Negative numbers and decimals. They work the same way, because only comparisons are used.
[-3, -1]and[-2, 0]intersect.
Testing
intersect(1, 6, 3, 8)should givetrue.intersect(1, 4, 4, 6)should givetrue.intersect(1, 8, 4, 6)should givetrue.intersect(4, 6, 1, 3)should givefalse.intersect(1, 2, 3, 4)should givefalse.