There were two approaches that came to my mind when I first read this problem. This is a classic recursion problem and we can use a a modified DFS approach checking at each point if we can move left and down and then recurse from the new positions. The time complexity of this would be exponential of the order of …

## Leetcode – 212. Word Search II

This problem builds on Word Search, the only difference being instead of searching for one particular word, we are now given a set of words. We could take our solution from the Word Search problem and run that algorithm for every word in the data set which would result in a lot of wasted computations as the nested for loops …

## Leetcode – 79. Word Search

In this problem, we are given a two dimensional board of characters and we have to check if the word can be found in the board by checking adjacent cells only. A basic strategy to solve this problem would be to start walking down the board until the first character is found. Once the first character is found, look at …

## Leetcode – 863. All Nodes Distance K In Binary Tree

When I first saw this problem, I panicked! I knew that this some how had to be a Breadth First Search problem because BFS from any node gives you the shortest path to every other node that is connected to the tree. Since every node is represented as a TreeNode with only left and right pointers, I would need to …

## Leetcode – 33. Search In Rotated Sorted Array

This is straight up Binary Search problem with some modifications. When we find the mid point of the given array, one of two things will hold true: The array from start to mid is sorted. The array from mid to end is sorted. Once we know which is the sorted half, all we have to do is check if the …

## Leetcode – 270. Closest Binary Search Tree Value

If the type of the target and they type of the value in the tree nodes were the same, and the problem was to find the node in the tree that is just smaller than the target, the problem becomes fairly simple. For example, given target = 17 and the graph:

1 2 3 4 5 6 7 |
20 / \ 9 25 / \ 5 12 / \ 11 14 |

the value we will return is 14. The …

## Leetcode – 42. Trapping Rain Water

There’s one thing common between this problem and the Container With Most Water problem and that is the height of the shorter tower dictates the result. In this problem, the amount of water that can accumulate between two towers is limited by the height of the shorter tower. Consider an array [4, 5, 9, 7 ,1, 0 ,4, 0 ,8 …

## Leetcode – 23. Merge k Sorted Lists

There are so many ways to solve this problem. Let’s look at some of them: Iterate through all the nodes in all the k lists and dump the values in an array, then sort the array, iterate through the sorted array, generate the linked list and return the head. This obviously doesn’t sound like an efficient algorithm. We can use …

## Leetcode – 22. Generate Parentheses

Before we start solving this problem, let’s do some math first. The problem statement clearly states that we have N pairs of parentheses to work with. That means for a string to be considered as part of the solution, it must be of size 2N. Once we have generated a string of size 2N, for it to actually be a …

## Leetcode – 54. Spiral Matrix

The first idea that popped in my head after reading this problem is to start at index [0,0] and move right, walk down all the columns, turn right, walk down all the rows, move right, walk down all the columns in decreasing order, move right, walk up all the rows in decreasing order. At this point, how do we keep …

- Page 1 of 2
- 1
- 2