Minimum Window Sort

Innoskrit August 2, 2022 Innoskrit Masterclass DSA Sheet, Two Pointers

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

Java

C++

Python

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:

Time and Space Complexity

Time Complexity: O(N)

Space Complexity: O(1)