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

MediumArrayDynamic ProgrammingSliding Window
Leetcode Link

Problem Description

The problem presents a binary array nums, comprised of 0s and 1s. The task is to find the size of the largest contiguous subarray of 1s that could be obtained by removing exactly one element from the array. You are also informed that if there is no such subarray made up entirely of 1s after removing an element, the function should return 0.

Intuition

The intuition for solving this problem involves looking at each segment of 1s as a potential candidate and checking the length we can obtain after removing an element. We want to maximize this length by strategically picking an element for removal. The key insight here is that if there are consecutive 1s, removing one 1 does not impact the length of the subarray of 1s on either side of it.

We can approach the solution by precomputing and storing the lengths of continuous 1s at any index from the left and right directions separately. This is done in two linear scans using the left and right auxiliary arrays:

  1. From Left to Right: Starting at the index 1, if the previous element is 1, increment the value in the left array at the current index by 1 plus the value at the previous index. This will give us the number of continuous 1s to the left of each index in the array nums.

  2. From Right to Left: Starting from the second to last index and going backwards, if the next element is 1, increment the value in the right array at the current index by 1 plus the value at the next index. This gives the number of continuous 1s to the right of each index.

The final result, after having populated both left and right arrays, is the maximum sum of corresponding elements from left and right arrays across all indices. This effectively simulates the removal of one element (either a 1 or 0) and joining the contiguous 1s from both left and right sides. However, the result should be the length after the removal of one element, so another -1 is implicitly considered in the max operation [since we don't actually remove the element but calculate what the length would be as if we did].

By applying this method, we can find the longest subarray containing only 1s after deleting exactly one element.

Learn more about Dynamic Programming and Sliding Window patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The solution to this problem relies primarily on dynamic programming to keep track of the length of continuous 1s on both sides of each index in the array nums.

Here is a breakdown of the implementation details:

  1. Initialization: Two lists, left and right, each of the same length as nums, are created and initialized with zeroes. These lists will store the length of continuous 1s to the left and right of each index, respectively.

  2. Populating the left list: We start iterating over the array nums from the second element onwards (index 1 because we consider 0 as the base case which is already initialized to zero). For each index i, if the element at the previous index (i - 1) is 1, we set left[i] to left[i - 1] + 1. Effectively, this records the length of a stretch of 1s ending at the current index.

  3. Populating the right list: We do a similar iteration, but this time from right to left, starting from the second-to-last element (index n - 2 where n is the length of nums). For each index i, if the element at the next index (i + 1) is 1, we set right[i] to right[i + 1] + 1. This captures the length of a stretch of 1s starting right after the current index.

  4. Finding the longest subarray: Once we have both left and right lists populated, we iterate over all possible remove positions (these positions do not have to be 1; they can be 0 as well, as we will merge stretches of 1s around them). For each index, we calculate the sum of left[i] + right[i], which approximates the length of the subarray of 1s if we removed the element at the current index. However, since we are supposed to actually remove an element to create the longest subsequence, the sum implicitly considers this by not adding an additional 1 even though we are summing the lengths from both sides.

  5. Returning the result: The maximum value from these sums corresponds to the size of the longest subarray containing only 1s after one deletion. This is found using the max() function applied to the sums of left[i] + right[i] for each index i.

The algorithm completes this in linear time with two passes through nums, and the space complexity is governed by the two additional arrays left and right, which are linear in the size of the input array nums.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Example Walkthrough

Let's use an example to illustrate the solution approach.

Suppose the input binary array nums is [1, 1, 0, 1, 1, 1, 0, 1, 1].

Step by Step Solution

  1. Initialization:
    We initialize two lists, left and right, with the same length as nums.
    left: [0, 0, 0, 0, 0, 0, 0, 0, 0]
    right: [0, 0, 0, 0, 0, 0, 0, 0, 0]

  2. Populating the left list:
    We iterate from left to right over the array nums, starting from index 1.

    • nums[1] is 1, and nums[0] is 1, so left[1] = left[0] + 1 -> 0 + 1 = 1.
    • As we continue, left becomes [0, 1, 0, 1, 2, 3, 0, 1, 2].

  3. Populating the right list:
    Iterating from right to left, starting from index 7.

    • nums[7] is 1, and nums[8] is 1, so right[7] = right[8] + 1 -> 0 + 1 = 1.
    • Continuing this process, the right list fills up as [2, 1, 0, 4, 3, 2, 0, 1, 0].

  4. Finding the longest subarray:
    We calculate the potential longest subarrays after a deletion for each index, by summing the left and right values at each index.

    • At index 2 (the first 0), the sum is left[2] + right[2] = 0 + 0 = 0.
    • At index 6 (the second 0), the sum is left[6] + right[6] = 3 + 0 = 3.
    • The longest subarray occurs at either index 2 or 6, where we would be removing the 0 to join the 1s.
    • Considering every index, we would have sums as [2, 1, 4, 5, 3, 2, 4, 1, 2].

  5. Returning the result:
    The maximum value from the sum of left and right for all indexes gives us the result.
    In this case, the maximum is 5, corresponding to index 3. Thus, the size of the longest subarray containing only 1s after one deletion is 5.

This approach allows us to solve the problem with a single pass for left and another for right, totaling linear time complexity, O(n), with n being the number of elements in nums. The use of the two lists left and right gives us a space complexity of O(n) as well.

Solution Implementation

1from typing import List
2
3class Solution:
4    def longestSubarray(self, nums: List[int]) -> int:
5        # Determine the length of the nums list
6        n = len(nums)
7
8        # Initialize two lists to keep track of consecutive ones to the left and right of each index
9        left_ones_count = [0] * n
10        right_ones_count = [0] * n
11
12        # Calculate the consecutive ones to the left of each index
13        for i in range(1, n):
14            if nums[i - 1] == 1:
15                left_ones_count[i] = left_ones_count[i - 1] + 1
16
17        # Calculate the consecutive ones to the right of each index
18        for i in range(n - 2, -1, -1):
19            if nums[i + 1] == 1:
20                right_ones_count[i] = right_ones_count[i + 1] + 1
21
22        # Find the maximum length subarray formed by summing up counts of left and right ones.
23        # Note that the question assumes we can remove one zero to maximize the length.
24        # So, connecting two streaks of ones effectively means removing one zero between them.
25        max_length = max(a + b for a, b in zip(left_ones_count, right_ones_count))
26
27        return max_length
28
1class Solution {
2
3    // Function to find the length of the longest subarray consisting of 1s after deleting exactly one element.
4    public int longestSubarray(int[] nums) {
5        int length = nums.length;
6
7        // Arrays to store the count of consecutive 1s to the left and right of each index in nums
8        int[] leftOnesCount = new int[length];
9        int[] rightOnesCount = new int[length];
10
11        // Count consecutive 1s from left to right, starting from the second element
12        for (int i = 1; i < length; ++i) {
13            if (nums[i - 1] == 1) {
14                // If the previous element is 1, increment the count
15                leftOnesCount[i] = leftOnesCount[i - 1] + 1; 
16            }
17        }
18
19        // Count consecutive 1s from right to left, starting from the second-to-last element
20        for (int i = length - 2; i >= 0; --i) {
21            if (nums[i + 1] == 1) {
22                // If the next element is 1, increment the count
23                rightOnesCount[i] = rightOnesCount[i + 1] + 1;
24            }
25        }
26
27        // Variable to store the answer, the maximum length of a subarray
28        int maxSubarrayLength = 0;
29
30        // Loop to find the maximum length by combining the left and right counts of 1s
31        for (int i = 0; i < length; ++i) {
32            // Compute the length of subarray by removing the current element, hence adding left and right counts of 1s.
33            // Since one element is always removed, the combined length of consecutive 1s from left and right
34            // should not be equal to the total length of the array (which implies no 0 was in the array to begin with).
35            maxSubarrayLength = Math.max(maxSubarrayLength, leftOnesCount[i] + rightOnesCount[i]);
36        }
37
38        // Reduce the length by 1 if the length of consecutive 1s equals the array length, since we need to remove one element.
39        if (maxSubarrayLength == length) {
40            maxSubarrayLength--;
41        }
42
43        // Return the maximum length of subarray after deletion
44        return maxSubarrayLength;
45    }
46}
47
1class Solution {
2public:
3    int longestSubarray(vector<int>& nums) {
4        // Get the size of the input array
5        int size = nums.size();
6
7        // Create two vectors to keep track of consecutive 1's on the left and right
8        vector<int> left(size, 0);
9        vector<int> right(size, 0);
10
11        // Fill the left array with the counts of consecutive 1's from the left
12        for (int i = 1; i < size; ++i) {
13            if (nums[i - 1] == 1) {
14                left[i] = left[i - 1] + 1;
15            }
16        }
17
18        // Fill the right array with the counts of consecutive 1's from the right
19        for (int i = size - 2; i >= 0; --i) {
20            if (nums[i + 1] == 1) {
21                right[i] = right[i + 1] + 1;
22            }
23        }
24
25        // Initialize the variable to store the maximum length of the subarray
26        int max_length = 0;
27
28        // Iterate over the input array to compute the maximum subarray length
29        for (int i = 0; i < size; ++i) {
30            // The longest subarray is the sum of consecutive 1's to the left and right of the current element
31            max_length = max(max_length, left[i] + right[i]);
32        }
33
34        // Return the computed maximum subarray length
35        return max_length;
36    }
37};
38
1function longestSubarray(nums: number[]): number {
2    // Get the size of the input array
3    const size: number = nums.length;
4
5    // Create two arrays to keep track of consecutive 1's to the left and right
6    let left: number[] = new Array(size).fill(0);
7    let right: number[] = new Array(size).fill(0);
8
9    // Fill the left array with the counts of consecutive 1's from the left
10    for (let i = 1; i < size; i++) {
11        if (nums[i - 1] === 1) {
12            left[i] = left[i - 1] + 1;
13        }
14    }
15
16    // Fill the right array with the counts of consecutive 1's from the right
17    for (let i = size - 2; i >= 0; i--) {
18        if (nums[i + 1] === 1) {
19            right[i] = right[i + 1] + 1;
20        }
21    }
22
23    // Initialize the variable to store the maximum length of the subarray
24    let maxLength: number = 0;
25
26    // Iterate over the input array to compute the maximum subarray length
27    for (let i = 0; i < size; i++) {
28        // The longest subarray is the sum of consecutive 1's to the left and right of the current element
29        maxLength = Math.max(maxLength, left[i] + right[i]);
30    }
31
32    // Return the computed maximum subarray length
33    return maxLength;
34}
35
Not Sure What to Study? Take the 2-min Quiz：

A heap is a ...?

Time and Space Complexity

The given code aims to find the length of the longest subarray of 1s after deleting one element from the array. Here's the analysis of its computational complexity:

Time Complexity:

  • The time complexity of this algorithm is O(n), where n is the length of the input array nums. The reasoning behind this is that there are two separate for loops that each iterate over the array exactly once. The first loop starts from index 1 and goes up to n-1, incrementing by 1 on each iteration. The second loop starts from n-2 and goes down to 0, decrementing by 1 on each iteration. In both of these loops, only a constant amount of work is done (simple arithmetic and array accesses), so the time complexity for each loop is linear with respect to the size of the array.

  • Furthermore, there's a final step that combines the results of the left and right arrays using max and zip, which is also a linear operation since it involves a single pass over the combined arrays, making it O(n).

Adding up these linear time operations (3 * O(n)) still results in an overall time complexity of O(n).

Space Complexity:

  • The space complexity of this algorithm is O(n) as well. This is because two additional arrays, left and right, are created to store the lengths of continuous ones to the left and right of each index, respectively. Each of these arrays is the same length as the input array nums.

  • Besides the two arrays left and right, there are only a constant number of variables used (i.e., n, i, a, b), so they do not add more than O(1) to the space complexity.

Thus, the total space complexity is determined by the size of the two additional arrays, which gives us O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫