https://algo.monster/problems/google_oa_min_decreasing_partitions
1 Like
Can someone give me a small explanation of what is being done in the proposed solution? Thanks.
1 Like
i guess we start for end , and try making buckets, we add an element to a bucket is top is smaller than arr[i] , else we make a new bucket, we can easily find the required bucket using binary search.
How can we use binary search here if the arrays are not sorted? Also, could we get more explanation about how they went from the problem statement to using a this bisect method?
I think it might be possible to solve this problem as a variant on finding the Longest Increasing Subsequence.
The minimum number of partitions should be discoverable by eliminating the longest decreasing subsequence until all values have been used. One could keep track of state with an array booleans, “used,” and perhaps a count that eventually signifies all values have been exhausted.
I should say that the solution above is very clean, but I like to be able to tie some of these problems back to those base patterns covered in the main coursework…