Click here to see the full article post
There is an O(n) time, O(1) space solution, which I have posted:
It is a little bit longer than others but not more complex
Your "Approach #2 Better Brute Force [Accepted]" is not accepted in fact when submitting Python code. It gets the "Time Limit Exceeded" error.
There's also a solution using TreeMap to scan array one time to find the largest right-side element that is smaller than the step value and keep record the smallest left-side element that is smaller than the step value. The running time of this algorithm is O(nlgn) and space cost is O(n)
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.