Woodstock Blog

a tech blog for general algorithmic interview questions

[LinkedIn] Sort Part to Make Entire Array Sorted

Question

link

Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted.

Solution

The solution from gfg is definitely good, but I find this graphic explanation a really great resource.

The idea is, find min and max in the unsorted proportion, and trim the original array.

Code

not written.