Link to question: CodeChef: Practical coding for everyone
I was able to solve the question with a worst time complexity of n^2. Either I’m missing something while calculating the time complexity or the test cases are weak.
After looking at the question it was clear that the final array would have all numbers equal to the smallest number in the array. So I found the smallest number in the array and broke the complete array into in a 2D array using the smallest number as breakpoints and adding the number of 1D array generated to the answer and now doing the same for all the 1D arrays generated again. The recursion breaks when size of array equals 1.
When I look into this method I find the worst case time complexity of this method n^2.
Test Case for worst complexity: 5 4 3 2 1 2 3 4 5