Two Pointers: Given an array, return the count of smallest subarray to be removed to make the remaining array sorted

Problem Statement:

Given an array, return the count of smallest subarray to be removed to make the remaining array sorted

Example:

Input: arr = [1, 2, 3, 6, 5, 3, 4]

Output = 2

Explanation: Remove [6, 5] to make the array sorted.

Solution Explanation:

We will use 2 pointer technique to solve the problem.

Take the left pointer and increase it till the array is increasing order.

Take the right pointer and decrement it till the array is descending order.

Then will use 2 pointer to find the min number of elements to be removed in middle to form a ascending array

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>

using namespace std;

int solution(vector<int>& arr) 
{
    int n = arr.size();

    int left = 0;
    int right = n - 1;

    while (left < n - 1 && arr[left] <= arr[left + 1]) 
    {
        left++;
    }

    if (left == n - 1)
        return 0;

    while (right > 0 && arr[right] >= arr[right - 1]) 
    {
        right--;
    }

    int result = min(n - left - 1, right);
    
    int i = 0, j = right;

    while (i <= left && j < n) 
    {
        if (arr[i] <= arr[j]) 
        {
            result = min(result, j - i - 1);
            i++;
        } 
        else 
        {
            j++;
        }
    }
    return result;
}


int main()
{
    vector<int> arr  = { 1, 2, 3, 6, 5, 3, 4};

    cout << (solution(arr));
}

Output

2