Minimum Window Sort (medium)

Problem Statement

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

Example 1:

Input: [1, 2, 5, 3, 7, 10, 9, 12]
Output: 5
Explanation: We need to sort only the subarray [5, 3, 7, 10, 9] to make the whole array sorted

Example 2:

Input: [1, 3, 2, 0, -1, 7, 10]
Output: 5
Explanation: We need to sort only the subarray [1, 3, 2, 0, -1] to make the whole array sorted

Example 3:

Input: [1, 2, 3]
Output: 0
Explanation: The array is already sorted

Example 4:

Input: [3, 2, 1]
Output: 3

.....

Like the course? Get enrolled and start learning!

adi berkowitz

· 2 years ago

I have comments in code explaining We basically traverse array left to right and then right to left

And we find the index that should begin the sort at each traversal

import math

class Solution:
  def sort(self, arr):
    left_pointer = 0
    right_pointer = len(arr)-1
    index = 0
    # Concept
    # We should traverse left to right tracking the number (left_pointer)
    # That needs to change
    while index< len(arr)-1 and left_pointer>=0:
      # left_pointer follows index until we have to set it back one
      # (take [1, 2, 5, 3, 7, 10, 9, 12] example) -> Index and left_pointer
      # Will keep increasing until index/left_ponter = 2 (5).  Next index is 3
      # This means that 5 onward needs to be sorted (for now)
      # So we move left_pointer back.
      # Now

Isabela Vlls

· 2 years ago

class Solution:
  def sort(self, arr):
    sortedVersion = sorted(arr)
    left, right = 0, len(arr)-1

    while left < len(arr) and arr[left] == sortedVersion[left]:
      left += 1
    while right >= 0 and arr[right] == sortedVersion[right]:
      right -= 1
    
    if left >= right: # if it's already sorted
      return 0

    count = right - left + 1
    return count

Mohammed Dh Abbas

· 2 years ago

import math

class Solution:
  def sort(self, arr):
    i = j = 0

    # find the first out order position element from [left to right] -->
    for count in range(len(arr)):
      if count - 1 >= 0 and arr[count] < arr[count - 1]:
        i = count - 1
        break

    # find the first out order position element from [right to left] <--
    end = i - 1 if i >= 0 else 0
    for count in range(len(arr) - 1, end, -1):  
      if count + 1 < len(arr) and arr[count] > arr[count + 1]:
        j = count + 1
        break

    # for example i and j are in the positions below
    # [-4, -2, 1, 3, 2, 9, 0, -3, 7, 10, 30]
    #             i            j      
    # find the min and max elements between i and j inclusive
    # min = -3, max = 9  == the range is out of order between [-

Abdullah AlKheshen

· 2 years ago

Fei Chen

· 2 years ago

import math

class Solution:
  def sort(self, arr):
    sorted_arr = sorted(arr)
    if sorted_arr == arr or len(arr) == 1:
      return 0
    l, r = 0, len(arr) - 1
    while l <= r:
      if arr[l] == sorted_arr[l]:      
        l+= 1
      elif arr[r] == sorted_arr[r]:     
        r -= 1
      else:
        break
    return r-l+1

Faraz Ahmed

· 3 years ago

Show 1 reply

rvadhith

· 3 years ago

Dang Nguyen

· 3 years ago

Deshapriya

· 3 years ago

public static int sort(int[] arr) {

int min = Integer.MAX_VALUE;

    int max = Integer.MIN_VALUE;

    if (arr.length == 1) return 0; 

    for (int i = 0; i < arr.length; ++i) {

        if (i == 0) {

            if (arr[i] > arr[i + 1]) {

                min = Math.min(min, arr[i]);

                max = Math.max(max, arr[i]);

            }

        } else if (i == arr.length - 1) {

            if (arr[i] < arr[i - 1]) {

                min = Math.min(min, arr[i]);

                max = Math.max(max, arr[i]);

            }

        } else {

            if (arr[i] > arr[i + 1] || arr[i] < arr[i - 1]) {

                min = Math.min(min, arr[i]);

                max = Math.max(max, arr[i]);

Mikhail Putilov

· 3 years ago

Reading Progress

Vote for new content