Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1493.html

1493. Longest Subarray of 1’s After Deleting One Element (Medium)

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1's in the resulting array.

Return 0 if there is no such subarray.

 

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Example 4:

Input: nums = [1,1,0,0,1,1,1,0,1]
Output: 4

Example 5:

Input: nums = [0,0,0]
Output: 0

 

Constraints:

  • 1 <= nums.length <= 10^5
  • nums[i] is either 0 or 1.

Related Topics:
Array

Solution 1.

prev2 and prev are the indexes of the non-one values we’ve seen most recently during scanning.

prev2              prev            i
  0       1 1 1     0      1 1 1   0

If the array only contains 1, then return N - 1. Otherwise, the answer is the maximum of i - prev2 - 2.

// OJ: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int longestSubarray(vector<int>& A) {
        int N = A.size(), prev2 = -1, prev = -1, ans = 0;
        for (int i = 0; i <= N; ++i) {
            if (i < N && A[i] == 1) continue;
            if (i == N && prev == -1) return N - 1;
            if (prev != -1) ans = max(ans, i - prev2 - 2);
            prev2 = prev;
            prev = i;
        }
        return ans;
    }
};

Solution 2. Sliding Window

Sliding window [i, j) with at most 2 zeros.

  1. Keep extending the right edge until the window becomes invalid, i.e. more than one zero, or can’t be extended any more.
  2. Now cnt can be either 0, 1 or 2. The corresponding size after deleting one element is j - i - max(cnt, 1).
  3. Then we shrink the left edge until cnt becomes valid, i.e. cnt <= 1.
  4. Back to step 1 until the window reaches the end.
// OJ: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int longestSubarray(vector<int>& A) {
        int i = 0, j = 0, N = A.size(), cnt = 0, ans = 0;
        while (j < N) {
            while (j < N && cnt <= 1) cnt += A[j++] == 0;
            ans = max(ans, j - i - max(cnt, 1));
            while (cnt > 1) cnt -= A[i++] == 0;
        }
        return ans;
    }
};

Solution 3. Sliding Window

Sliding window [i, j) with at most 1 zero.

  1. Keep extending the right edge until it reaches the end or one more extension will include 2 zeros.
  2. j - i - 1 is the corresponding answer for this window.
  3. Shrink the left edge until cnt == 0.
  4. Back to step 1 until the window reaches the end.
// OJ: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int longestSubarray(vector<int>& A) {
        int i = 0, j = 0, N = A.size(), cnt = 0, ans = 0;
        while (j < N) {
            while (j < N && cnt + (A[j] == 0) <= 1) cnt += A[j++] == 0;
            ans = max(ans, j - i - 1);
            while (cnt == 1) cnt -= A[i++] == 0;
        }
        return ans;
    }
};

Solution 4. Sliding Window

Sliding window [i, j] with at most 1 zero.

  1. Keep extending the right edge.
  2. Once the cnt > 1, shrink the left edge.
  3. The size for this window with one deletion is j - i.
  4. Back to step 1 until it reaches the end.

This solution is simpler than the previous one because we don’t need to think about when to stop the extension of the right edge.

// OJ: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int longestSubarray(vector<int>& A) {
        int i = 0, j = 0, N = A.size(), cnt = 0, ans = 0;
        for (; j < N; ++j) {
            cnt += A[j] == 0;
            while (cnt > 1) cnt -= A[i++] == 0;
            ans = max(ans, j - i);
        }
        return ans;
    }
};

Solution 5. Sliding Window

Sliding window [i - ans + 1, i] with at most 1 zero that never shrinks.

// OJ: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int longestSubarray(vector<int>& A) {
        int N = A.size(), cnt = 0, ans = 0;
        for (int i = 0; i < N; ++i) {
            cnt += A[i] == 0;
            if (cnt > 1) cnt -= A[i - ans] == 0;
            else ++ans;
        }
        return ans - 1;
    }
};

Sliding window [i, j] with at most 1 zero taht never shrinks.

// OJ: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int longestSubarray(vector<int>& A) {
        int i = 0, j = 0, N = A.size(), cnt = 0;
        for (; j < N; ++j) {
            cnt += A[j] == 0;
            if (cnt > 1) cnt -= A[i++] == 0;
        }
        return j - i - 1;
    }
};

  • class Solution {
    public int longestSubarray(int[] nums) {
        int length = nums.length;
        int index = 0;
        while (index < length && nums[index] == 0)
            index++;
        if (index == length)
            return 0;
        List<Integer> ones = new ArrayList<Integer>();
        List<Integer> zeros = new ArrayList<Integer>();
        int prev = 1;
        int count = 1;
        for (int i = index + 1; i < length; i++) {
            int num = nums[i];
            if (num == prev)
                count++;
            else {
                if (prev == 1)
                    ones.add(count);
                else
                    zeros.add(count);
                prev = num;
                count = 1;
            }
        }
        if (prev == 1)
            ones.add(count);
        else
            zeros.add(count);
        if (index == 0 && zeros.size() == 0)
            return ones.get(0) - 1;
        int maxLength = ones.get(0);
        int size = ones.size();
        for (int i = 1; i < size; i++) {
            int zero = zeros.get(i - 1);
            int prevOne = ones.get(i - 1);
            int one = ones.get(i);
            maxLength = Math.max(maxLength, one);
            if (zero == 1)
                maxLength = Math.max(maxLength, prevOne + one);
        }
        return maxLength;
    }
}

############

class Solution {
    public int longestSubarray(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 1; i < n; ++i) {
            if (nums[i - 1] == 1) {
                left[i] = left[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i + 1] == 1) {
                right[i] = right[i + 1] + 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, left[i] + right[i]);
        }
        return ans;
    }
}

  • // OJ: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int longestSubarray(vector<int>& A) {
        int N = A.size(), prev2 = -1, prev = -1, ans = 0;
        for (int i = 0; i <= N; ++i) {
            if (i < N && A[i] == 1) continue;
            if (i == N && prev == -1) return N - 1;
            if (prev != -1) ans = max(ans, i - prev2 - 2);
            prev2 = prev;
            prev = i;
        }
        return ans;
    }
};

  • class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        left = [0] * n
        right = [0] * n
        for i in range(1, n):
            if nums[i - 1] == 1:
                left[i] = left[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if nums[i + 1] == 1:
                right[i] = right[i + 1] + 1
        return max(left[i] + right[i] for i in range(n))



  • func longestSubarray(nums []int) int {
	n := len(nums)
	left := make([]int, n)
	right := make([]int, n)
	for i := 1; i < n; i++ {
		if nums[i-1] == 1 {
			left[i] = left[i-1] + 1
		}
	}
	for i := n - 2; i >= 0; i-- {
		if nums[i+1] == 1 {
			right[i] = right[i+1] + 1
		}
	}
	ans := 0
	for i := 0; i < n; i++ {
		ans = max(ans, left[i]+right[i])
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

All Problems

All Solutions