INTERVAL LIST INTERSECTIONS | LEETCODE 986 | PYTHON TWO-POINTER SOLUTION
Vložit
- čas přidán 27. 07. 2024
- Channel Discord Community: / discord
Problem Link: leetcode.com/problems/interva...
Today we are solving a popular Facebook interview question that can be solved using a two-pointer approach: Interval List Intersections. This question is quite easy to reason about visually and it turns out that writing the code for this is actually quite simple as well.
TIMESTAMPS
00:00 Intro
00:07 Question Prompt
00:33 Basic Example
01:15 Solution Intuition
4:04 Coding
10:19 Time/Space Complexity
11:30 Outro - Věda a technologie
Bro your explanation is GOLD
Honestly man, I’m sooo grateful for you! Thank you soo much!
thank you for making this video
we're in the code editor, let's type this up....
An alternate approach to solve the above problem. I treated it like a sweep line. The time complexity is O(nlogn) though.
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
firstList.extend(secondList)
firstList.sort()
answer = []
end = firstList[0][1]
for i in range(1, len(firstList)):
if firstList[i][0]
Could work yes, but interviewer will likely for this want O(N) time and without using extra space (from the sort) so expect a follow-up to reduce the complexity of your solution if you do this
@@crackfaang You are correct. I often wonder how to come up with a better solution that is radically different (based on an entirely different idea) than the one you began with. Do you have any pointers when we face the above issue?
@@Shreyas535 Either you are smart enough to come up with it from prior experience with similar algorithms or you just memorise the optimal solution. After you learn the fundamentals of LC and the common algorithms such that you can explain solutions, the rest is just memorisation haha