Even if the input is sorted by L, I cannot find a way without sorting again or tree structures. If you do, please help me. Thanks!
Although I do not have a mathematically sound proof right now, you can rest assured that a worst-case O(N) solution does not exist for this problem. The best you can do is O(NlogN)
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.