2024-03-16 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge
|

Today I have done leetcode's March LeetCoding Challenge with cpp.

March LeetCoding Challenge 16

Description

Contiguous Array

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

 

Example 1:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Example 2:

Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

 

Constraints:

  • 1 <= nums.length <= 105
  • nums[i] is either 0 or 1.

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
public:
  int findMaxLength(vector<int>& nums) {
    int all = 0;
    int one = 0;
    int answer = 0;
    map<int, int> pos{{0, -1}};
    for(auto n : nums) {
      if(n) {
        one += 1;
      } else {
        one -= 1;
      }
      if(pos.count(one)) {
        answer = max(answer, all - pos[one]);
      } else {
        pos[one] = all;
      }
      all += 1;
    }
    return answer;
  }
};

// Accepted
// 564/564 cases passed (212 ms)
// Your runtime beats 32.57 % of cpp submissions
// Your memory usage beats 14.46 % of cpp submissions (84.3 MB)
Algorithm