Last active
May 27, 2020 10:55
-
-
Save Gowtham-369/63368c2c3f8b7cc6adcddff194f9738a to your computer and use it in GitHub Desktop.
Day 26: LeetCode 30 Day May Challenges
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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; | |
| } | |
| }; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment