Leetcode Problem #84 (Hard)

Introduction

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.

Problem Statement

Imagine having rectangular blocks arranged in a straight line. Each block has a width of 1 unit and the i-th


Similar To Leetcode #503 (Medium)

Introduction

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.

Problem Statement


Leetcode Problem #1293 (Hard)

Introduction

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.

Problem Statement


Leetcode Problem #486 (Medium)

Introduction

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.

Problem Statement


Leetcode Problem #312 (Hard)

Introduction

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.

Problem Statement


Dealing with huge arrays and large numbers

Introduction

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.

Coordinate Compression In 1D

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…

Algorithms Digest

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store