My Leet Code Journey

  Problem Description You have  d  dice, and each die has  f  faces numbered  1, 2, ..., f . Return the number of possible ways (out of  fd  total ways)  modulo  10^9 + 7  to roll the dice so the sum of the face up numbers equals  target . Example 1: Input: d = 1, f = 6, target = 3 Output: 1 Explanation: You throw one die with 6 faces. There is only one way to get a sum of 3. Example 2: Input: d = 2, f = 6, target = 7 Output: 6 Explanation: You throw two dice, each with 6 faces. There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1. Example 3: Input: d = 2, f = 5, target = 10 Output: 1 Explanation: You throw two dice, each with 5 faces. There is only one way to get a sum of 10: 5+5. Example 4: Input: d = 1, f = 2, target = 3 Output: 0 Explanation: You throw one die with 2 faces. There is no way to get a sum of 3. Example 5: Input: d = 30, f = 30, target = 500 Output: 222616187 Explanation: The answer mu...

Photo by Susan Yin on  Unsplash Problem Description There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up , down , left or right , but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction. Given the ball’s start position , the destination and the maze , determine whether the ball could stop at the destination. The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes. Example 1: Input 1: a maze represented by a 2D array 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 Input 2: start coordinate (rowStart, colStart) = (0, 4) Input 3: destination coordinate (rowDest, colDest) = (4, 4) Output: true Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right. Sol...

  Photo by  cetteup  on  Unsplash Problem Description Given an integer array  nums , find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Solution Obvious Solution The obvious (and brute force) way is list all contiguous subarray and then calculate each one’s sum to get the largest one out. For subarrays starting from 1st number, there will be N subarrays; forsubarrays starting from 2nd number, N-1 subarrays; … So in total, I need to calculate N+N-1+N-2+…+1 which is O(N²) without taking the calculation of the sums of subarrays. Obviously, obvious solution is too time consuming. Best Solution (to me) The intuition is the quickest one should be O(N). The reason is at least I need to visit each element once. Let me imaging when I run into a number with index = x, the largest sum of a subarray ending with x sho...

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: o...

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...