Blog

The skyline problem is another famous algorithm problem using bars, like Lagest Rectangle in a Histogram. Although the problem is described using bars, it is totally another problem compared to the largest rectangle. The skyline problem asks range maximum values.

“Find the largest rectangular area in a histogram” is a famous algorithm problem using bars. There are some types of problems expressed by bars such as trapping water or skyline. Those look like similar since all are plotted on 2D plain multiple bars on. However, how to think and solve the problems are not the same. What data structure and algorithm can be applied to solve problems effectively is, sometime, confusing. For this reason, I’m going to add this topic to my memo.

This post is about XOR bit manipulations. XOR is surprisingly capable of solving various algorithm problems.

Let’s think how we can divide an array of integers into K fair amount groups. The problem description is: given an array of integers, divide into k subarrays so that the differences of sum of each subarray will be minimized. Keep the order of the given array.

Let’s count smaller on the right in an array. More precisely, the problem is: given an array of integers, count integers smaller than the index i, also, located on the right of index i. So, the answer will be also an array of the integers. Apparently, the answer to the last element is 0.