*Problem: Minerals in a cave You are given a picture of a cave that is n pixels tall and m pixels wide. Each pixel is either a 0 or a 1. Each column of the picture belongs to exactly one of the following categories:

• A column is a mineral-column if every pixel in it is a 1.

• A column is a stalactite if it has both 0s and 1s, and all the ones appear above all the 0s.

• A column is a stalagmite if it has both 0s and 1s, and all the ones appear below all the 0s.

• A column is nothing if every pixel in it is a 0s.

The length of a stalactite or stalagmite is the number of 1s in that column. Given such a picture, devise a O(m log n) algorithm that outputs the following value: max(length of the longest stalactite, length of the longest stalagmite).

[Expected: Pseudocode for your algorithm and a clear English description of what your The algorithm is doing and why it is correct.]*

I am thinking pseudo code but for traversing the grid of pixel I need two loops with time complexity O(n*m) but required is O(mlogn). Any idea how to make more proficient pseudocode

CodePudding user response：

For each column:

• Check the top bottom pixels to see if it's a stalactite, stalagmite, full, or empty - O(1)
• If it's a stalactite or stalagmite, binary search to determine the length - O(log n)
• Remember the longest length found - O(1)