Given an array arr[] of N integers, the task is to find the maximum length of sub-array consisting of the same type of element on both halves of the sub-array. Also, the elements on both halves differ from each other.
Examples:
Input: arr[] = {2, 3, 4, 4, 5, 5, 6, 7, 8, 10}
Output: 4
Explanation:
{2, 3}, {3, 4}, {4, 4, 5, 5}, {5, 6}, etc, are the valid sub-arrays where both halves have only one type of element.
{4, 4, 5, 5} is the sub-array having maximum length.
Hence, the output is 4.Input: arr[] = {1, 7, 7, 10, 10, 7, 7, 7, 8, 8, 8, 9}
Output: 6
Explanation:
{1, 7}, {7, 7, 10, 10}, {7, 7, 7, 8, 8, 8}, {8, 9}, etc, are the valid sub-arrays where both halves have only one type of element.
{7, 7, 7, 8, 8, 8} is the sub-array having maximum length.
Hence, the output is 6.
Naive Approach: The naive idea is to generate all possible subarray and check any subarray with maximum length can be divided into two halves such that all the elements in both the halves are the same.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: To solve this problem the idea is to use the concept of Prefix Sum. Follow the steps below to solve the problem:
- Traverse the array from the start in the forward direction and store the continuous occurrence of an integer for each index in an array forward[].
- Similarly, traverse the array from the end in the reverse direction and store the continuous occurrence of an integer for each index in an array backward[].
- Store the maximum of min(forward[i], backward[i+1])*2, for all the index where arr[i]!=arr[i+1].
- Print the value obtained in the above step.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that finds the maximum // length of the sub-array that // contains equal element on both // halves of sub-array void maxLengthSubArray(int A[], int N) { // To store continuous occurrence // of the element int forward[N], backward[N]; // To store continuous // forward occurrence for (int i = 0; i < N; i++) { if (i == 0 || A[i] != A[i - 1]) { forward[i] = 1; } else forward[i] = forward[i - 1] + 1; } // To store continuous // backward occurrence for (int i = N - 1; i >= 0; i--) { if (i == N - 1 || A[i] != A[i + 1]) { backward[i] = 1; } else backward[i] = backward[i + 1] + 1; } // To store the maximum length int ans = 0; // Find maximum length for (int i = 0; i < N - 1; i++) { if (A[i] != A[i + 1]) ans = max(ans, min(forward[i], backward[i + 1]) * 2); } // Print the result cout << ans; } // Driver Code int main() { // Given array int arr[] = { 1, 2, 3, 4, 4, 4, 6, 6, 6, 9 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Function Call maxLengthSubArray(arr, N); return 0; } |
Java
// Java program for the above approach class GFG{ // Function that finds the maximum // length of the sub-array that // contains equal element on both // halves of sub-array static void maxLengthSubArray(int A[], int N) { // To store continuous occurrence // of the element int forward[] = new int[N]; int backward[] = new int[N]; // To store continuous // forkward occurrence for(int i = 0; i < N; i++) { if (i == 0 || A[i] != A[i - 1]) { forward[i] = 1; } else forward[i] = forward[i - 1] + 1; } // To store continuous // backward occurrence for(int i = N - 1; i >= 0; i--) { if (i == N - 1 || A[i] != A[i + 1]) { backward[i] = 1; } else backward[i] = backward[i + 1] + 1; } // To store the maximum length int ans = 0; // Find maximum length for(int i = 0; i < N - 1; i++) { if (A[i] != A[i + 1]) ans = Math.max(ans, Math.min(forward[i], backward[i + 1]) * 2); } // Print the result System.out.println(ans); } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 1, 2, 3, 4, 4, 4, 6, 6, 6, 9 }; // Size of the array int N = arr.length; // Function call maxLengthSubArray(arr, N); } }// This code is contributed by rutvik_56 |
Python3
# Python3 program for the above approach # Function that finds the maximum # length of the sub-array that # contains equal element on both # halves of sub-array def maxLengthSubArray(A, N): # To store continuous occurrence # of the element forward = [0] * N backward = [0] * N # To store continuous # forward occurrence for i in range(N): if i == 0 or A[i] != A[i - 1]: forward[i] = 1 else: forward[i] = forward[i - 1] + 1 # To store continuous # backward occurrence for i in range(N - 1, -1, -1): if i == N - 1 or A[i] != A[i + 1]: backward[i] = 1 else: backward[i] = backward[i + 1] + 1 # To store the maximum length ans = 0 # Find maximum length for i in range(N - 1): if (A[i] != A[i + 1]): ans = max(ans, min(forward[i], backward[i + 1]) * 2); # Print the result print(ans) # Driver Code # Given array arr = [ 1, 2, 3, 4, 4, 4, 6, 6, 6, 9 ] # Size of the array N = len(arr) # Function call maxLengthSubArray(arr, N) # This code is contributed by yatinagg |
C#
// C# program for the above approach using System;class GFG{ // Function that finds the maximum // length of the sub-array that // contains equal element on both // halves of sub-array static void maxLengthSubArray(int []A, int N) { // To store continuous occurrence // of the element int []forward = new int[N]; int []backward = new int[N]; // To store continuous // forkward occurrence for(int i = 0; i < N; i++) { if (i == 0 || A[i] != A[i - 1]) { forward[i] = 1; } else forward[i] = forward[i - 1] + 1; } // To store continuous // backward occurrence for(int i = N - 1; i >= 0; i--) { if (i == N - 1 || A[i] != A[i + 1]) { backward[i] = 1; } else backward[i] = backward[i + 1] + 1; } // To store the maximum length int ans = 0; // Find maximum length for(int i = 0; i < N - 1; i++) { if (A[i] != A[i + 1]) ans = Math.Max(ans, Math.Min(forward[i], backward[i + 1]) * 2); } // Print the result Console.WriteLine(ans); } // Driver Code public static void Main(String[] args) { // Given array int []arr = { 1, 2, 3, 4, 4, 4, 6, 6, 6, 9 }; // Size of the array int N = arr.Length; // Function call maxLengthSubArray(arr, N); } }// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program for the above approach// Function that finds the maximum // length of the sub-array that // contains equal element on both // halves of sub-array function maxLengthSubArray(A, N) { // To store continuous occurrence // of the element let forward = Array.from({length: N}, (_, i) => 0); let backward = Array.from({length: N}, (_, i) => 0); // To store continuous // forkward occurrence for(let i = 0; i < N; i++) { if (i == 0 || A[i] != A[i - 1]) { forward[i] = 1; } else forward[i] = forward[i - 1] + 1; } // To store continuous // backward occurrence for(let i = N - 1; i >= 0; i--) { if (i == N - 1 || A[i] != A[i + 1]) { backward[i] = 1; } else backward[i] = backward[i + 1] + 1; } // To store the maximum length let ans = 0; // Find maximum length for(let i = 0; i < N - 1; i++) { if (A[i] != A[i + 1]) ans = Math.max(ans, Math.min(forward[i], backward[i + 1]) * 2); } // Print the result document.write(ans); } // Driver Code // Given array let arr = [ 1, 2, 3, 4, 4, 4, 6, 6, 6, 9 ]; // Size of the array let N = arr.length; // Function call maxLengthSubArray(arr, N); </script> |
Output:
6
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
