algoadvance

Leetcode 485. Max Consecutive Ones

Problem Statement:

Given a binary array nums, return the maximum number of consecutive 1s in the array.

Clarifying Questions:

  1. Constraints on nums:
    • What is the length range of the array?
      • Answer: The length of nums can be between 0 and 10^5.
    • Will it only contain 0 and 1?
      • Answer: Yes, nums is a binary array.
  2. Edge Cases:
    • What should be the output if the array is empty?
      • Answer: If the array is empty, the output should be 0 since there are no 1s.

Strategy:

  1. Initialization:
    • Initialize two counters: one to keep track of the current count of consecutive 1s (currentCount), and another to store the maximum count encountered so far (maxCount).
  2. Iteration:
    • Iterate through the array:
      • If the current element is 1, increment the currentCount.
      • If the current element is 0, compare currentCount with maxCount and update maxCount if necessary. Then, reset currentCount to zero since the sequence of consecutive 1s is broken.
  3. Final Comparison:
    • After the loop, ensure to check and update maxCount one last time as the longest streak might be at the end of the array.

Time Complexity:

Code:

#include <vector>
#include <algorithm> // for the std::max function

class Solution {
public:
    int findMaxConsecutiveOnes(std::vector<int>& nums) {
        int maxCount = 0;
        int currentCount = 0;

        for(int num : nums) {
            if(num == 1) {
                currentCount++;
            } else {
                maxCount = std::max(maxCount, currentCount);
                currentCount = 0;
            }
        }

        // Final comparison in case the array ends with a sequence of 1s
        maxCount = std::max(maxCount, currentCount);

        return maxCount;
    }
};

Explanation:

  1. Initialization:
    • maxCount and currentCount are initialized to 0.
  2. Iteration:
    • For each element in the array nums, we check if it is 1. If it is, currentCount is incremented.
    • If the element is 0, this means the sequence of consecutive 1s has ended. We then update maxCount if currentCount (the length of the recent sequence) is greater than maxCount, and reset currentCount to 0.
  3. Final Check:
    • After the loop, the final maxCount is compared with currentCount once more, in case the array ended with a sequence of 1s.

This ensures that the function correctly identifies the longest sequence of consecutive 1s in the binary array nums.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI