Search code examples
algorithmsearchdata-structurespseudocode

Mineral in a Cave-Devise a O(mlogn) time complexity algorithm

*Problem: Minerals in a cave

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

Solution

  • 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)