Minimum length Unsorted Continous subarray

user_13300548 0
Viewed 116

I am attempting this common interview problem Shortest Unsorted Continous subarray Problem statement looks like this.

Given an unsorted array A of size N. Find the subarray 0 <= s < r < N such that sorting this subarray makes the whole array sorted.

My Approach:

My idea was based on selection sort. We can traverse over the given array A choosing the elements A[i]. For every such element chosen, I tried to determine its correct position in the sorted array. For this, I compared A[i] with every A[j], such that i < j < N. But as you can see this approach took O(N*N) time complexity, but the judge expected a solution of O(N) time complexity and obviously O(1) extra space. Can anyone help me with an acceptable solution?

space-complexity time-complexity sorting arrays
1 Answers

Steps :
1) Find the first index from left and first index from right where the condition of sorted array fails i.e., A[i] > A[i+1]
2) Then find the minimum and maximum element in this range
3) If the minimum element obtained is not greater than all the elements before the considered range then, update the starting index
4) If the maximum element obtained is not lesser than all the elements after the considered range then, update the ending index
5) Starting and ending index obtained in this way will give us the correct answer

Time Complexity of this approach is O(n) and space complexity is O(1)

If u still have a doubt, you can refer this video.
Link : https://youtu.be/UfBfr-VRYOU

user_133537630
Related