Longest Subarray of 1's After Deleting One Element

The task is to find the length of the longest contiguous subarray consisting only of 1s after removing one element from the given binary array.

Example 1:

Example 1:
Input: [1,1,0,1]
Output: 3
Explanation: After removing the element at index 2 (which is 0), the longest subarray with only 1s is [1,1,1], which has a length of 3.

Example 2:

Example 2:
Input: [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After removing the element at index 4 (which is 0), the longest subarray with only 1s is [1,1,1,1,1], which has a length of 5.

Example 2:

Example 3:
Input: [1,1,1]
Output: 2
Explanation: Since there's only one element to remove, the resulting array will have two 1s, and the length of the longest subarray with only 1s will be 2.

Constraints:

- The length of the input array is between 1 and 105.

- Each element in the array is either 0 or 1.

Java implementation:

public int longestSubarray(int[] nums) {
		int n = nums.length;
		int right = 0;
		int left = 0;
		Map<Integer, Integer> map = new HashMap<>();

		int maxLen = 0;

		for (int i = 0; i < n; i++) {
			map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
		}

		if (map.size() == 1 && map.getOrDefault(0, 0) == 0) {
			return n - 1;
		} else if (map.size() == 1 && map.getOrDefault(1, 0) == 0) {
			return 0;
		}
		map.clear();

		while (right < n) {
			map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);

			while (map.getOrDefault(0, 0) > 1) {
				if (map.get(nums[left]) == 1) {
					map.remove(nums[left]);
				} else {
					map.put(nums[left], map.get(nums[left]) - 1);
				}
				left++;
				maxLen = Math.max(maxLen, right - left + 1);
			}

			if (map.getOrDefault(0, 0) == 1) {
				maxLen = Math.max(maxLen, right - left + 1);
			}

			right++;
		}

		return maxLen - 1;
	}

1. Initialization: Initialize variables `n`, `right`, `left`, `map`, and `maxLen`.

2. Count Occurrences: Iterate through the `nums` array and count the occurrences of each element using a HashMap `map`.

3. Handle Edge Cases: If there's only one distinct element and it's either all 0s or all 1s, handle those cases separately.

4. Sliding Window Approach: Use a sliding window approach to find the longest subarray containing only 1s after removing one element.

   - Expand the window by incrementing `right` until the condition is met.

   - Shrink the window by incrementing `left` until the condition is met.

   - Update `maxLen` accordingly.

5. Return Result: Return `maxLen - 1`.

C++ implementation:

#include <vector>
using namespace std;

#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n = nums.size();
        int right = 0;
        int left = 0;
        unordered_map<int, int> map;

        int maxLen = 0;

        for (int i = 0; i < n; i++) {
            map[nums[i]]++;
        }

        if (map.size() == 1 && map.count(0) == 0) {
            return n - 1;
        } else if (map.size() == 1 && map.count(1) == 0) {
            return 0;
        }
        map.clear();

        while (right < n) {
            map[nums[right]]++;

            while (map[0] > 1) {
                if (map[nums[left]] == 1) {
                    map.erase(nums[left]);
                } else {
                    map[nums[left]]--;
                }
                left++;
                maxLen = max(maxLen, right - left + 1);
            }

            if (map[0] == 1) {
                maxLen = max(maxLen, right - left + 1);
            }

            right++;
        }

        return maxLen - 1;
    }
};

Python implementation:

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        right = 0
        left = 0
        map = {}

        maxLen = 0

        for i in range(n):
            map[nums[i]] = map.get(nums[i], 0) + 1

        if len(map) == 1 and map.get(0, 0) == 0:
            return n - 1
        elif len(map) == 1 and map.get(1, 0) == 0:
            return 0
        map.clear()

        while right < n:
            map[nums[right]] = map.get(nums[right], 0) + 1

            while map.get(0, 0) > 1:
                if map[nums[left]] == 1:
                    del map[nums[left]]
                else:
                    map[nums[left]] -= 1
                left += 1
                maxLen = max(maxLen, right - left + 1)

            if map.get(0, 0) == 1:
                maxLen = max(maxLen, right - left + 1)

            right += 1

        return maxLen - 1