1493. Longest Subarray of 1's After Deleting One Element

[songyy5517]

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.

Intuition This problem is similar to the previous one where we can consider k as 1. A simple idea is to iterate over the array with a sliding window. For each element we come across, we consider it as the end of the subarray and also the rightmost element of the window. Meanwhile, we keep a left pointer to form the longest valid subarray with the current element. Then, we calclulate the window length and update the global maximum value.

[songyy5517]

Approach: Sliding Window

1. Exception handling;
2. Define variables:
   • left = 0: the leftnmost element, forming the longest subarray with the current element;
   • max_len = 0: the global maximum length;
   • k = 1: the number of zeros allowed to be in the array.
3. Iterate over the entire array: （1）If the current element is 0, decrease k by 1; （2）If k < 0， then move the left pointer to the right until the window only contains one zero. （3）Calculate the length of the current window, and update the global maximum.
4. Return the global maximum length max_len.

Complexity Analysis

• Time complexity: $O(N)$ , looping through the array once takes $O(N)$ time;
• Space complexity: $O(1)$ , just additionally define $O(1)$ - sized variables.

[songyy5517]

class Solution {
    public int longestSubarray(int[] nums) {
        // Intuition: Sliding window. this problem is similar the previous one.
        // where we can see k as 1. So this problem can also transformed
        // into finding the longest subarray including just one zero.

        // 1. Exception handling
        if (nums == null || nums.length == 1)
            return 0;

        // 2. Define variables
        int left = 0;
        int max_len = 1;
        int k = 1;

        // 3. Loop through the array
        for (int i = 0; i < nums.length; i++){
            // Update the right pointer
            if (nums[i] == 0)
                k --;

            // Update the left pointer
            while (k < 0){
                if (nums[left ++] == 0)
                    k ++;
            }

            max_len = Math.max(max_len, i - left + 1);
        }

        return max_len - 1;
    }
}

[songyy5517]

2024/5/14