@cubefreak777 what are your thoughts on this?
Can we solve it faster than O(N^2)?
This problem essentially asks us to find if there exists a polyline with absolute slope 1 at any point which starts and ends at the same level (since the array is circular) and this property should hold for any index. Hence we can just start off from any index (the index with minimum value may be a good choice) and then try yo get make an increasing polyline as long as we can and if we canât then we just proceed with a decreasing polyline. If at any point it happens to be the case that we canât find the desired number(it shouldnât be the number with which we started the polyline)then itâs impossible otherwise we have a solution.
Itâs the most obvious thing that comes to my mind(might be terribly wrong as well as I donât have a proof of correctness), do you see any countercase to this?
2 Likes