Description
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.
Constraints:
1 <= nums.length <= 105nums[i] is either 0 or 1.
Solutions
Solution 1: Enumeration
We can enumerate each position i to be deleted, then calculate the number of consecutive 1s on the left and right, and finally take the maximum value.
Specifically, we use two arrays left and right of length n+1, where left[i] represents the number of consecutive 1s ending with nums[i-1], and right[i] represents the number of consecutive 1s starting with nums[i].
The final answer is max_{0 ≤ i < n} {left[i] + right[i+1]}.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
PythonJavaC++GoTypeScriptRust
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
n = len(nums)
left = [0] * (n + 1)
right = [0] * (n + 1)
for i, x in enumerate(nums, 1):
if x:
left[i] = left[i - 1] + 1
for i in range(n - 1, -1, -1):
if nums[i]:
right[i] = right[i + 1] + 1
return max(left[i] + right[i + 1] for i in range(n))(code-box)
class Solution {
public int longestSubarray(int[] nums) {
int n = nums.length;
int[] left = new int[n + 1];
int[] right = new int[n + 1];
for (int i = 1; i <= n; ++i) {
if (nums[i - 1] == 1) {
left[i] = left[i - 1] + 1;
}
}
for (int i = n - 1; i >= 0; --i) {
if (nums[i] == 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 + 1]);
}
return ans;
}
}(code-box)
class Solution {
public:
int longestSubarray(vector<int>& nums) {
int n = nums.size();
vector<int> left(n + 1);
vector<int> right(n + 1);
for (int i = 1; i <= n; ++i) {
if (nums[i - 1]) {
left[i] = left[i - 1] + 1;
}
}
for (int i = n - 1; ~i; --i) {
if (nums[i]) {
right[i] = right[i + 1] + 1;
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, left[i] + right[i + 1]);
}
return ans;
}
};(code-box)
func longestSubarray(nums []int) (ans int) {
n := len(nums)
left := make([]int, n+1)
right := make([]int, n+1)
for i := 1; i <= n; i++ {
if nums[i-1] == 1 {
left[i] = left[i-1] + 1
}
}
for i := n - 1; i >= 0; i-- {
if nums[i] == 1 {
right[i] = right[i+1] + 1
}
}
for i := 0; i < n; i++ {
ans = max(ans, left[i]+right[i+1])
}
return
}(code-box)
function longestSubarray(nums: number[]): number {
const n = nums.length;
const left: number[] = Array(n + 1).fill(0);
const right: number[] = Array(n + 1).fill(0);
for (let i = 1; i <= n; ++i) {
if (nums[i - 1]) {
left[i] = left[i - 1] + 1;
}
}
for (let i = n - 1; ~i; --i) {
if (nums[i]) {
right[i] = right[i + 1] + 1;
}
}
let ans = 0;
for (let i = 0; i < n; ++i) {
ans = Math.max(ans, left[i] + right[i + 1]);
}
return ans;
}(code-box)
impl Solution {
pub fn longest_subarray(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut left = vec![0; n + 1];
let mut right = vec![0; n + 1];
for i in 1..=n {
if nums[i - 1] == 1 {
left[i] = left[i - 1] + 1;
}
}
for i in (0..n).rev() {
if nums[i] == 1 {
right[i] = right[i + 1] + 1;
}
}
let mut ans = 0;
for i in 0..n {
ans = ans.max(left[i] + right[i + 1]);
}
ans as i32
}
}(code-box)
Solution 2: Two Pointers
The problem is actually asking us to find the longest subarray that contains at most one 0. The remaining length after deleting one element from this subarray is the answer.
Therefore, we can use two pointers j and i to point to the left and right boundaries of the subarray, initially j = 0, i = 0. In addition, we use a variable cnt to record the number of 0s in the subarray.
Next, we move the right pointer i. If nums[i] = 0, then cnt is incremented by 1. When cnt > 1, we need to move the left pointer j until cnt ≤ 1. Then, we update the answer, i.e., ans = max(ans, i - j). Continue to move the right pointer i until i reaches the end of the array.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
PythonJavaC++GoTypeScriptRust
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
ans = 0
cnt = j = 0
for i, x in enumerate(nums):
cnt += x ^ 1
while cnt > 1:
cnt -= nums[j] ^ 1
j += 1
ans = max(ans, i - j)
return ans(code-box)
class Solution {
public int longestSubarray(int[] nums) {
int ans = 0, n = nums.length;
for (int i = 0, j = 0, cnt = 0; i < n; ++i) {
cnt += nums[i] ^ 1;
while (cnt > 1) {
cnt -= nums[j++] ^ 1;
}
ans = Math.max(ans, i - j);
}
return ans;
}
}(code-box)
class Solution {
public:
int longestSubarray(vector<int>& nums) {
int ans = 0, n = nums.size();
for (int i = 0, j = 0, cnt = 0; i < n; ++i) {
cnt += nums[i] ^ 1;
while (cnt > 1) {
cnt -= nums[j++] ^ 1;
}
ans = max(ans, i - j);
}
return ans;
}
};(code-box)
func longestSubarray(nums []int) (ans int) {
cnt, j := 0, 0
for i, x := range nums {
cnt += x ^ 1
for ; cnt > 1; j++ {
cnt -= nums[j] ^ 1
}
ans = max(ans, i-j)
}
return
}(code-box)
function longestSubarray(nums: number[]): number {
let [ans, cnt, j] = [0, 0, 0];
for (let i = 0; i < nums.length; ++i) {
cnt += nums[i] ^ 1;
while (cnt > 1) {
cnt -= nums[j++] ^ 1;
}
ans = Math.max(ans, i - j);
}
return ans;
}(code-box)
impl Solution {
pub fn longest_subarray(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut ans = 0;
let mut j = 0;
let mut cnt = 0;
for i in 0..n {
cnt += nums[i] ^ 1;
while cnt > 1 {
cnt -= nums[j] ^ 1;
j += 1;
}
ans = ans.max(i - j);
}
ans as i32
}
}(code-box)
Solution 3: Two Pointers (Optimization)
In Solution 2, we move the left pointer in a loop until cnt ≤ 1. Since the problem asks for the longest subarray, it means we don't need to reduce the length of the subarray. Therefore, if cnt \gt 1, we only move the left pointer once, and the right pointer continues to move to the right. This ensures that the length of the subarray does not decrease.
Finally, the answer we return is n - l - 1, where l is the position of the left pointer.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
PythonJavaC++GoTypeScriptRust
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
cnt = l = 0
for x in nums:
cnt += x ^ 1
if cnt > 1:
cnt -= nums[l] ^ 1
l += 1
return len(nums) - l - 1(code-box)
class Solution {
public int longestSubarray(int[] nums) {
int cnt = 0, l = 0;
for (int x : nums) {
cnt += x ^ 1;
if (cnt > 1) {
cnt -= nums[l++] ^ 1;
}
}
return nums.length - l - 1;
}
}(code-box)
class Solution {
public:
int longestSubarray(vector<int>& nums) {
int cnt = 0, l = 0;
for (int x : nums) {
cnt += x ^ 1;
if (cnt > 1) {
cnt -= nums[l++] ^ 1;
}
}
return nums.size() - l - 1;
}
};(code-box)
func longestSubarray(nums []int) int {
cnt, l := 0, 0
for _, x := range nums {
cnt += x ^ 1
if cnt > 1 {
cnt -= nums[l] ^ 1
l++
}
}
return len(nums) - l - 1
}(code-box)
function longestSubarray(nums: number[]): number {
let [cnt, l] = [0, 0];
for (const x of nums) {
cnt += x ^ 1;
if (cnt > 1) {
cnt -= nums[l++] ^ 1;
}
}
return nums.length - l - 1;
}(code-box)
impl Solution {
pub fn longest_subarray(nums: Vec<i32>) -> i32 {
let mut cnt = 0;
let mut l = 0;
for &x in &nums {
cnt += x ^ 1;
if cnt > 1 {
cnt -= nums[l] ^ 1;
l += 1;
}
}
(nums.len() - l - 1) as i32
}
}(code-box)
