My Leet Code Journey

Photo by  Berat Çıldır  on  Unsplash Problem Description Given a binary tree, return the  vertical order  traversal of its nodes values. For each node at position  (X, Y) , its left and right children respectively will be at positions  (X-1, Y-1)  and  (X+1, Y-1) . Running a vertical line from  X = -infinity  to  X = +infinity , whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing  Y  coordinates). If two nodes have the same position, then the value of the node that is reported first is the value that is smaller. Return an list of non-empty reports in order of  X  coordinate. Every report will have a list of values of nodes. Example 1: Input: [1,3,5,null,null,7,9,null,null, 11,13] Output: [[3],[1,7],[5,11],[9],[13]] Solution As the graph for above example shows, it is actually asking for one thing: output all Y values (from smallest to largest) by X value from smallest to large

Problem Description Given a collection of intervals, merge all overlapping intervals. Example 1: Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6]. Example 2: Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping. Solution Obvious Solution The obvious (and brute force) way is : assuming there are N intervals, pick the first interval and compare it with the rest N-1 intervals, if there is overlap, I will merge the overlapped interval into the first interval; after that, I should have M intervals where M≤N; then I pick the second interval from those M intervals and compare it with the rest M-1 intervals and repeat the same logic … until I reach the last interval. In worst case (no overlap at all), each one needs to compare with the rest N-1, N - 2, N - 3, …. intervals and hence make the time complextiy O(N²). To optimize

Photo by  Paweł Czerwiński  on  Unsplash Problem Description Given an array of integers and an integer  k , you need to find the total number of continuous subarrays whose sum equals to  k . Example 1: Input: nums = [2,2,3,0,4,-1,1,6], k = 7 Output: 3 Solution Obvious Solution There is certainly a brute force way. Iterarte the whole list, check the sum of (currentElement to currentElement+1), (currentElement to currentElement + 2), pesudo code looks like: In total, there are 3 loops and make the time complexity O(N³). It should work but definitely not an efficient way. There are ways to optimize this since there are many duplication of computation and the complexity can be decreased to O(N²). Best Solution (to me) Obviously, each subarray will end up with some index. Let me use i to represent that  some index . And sum(0 to i) is very easy (and cheap — just take O(N)) to get. Look at below example at i = 4, sum(0 to 4)= X + K. That means sum(0 t

Photo by  Ricky Kharawala  on  Unsplash Problem Description Given a non-empty, singly linked list with head node  head , return a middle node of linked list. If there are two middle nodes, return the second middle node. Example 1: Input: [1,2,3] Output: Node 2 from this list (Serialization: [2,3]) The returned node has value 3. (The judge's serialization of this node is [2,3]). Example 2: Input: [1,2,3,4] Output: Node 3 from this list (Serialization: [3,4]) Since the list has two middle nodes with values 2 and 3, I return the second one. Solution There are basically 2 ways to tackle this problem.  One  is obvious to scan the link twice: the first time to get the total number of nodes, then I can divide it by 2 to get the middle index, a second scan will be run to find the middle index to return.  The other  way to do it is using one time scan: I can use 2 movers (fast and slow ones), in each iteration, slow mover will only move to the next node while fast one will move to the next