My Leet Code Journey

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