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: 0
Explanation:
- 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: 3
Explanation:
- 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++
// C++ program for// the above approach#include <bits/stdc++.h>using namespace std;// Function to minimize length of// the array by removing similar// subarrays from both ends of the arrayvoid findMinLength(int arr[], int N){ // Initialize two pointers int front = 0, back = N - 1; while (front < back) { // Stores the current integer int x = arr[front]; // Check if the elements at // both ends are same or not if (arr[front] != arr[back]) break; // Move the front pointer while (arr[front] == x && front <= back) front++; // Move the rear pointer while (arr[back] == x && front <= back) back--; } // Print the minimized length of the array cout << back - front + 1 << endl;}// Driver Codeint main(){ // Input int arr[] = { 1, 1, 2, 3, 3, 1, 2, 2, 1 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call to find the // minimized length of the array findMinLength(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to minimize length of // the array by removing similar // subarrays from both ends of the array static void findMinLength(int arr[], int N) { // Initialize two pointers int front = 0, back = N - 1; while (front < back) { // Stores the current integer int x = arr[front]; // Check if the elements at // both ends are same or not if (arr[front] != arr[back]) break; // Move the front pointer while (arr[front] == x && front <= back) front++; // Move the rear pointer while (arr[back] == x && front <= back) back--; } // Print the minimized length of the array System.out.println( back - front + 1 ); } // Driver Code public static void main(String[] args) { // Input int arr[] = { 1, 1, 2, 3, 3, 1, 2, 2, 1 }; int N = arr.length; // Function call to find the // minimized length of the array findMinLength(arr, N); }}// This code is contributed by sanjoy_62. |
Python3
# Python program for# the above approach# Function to minimize length of# the array by removing similar# subarrays from both ends of the arraydef findMinLength(arr, N): # Initialize two pointers front = 0 back = N - 1 while (front < back): # Stores the current integer x = arr[front] # Check if the elements at # both ends are same or not if arr[front] != arr[back]: break # Move the front pointer while (arr[front] == x and front <= back): front += 1 # Move the rear pointer while (arr[back] == x and front <= back): back -= 1 # Print the minimized length of the array print(back - front + 1)# Driver Code# Inputarr = [1, 1, 2, 3, 3, 1, 2, 2, 1]N = len(arr)# Function call to find the# minimized length of the arrayfindMinLength(arr, N)# This code is contributed by sudhanshugupta2019a. |
C#
// C# program for the above approachusing System;public class GFG{ // Function to minimize length of // the array by removing similar // subarrays from both ends of the array static void findMinLength(int []arr, int N) { // Initialize two pointers int front = 0, back = N - 1; while (front < back) { // Stores the current integer int x = arr[front]; // Check if the elements at // both ends are same or not if (arr[front] != arr[back]) break; // Move the front pointer while (arr[front] == x && front <= back) front++; // Move the rear pointer while (arr[back] == x && front <= back) back--; } // Print the minimized length of the array Console.WriteLine( back - front + 1 ); } // Driver Code public static void Main(String[] args) { // Input int []arr = { 1, 1, 2, 3, 3, 1, 2, 2, 1 }; int N = arr.Length; // Function call to find the // minimized length of the array findMinLength(arr, N); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript program for// the above approach// Function to minimize length of// the array by removing similar// subarrays from both ends of the arrayfunction findMinLength(arr, N){ // Initialize two pointers let front = 0, back = N - 1; while (front < back) { // Stores the current integer let x = arr[front]; // Check if the elements at // both ends are same or not if (arr[front] != arr[back]) break; // Move the front pointer while (arr[front] == x && front <= back) front++; // Move the rear pointer while (arr[back] == x && front <= back) back--; } // Print the minimized length of the array document.write(back - front + 1); document.write("<br>");}// Driver Code // Input let arr = [ 1, 1, 2, 3, 3, 1, 2, 2, 1 ]; let N = arr.length; // Function call to find the // minimized length of the array findMinLength(arr, N);// This code is contributed by Surbhi Tyagi.</script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
