 # LC986

Problem:
Given two sorted lists of intervals, List A and List B, the intervals in each list are not overlapped or disjoint. Find the overlapping intervals between A and B

Intuition:
When we see two sorted arrays/Lists, naturally we can think of anther problem that we know how to solve — merge two sorted arrays.
Thus, we can use two pointers to do this problem. We now how to move the pointers according to the ending time of each interval. If A[i].end < B[j].end, we move i because B[j] may have additional time period to overlap with different interval from A.
Secondly, we can easily get the overlapping interval by:

`Interval a = [s1, e1], b = [s2, e2]If s2 <= e1 and s1 <= e2 then, overlap interval = [max(s1, s2), min(e1, e2)]`

Algorithm

--

--

# LC 1041

Problem:
Instruction for a robot movement
L : turn left, R: turn right, G: go straight for 1 step
Given sequence of instruction will be repeated indefinitely.

Goal: given a sequence of instructions, check if robot forming a cycle.

Intuition:
if after one scan of execution, the robot faces different direction than starting direction(north), then won’t form a cycle.
or if the starting position and the ending position is the same, it forms a cycle

Algorithm:
define four directions: [<(0, 1), north>, <(1, 0), east>, <(0, -1), south>, <(-1, 0), west>]
as we know the initial direction is always north, so use a variable to represent the direction, cur = 0, here 0 is the index in the direction array.
loop thru each instruction char, and change the cur accordingly
use (x, y) to represent position, and update the x, y when G is encountered.

Code:

--

--

# LC 560

Goal: Find the numbers of subarrays that sum up to k. Array is an int array and has duplicates and negative numbers.

Intuition:
when negative numbers are allowed, then we cannot use the sliding window method because we can’t decide the right boundary of the window. Thus, we need a…

--

--