Day 26: LeetCode 30 Day May Challenges

Contigious_Binary_array.cpp

class Solution {
public:
    /*bool Areequal(string s){
    int z=0,v=0;
    for(auto x : s){
        if(x == '0')
            z++;
        else
            v++;
    }
    //cout<<"z : "<<z<<" v : "<<v;
    if(z==v)
        return true;
    else
        return false;    
}

int findMaxLength(vector<int> &nums)
{
    int n = nums.size();
    string s;
    for (int x : nums)
    {
        s = s + to_string(x);
    }
    //cout<<s;
    int m = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = n-i; j > 0; j--)
        {
            if(Areequal(s.substr(i,j))){
                m = max(m,j);
            }
        }
    }
    return m;
}
*/

/**Gives TLE
O(n*n)
int findMaxLength(vector<int> &nums){
    int m = 0;
    int n = nums.size();
    for(int i=0; i<n-1; i++){
        int z = 0,v =0;
        for(int j=i; j<n; j++){
            if(nums[j]==0)
                z++;
            else
                v++;
            if(z==v)
                m = max(m,2*z);  
        }
    }
    return m;
*/
  //O(n)
  int findMaxLength(vector<int>& nums){
        int n = nums.size();
        int c = 0,len=0;
        unordered_map<int,int> m;
        for(int i=0; i<n; i++){
            if(nums[i]==0)
                c++;
            else
                c--;
            if(c==0)
                len = max(len,i+1);
            else if(m.find(c)!=m.end()){
                //if once c reached prev value means in b/w contains equal 0 and 1;range gives the length. 
                len = max(len,i-m[c]);
            }
            //insert index value for non zero count 'c'
            else
                m[c] = i;
        }
        return len;
    }
};

Problem_statement26.txt

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
Example 2:
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Note: The length of the given binary array will not exceed 50,000