Find the largest subarray in an array whose all elements are same in O(N) time .

Question

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

1<=A[i]<=1000000

1<=N<=100000

Example :

100 200 400 10000 5 5 300

Output : 2 ( {5,5} is the largest subarray of length "2" which has all equal elements in it) .

Note :

1)Algorithm-explanation is must .

2)Adding code is optional .

3)Use Format option while adding code

Answer 1

1)

    Maintain maximum length of subarray. At the beginning it is equal to 1.

    Maintain index of begin and end of longest subarray, at the beginning it is equal to (0, 1).

    Maintain length of current subarray. At the beginning it is equal to 1.

   Iterate through array, starting from second element. If current element is equal to previous increment length of current subarray, else make it equal to 1. After it compare length of current subarray to length of maximum subarray. If current is longer, make maximum equal to current, and change indexes of begin and end of maximum subarray.

Time complexity is O(N) since you just iterate through array. Memory complexity is O(N) since answer can be as long as original array.

 

2) 

vector<int> solution(vector<int> a){

    int maximumLength = 1;

    pair<int, int> maximumSubarray(0, 1);

    int currentLength = 1;

    for(int i = 1; i < a.size(); i++){

        if(a[i] == a[i-1]){

            currentLength++;

        }else{

            currentLength = 1;

        }

        

        if(maximumLength < currentLength){

            maximumLength = currentLength;

            maximumSubarray.first = i - currentLength + 1;

            maximumSubarray.second = i + 1;

        }

    }

    vector<int> ans(maximumLength);

    for(int i = 0; i < maximumLength; ++i){

        ans[i] = a[maximumSubarray.first + i];

    }

    return ans;

}

 

Answer 2

Another but not space efficient approach is by using stack,
increment the count if top of stack is same as current element.
Downside : Space complexity O(n)


#include<bits/stdc++.h>

using namespace std;


int32_t main()

{

    vector<int> TC1 = {6,1,2,5,8,8,8,2,2,4};
    vector<int> TC2 = {1,2,3,1,2,3,1,2,3};
    vector<int> TC3 = {1,6,6,1,1,7,7,2,2};
    vector<int> a = TC3;

    stack<pair<int,int>> sk;    // element and frequency
    int ans = 0;

    for(auto i : a)
        {
            if(sk.size() and sk.top().first == i)
                sk.top().second++;
            else
                sk.push({i,1});
            ans = max(ans , sk.top().second);
        }
    cout<<"maxLen is "<<ans;
}
Interviewer will responce can you do it better, then just count conseutive same elements. and you would be selected. XD