Minimum unsorted subarray.

You are given an unsorted array, you need to find the minimum length of subarray sorting which the whole array becomes sorted. Return the starting and ending indices of the subarray.

Sample Input - {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60}
Expected Output - 3 to 8
Explanation - Subarray starting at index 3 and ending at index 8 that is {30, 25, 40, 32, 31, 35}, if sorted makes the whole array sorted.

Algorithm

The problem can be solved in two steps.

  1. Find the candidate unsorted subarray.
    Start scanning the array from left to right. Find the first element that is greater then the next element. Let the index of such an element be s.
    Start scanning from right to left. Find the first element which is smaller than the next element (right to left order). Let e be the index of such an element.
  2. Check whether sorting this subarray, makes the array sorted or not. If not, include more elements.
    Find the minimum and maximum element in the candidate subarray. Then find the first element in subarray [0…(s-1)] which is greater than the minimum element in the candidate subarray and change s to this index. If no such element is found, then continue.
    Find the last element in subarray [(e+1) to (n-1)] which is smaller than the maximum element in the candidate subarray and change e to that index. If no such element is found, continue.
  3. Return s and e.
#include <bits/stdc++.h>
using namespace std;

void helper(vector<int> nums, int n){
	int s =0, e=0;
	for(int i=0; i<n-1; i++){
		if(nums[i]>nums[i+1]){
			s=i;
			break;
		}
	}
	for(int i=n-1; i>0; i--){
		if(nums[i]<nums[i-1]){
			e=i;
			break;
		}
	}
	int min_ = INT_MAX;
	int max_ = INT_MIN;
	for(int i=s; i<=e; i++){
		if(nums[i]<min_){
			min_ = nums[i];
		}
		if(nums[i]>max_){
			max_ = nums[i];
		}
	}
	for(int i=0; i<s; i++){
		if(nums[i]>min_){
			s=i;
			break;
		}
	}
	for(int i=n-1; i>e; i--){
		if(nums[i]<max_){
			e = i;
			break;
		}
	}
	cout<<s<<" to "<<e;
}

int main(){
	vector<int> nums = {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60}; 
	helper(nums, nums.size());
	return 0;
}

Also, check another popular interview problem Symmetric Tree (Mirror image of itself).

One comment

Leave a Reply

Your email address will not be published.