C Exercises: Find the minimum length of subarray such that, sorting this subarray makes the whole array sorted

Last update on March 18 2025 13:20:57 (UTC/GMT +8 hours)

91. Minimum Length Subarray to Sort Array

An unsorted array of a specific size is given. Write a program in C to find the minimum length of a subarray such that sorting this subarray makes the whole array sorted.

Expected Output:
The given array is:
10 12 15 17 28 32 42 18 56 59 67
The minimum length of unsorted subarray which makes the given array sorted
lies between the indeces 4 and 7

The task is to write a C program that finds the minimum length of a subarray in an unsorted array such that sorting this subarray will make the entire array sorted. The program should determine the starting and ending indices of the smallest subarray that, when sorted, will result in the whole array being sorted. The output should display these indices.

Sample Solution:

C Code:

#include<stdio.h>

// Function to find the minimum length of an unsorted subarray
void findUnsortedSubArr (int arr1[], int arr_size) 
{ 
  int m = 0, en = arr_size-1, i, max, min;    

  // Finding the leftmost index where the unsorted part begins
  for (m = 0; m < arr_size-1; m++) 
  { 
    if (arr1[m] > arr1[m+1]) 
      break; 
  } 

  // If the array is already sorted, print it and return
  if (m == arr_size-1) 
  { 
    printf("The given array is sorted."); 
    return; 
  } 

  // Finding the rightmost index where the unsorted part ends
  for(en = arr_size - 1; en > 0; en--) 
  { 
    if(arr1[en] < arr1[en-1]) 
      break; 
  } 

  // Finding the maximum and minimum elements within the unsorted subarray
  max = arr1[m]; 
  min = arr1[m]; 
  for(i = m + 1; i <= en; i++) 
  { 
    if(arr1[i] > max) 
      max = arr1[i]; 
    if(arr1[i] < min) 
      min = arr1[i]; 
  } 

  // Adjusting the left index of the unsorted subarray
  for(i = 0; i < m; i++) 
  { 
    if(arr1[i] > min) 
    {   
      m = i; 
      break; 
    }       
  }  

  // Adjusting the right index of the unsorted subarray
  for(i = arr_size - 1; i >= en+1; i--) 
  { 
    if(arr1[i] < max) 
    { 
      en = i; 
      break; 
    }  
  } 

  // Printing the indices of the unsorted subarray
  printf("The minimum length of unsorted subarray which makes the given array sorted ");
  printf("\nlies between the indices %d and %d", m, en); 
  return; 
} 

// Main function
int main() 
{ 
  int arr1[] = {10, 12, 15, 17, 28, 32, 42, 18, 56, 59, 67}; 
  int arr_size = sizeof(arr1)/sizeof(arr1[0]); 
  int i;

  // Printing the original array
  printf("The given array is:  \n");
  for(i = 0; i < arr_size; i++)
  {
    printf("%d  ", arr1[i]);
  }
  printf("\n");

  // Calling the function to find the unsorted subarray
  findUnsortedSubArr(arr1, arr_size); 
  return 0; 
}

Output:

The given array is:  
10  12  15  17  28  32  42  18  56  59  67  
The minimum length of unsorted subarray which makes the given array sorted 
lies between the indeces 4 and 7

Visual Presentation:

Flowchart:/p>

For more Practice: Solve these Related Problems:

• Write a C program to determine the minimum subarray that, when sorted, makes the entire array sorted using two-pointer technique.
• Write a C program to find the smallest unsorted subarray using prefix and suffix comparisons.
• Write a C program to compute the boundaries of the subarray that needs sorting and then output its length.
• Write a C program to determine the minimum subarray to sort using a recursive approach to check sortedness.

C Programming Code Editor:

Click to Open Editor

Previous: Given an array of size n such that every element is in the range from 0 to n-1. Write a program in C to rearrange the given array so that arr[i] becomes arr[arr[i]].
Next: Write a program in C that checks whether the elements in an unsorted array appears consecutively or not.