Grokking 75: Top Coding Interview Questions

0% completed

​

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!
P

Pratheek Sankeshi

· 4 years ago

how do u get the intuition to do this?

Show 2 replies
M

Mikhail Putilov

· 3 years ago

Why is it medium? It is impossible to come up with a solution O(n) in a reasonable time...

Dang Nguyen

Dang Nguyen

· 2 years ago

[22, 34, 59, 60, 75, 76, 81] fails because it expects 1 during submission, but when I run it before submission it expects 0.

R

rvadhith

· 2 years ago

Actual answer is 0. Submission is expecting 1.

J

J

· 4 years ago

Python 3 solution fails on LC equivalent 581. Shortest Unsorted Continuous Subarray due to edge case [1,3,2,4,5].

Show 1 reply
J

Jharol Rivera

· 4 years ago

subarray_max = -math.inf subarray_min = math.inf for k in range(low, high+1): subarray_max = max(subarray_max, arr[k]) subarray_min = min(subarray_min, arr[k])

is it possible to reduce this part to this?

subarray_max = max(arr[low:high+1]) subarray_min = min(arr[low:high+1])

Show 2 replies
I

Ike Nwankwo

· 3 years ago

def shortest_window_sort(arr): if len(arr) < 2: return 0

start,end= -1,-2 high_num = arr[0] for i in range(1,len(arr)): if arr[i] >= high_num: high_num = arr[i] else: start = i - 1 if start == -1 else start while start > 0 and arr[i] < arr[start - 1]: start -=1 end = i return end-start+1

this is my solution. This is also O(N) correct?

Deshapriya

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]);
Faraz Ahmed

Faraz Ahmed

· 2 years ago

i have dry run it multiple times, iam getting 6 as the size of subarray window? i think visualization of algorithm is misleading , if you dry run the first input based on the visualization of algorithm you get 6 as the size of subarray!

i might be wrong, but i have dry run it twice, what you guys think???

i think the problem is here:     while (low > 0 && arr[low - 1] > subarrayMin) {       low -= 1;     }     // extend the subarray to include any number which is smaller than the maximum of     // the subarray     while (high < arr.length - 1 && arr[high + 1] < subarrayMax) {       high += 1;     }

While in visualization it compares arr[min] > subarray_min ? then low-- , to insert from beginning

the min and max i found in subarray 👇 min=3 max=10

the first inorder from beginning

Show 1 reply
Fei Chen

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