How to find the largest subarray in an array with same first and last elements efficiently ?

Question

Expected Time Complexity : O(N) , where 'N'  is the size of array .

1<=A[i]<=1000000

1<=N<=1000000

Example :

5

1 2 3 2 4

Output : 3  ({2,3,2} is the largest subarray whose first and last elements are the same)

Answer 1

For each number in the array , we need to know its first occurrence in the array and the last occurence in the array . We will store the first occurrence of every element in hashmap(or array) a1 and last occurrence of every element in hashmap(or array) b1 . 

Example : 

5 6 5 2 2 6 7 7 

Position of first occurrence of 5 : 1 

Position of last occurrence of 5 : 3 

Possible length = (3-1) = 2 . 

Similarly, we do for numbers : 6,2,7 and find the maximum of all possible lengths . 

Code : 

#include <bits/stdc++.h>
using namespace std;
int a1[1000000+10];
int b1[1000000+9];
int main() 
{
    
     int n ; 
     cin>>n ; 
     int a[n] ; 
     int i = 0 ;
     while(i<n)
     {
         cin>>a[i];
         b1[a[i]]=i ; 
         i++;
     }
    
     i = n - 1  ;
     while(i>=0)
     {
         a1[a[i]]=i ; 
         i--;
     }
     int maxi = -1 ; 
     i=1;
     while(i<=1000000)
     {
         int possible = abs(a1[i]-b1[i]) + 1 ; 
         maxi = max(maxi,possible);
         i++;
     }
     cout<<maxi ; 
    return 0;
}

Answer 2

We check the first and last pointer placed at first position and last position respectively then we make condition that if first position element is less than or equal to Last position element than we print the subarray and that will be our longest subarray, else we can shift the first position by 1 forward and last position by 1 backwards and then again check and print.

Optimal solution : Can be to use unordered maping

We store the first and last in unordered amp differently and check the difference in both the elements should be maximum.

Answer 3

Approach:

Used hashmap of Integer and list in order to save the elements along with the index value it has occurred in the array

time complexity of the below solution is O(n)

Answer 4

// Time complexity O(n)

//space complexity O(n)

// Just use 2 maps to store the location of first and last occurence of an element

 

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,y,mx=-1;
    cin>>n;
    map<long long,long long> x,z;
    
    for(long long i=0;i<n;i++)
    {
        cin>>y;
        if(x.find(y)!=x.end())
        {    
            z[y]=i;
            
            mx=max(mx,z[y]-x[y]);
        }
        else
        {
            x[y]=i;
            
        }
    }
    cout<<mx+1;
    return 0;
}

Answer 5

Its an nlogn time and O(n) space solution,

We would make a new vector of pairs in which we store elements along with their indices and then sort it in increasing order and if elements are same we sort it in increasing order of indices . This can be done in nlogn using sort function in c++ or making a merge sort function .Now all the same elements would come together and form a subarray Now the question transforms to get the longest subarray with same elements and find the difference between the indices of first and last element as that will give the longest subarray starting and ending with that particular element . and finally update the answer if new max is found. This process can be easily done using 2 pointer. Please like if you understand the solution and for further any doubts you can ping me on telegram or comment here I will surely see to it that doubt is cleared.

Comments

Hey , can you add your name so people know, who you are ?