This post covers the Largest Rectangle in Histogram problem on Leetcode.
The challenge is not in figuring out how to solve the problem but rather to figure out how to optimize the runtime. It’s a direct application of the technique used in Previous Smaller Element as covered in this blog post.
Given an array of integers
heightsrepresenting the histogram's bar height where the width of each bar is
1, return the area of the largest rectangle in the histogram.
Imagine having rectangular blocks arranged in a straight line. Each block has a width of 1 unit and the
This blog post covers a variation of the Next Greater Element II problem on Leetcode. It is one of the problems which requires very clever use of a simple data structure. Moreover, this technique is used in several other Leetcode problems such as Largest Rectangle In Histogram and Maximal Rectangle as a sub-routine.
Given an array
nums, return the previous smaller number (PSE) for every element in
The previous smaller number of an element
xis the first number (highest index) to the left of
xthat is smaller than
This blog post covers the Shortest Path In A Grid With Obstacles Elimination problem on Leetcode.
This problem illustrates how a standard graph traversal algorithm can solve a tricky problem if we smartly encode multiple parameters into the graph state.
You are given an
m x ngrid, where each cell is either
1(obstacle). In one step, you can move up, down, left or right from and to an empty cell.
Return the minimum number of steps to walk from the upper left corner
(0, 0)to the lower right corner
(m-1, n-1)given that you…
This blog post covers the Predict The Winner problem on Leetcode. It is a dynamic programming problem. The solution is not too hard once we know exactly what to compute.
This post digs deeper into the problem statement to break it down and see how it leads to a DP solution. It also explains the DP formulation one step at a time.
Lastly, it describes a smart trick for an O(1) solution for special cases.
You are given an integer array
n. Two players are playing a game with this array: player 1 and player 2.
This blog post covers the Bursting Balloons problem on Leetcode. It is a dynamic programming problem in which coming up with the sub-problem definition is hard.
Instead of directly explaining the solution, this post goes through the thought process of formulating the DP solution in a step-by-step manner.
You are given
nballoons, indexed from
n - 1. Each balloon is painted with a number on it represented by an array
nums. You are asked to burst all the balloons.
If you burst the
ithballoon, you will get
nums[i - 1] * nums[i] * nums[i + 1]…
Coordinate compression is a technique to map a large set of points to a smaller range by removing gaps and/or redundant information. By compressing the points to a smaller range, we can save considerable time and memory.
Most of you would have unknowingly applied 1D coordinate compression but it’s 2D coordinate compression that is extremely powerful. This blog post explains both cases.
The simplest example of coordinate compression is sorting a 1D array.
Suppose we have an array A of size N. After sorting, the element A[i] is mapped to index i. This way, elements that were in an arbitrary…