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 …

## Leetcode – 11. Container With Most Water

From the description of the problem, we are told that each number in the array represents the height of the vertical line at that index. So given an array [4, 3, 7, 8, 2, 6, 9, 5], a visual representation of this array would look something like: | | | | | | | | | | | | | …

## Leetcode – 10. Regular Expression Matching (Dynamic Programming)

This article is in continuation to my previous article solving the same problem with recursion. The fact that this problem could be solved with recursion made me think about the optimal substructure of this problem. As it turns out, this problem has one and can be solved using dynamic programming. To solve using dynamic programming, we will construct a table …

## Leetcode – 10. Regular Expression Matching

My initial thought after reading the description of this problem is that let’s just consider, for the moment, that this problem needs to be implemented for • only. For e.g given the text abc does it match a•b? You can come up with examples and you will realize that to implement just the •, the lengths of the two strings …