Saturday, 23 Oct 2021

# Minimize length of an array by removing similar subarrays from both ends

Minimize length of an array by removing similar subarrays from both ends
Given an array arr[] of size N, the task is to minimize the length of the given array by repeatedly removing subarrays from the start and end of the array which consists of the same single element.
Examples:

Input: arr[] = { 3, 1, 2, 1, 1, 2, 1, 3 }Output: 0Explanation:
Since both the first and last elements are 3, removing them modifies arr[] to {1, 2, 1, 1, 2, 1}.
Since both the first and last elements are 1, removing them modifies arr[] to {2, 1, 1, 2}.
Since both the first and last elements are 2, removing them modifies arr[] to {1, 1}.
Since both the first and last elements are 1, removing them modifies arr[] to {}.
Input: arr[] = {1, 1, 2, 3, 3, 1, 2, 2, 1}Output: 3Explanation:
Removing { 1, 1 } from the start and { 1 } from the end modifies arr[] to { 2, 3, 3, 1, 2, 2 }.
Removing { 2 } from the start and { 2, 2 } from the end modifies arr[] to { 3, 3, 1 }.
No more elements can be deleted.

Approach: The idea is to use Two-Pointer technique to solve the problem. Follow the steps below to solve the problem:Initialize two pointers front = 0, back = N – 1 to traverse the array from both ends simultaneously.
Traverse the array arr[] till front < back: If both the elements are different, then break the loop. Otherwise, increment front pointer and decrement back pointer until they point to an element different from the current one. Print the difference between the position of two pointers as the minimized length of the array. Below is the implementation of the above approach: C++    #include using namespace std;    void findMinLength(int arr[], int N) {          int front = 0, back = N - 1;        while (front < back) {                     int x = arr[front];                              if (arr[front] != arr[back])             break;                     while (arr[front] == x                && front