The solution uses O(n) to decompose the input array into an array of increasing arrays, and then uses O(k) to merge them. Isn’t that not the problem asks for - O(k) additional storage? Instead we could do in place reversal of the decreasing subarrays and then record the start and end of each increasing subarray, and then do the merge. Space is still O(k). Thoughts?
Question about 11.2 in 1.4.7
Hey Ray,
This is a very good question. To be honest, the reason I create those increasing sorted arrays is due to the function signature of MergeArrays(). Of course you can circumvent that by creating a vector wrapper which doesn’t store those elements but accesses elements according to its trend. Your way is also implicitly use O(n) storage, and personally I probably will remove this constraint in the future.
0 Likes