Problem Statement

Given an array, find the length of the smallest subarray in the given array which when sorted will sort the whole array.

Example:

Input: arr: [1, 3, 2, 0, -1, 7, 10]
Output: 5
Explanation: If we sort subarray [1, 3, 2, 0, -1], the whole array will be sorted.

Code

import java.util.*;

class Innoskrit {
    
    public static int sort(int[] arr) {

        int low = 0, high = arr.length - 1;
        while(low < high && arr[low] <= arr[low + 1]) {
            low++;
        }
        
        if(low == high) return 0;
        
        while(high > 0 && arr[high] >= arr[high - 1]) {
            high--;
        }
        
        int minWindow = Integer.MAX_VALUE, maxWindow = Integer.MIN_VALUE;
        
        for(int i = low; i <= high; i++) {
            minWindow = Math.min(minWindow, arr[i]);
            maxWindow = Math.max(maxWindow, arr[i]);
        }
        
        while(low - 1 >= 0 && arr[low - 1] > minWindow) {
            low--;
        }
        
        while(high + 1 < arr.length && arr[high + 1] < maxWindow) {
            high++;
        }
        
        return (high - low + 1);
    }

    public static void main(String[] args) {
    
        int arr[] = new int[] {1, 3, 2, 0, -1, 7, 10};
        System.out.println(Innoskrit.sort(arr));

    }
}
#include<bits/stdc++.h>
using namespace std;

class Innoskrit {
    
public:
    
    static int sort(vector<int> &arr) {
        
        int low = 0, high = arr.size() - 1;
        while(low < high && arr[low] <= arr[low + 1]) {
            low++;
        }
        
        if(low == high) return 0;
        
        while(high > 0 && arr[high] >= arr[high - 1]) {
            high--;
        }
        
        int minWindow = INT_MAX, maxWindow = INT_MIN;
        
        for(int i = low; i <= high; i++) {
            minWindow = min(minWindow, arr[i]);
            maxWindow = max(maxWindow, arr[i]);
        }
        
        while(low - 1 >= 0 && arr[low - 1] > minWindow) {
            low--;
        }
        
        while(high + 1 < arr.size() && arr[high + 1] < maxWindow) {
            high++;
        }
        
        return (high - low + 1);
    }
};

int main() {

    vector<int> arr = {1, 3, 2, 0, -1, 7, 10};
    cout << Innoskrit::sort(arr);
	
}
import math

class Innoskrit:
    
    @staticmethod
    def sort(arr):
        
        low, high = 0, len(arr) - 1
        while low < high and arr[low] <= arr[low + 1]:
            low += 1
            
        if low == high:
            return 0
            
        while high > 0 and arr[high] >= arr[high - 1]:
            high -= 1
            
        min_window, max_window = math.inf, -math.inf
        
        for i in range(low, high + 1):
            min_window = min(min_window, arr[i])
            max_window = max(max_window, arr[i])
            
        while low - 1 >= 0 and arr[low - 1] > min_window:
            low -= 1
            
        while high + 1 < len(arr) and arr[high + 1] < max_window:
            high += 1
            
        return (high - low + 1)
    
    
if __name__ == '__main__':
    arr = [1, 3, 2, 0, -1, 7, 10]
    print(Innoskrit.sort(arr))

Output:

5

Time and Space Complexity

Time Complexity: O(N)

Space Complexity: O(1)