Longest Ones After Deleting One Element

Interview Problem Interview Medium Variable-size Window Array

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.longestSubarray(nums). nums is binary. Delete exactly one element and return the longest non-empty subarray containing only ones afterward.

Starter code

class Solution:
    def longestSubarray(self, nums):
        pass

Test cases

one-zero

{
  "args": [
    [
      1,
      1,
      0,
      1
    ]
  ]
}

Expected: 3

Wizard outline

Step 1: Initialize Solution.longestSubarray
Replace the empty starter with the first real state owned by Solution.longestSubarray. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Pass the Delete From All Ones case
Complete the readable core algorithm for one representative Interview case. Maintain a window with at most one zero and subtract one position for the mandatory deletion.
Step 3: Harden the Several Zeroes boundary
Repair the reviewed boundary and pass the complete submission contract. Every feasible post-deletion run comes from a window with at most one zero. The algorithm keeps the longest such window ending at each right index, and subtracting one handles either deleting that zero or the mandatory deletion from an all-ones window.

Footguns and prerequisites

An all-ones input still requires deleting one element, so its answer is len(nums)-1.
arrays strings two pointers sliding window

Reviewed references

LeetCode 1493 — Longest Subarray of 1's After Deleting One Element

Practice prerequisites

Shrink Until the Window Is Valid(opens in a new tab)
Shrink Until the Window Is Valid isolates after shrinking, the current half-open window is valid and no earlier left boundary works for the same right endpoint. That focused state discipline is required when implementing longest ones after delete as a complete Interview Problem.

Recommended approach and implementation

Slide a window containing at most one zero. Its best post-deletion ones length is window length minus one, represented by right-left.

Why it works: Every feasible post-deletion run comes from a window with at most one zero. The algorithm keeps the longest such window ending at each right index, and subtracting one handles either deleting that zero or the mandatory deletion from an all-ones window.

class Solution:
    def longestSubarray(self, nums):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        left = zeros = best = 0
        for right, value in enumerate(nums):
            if value == 0:
                zeros += 1
            while zeros > 1:
                if nums[left] == 0:
                    zeros -= 1
                left += 1
            best = max(best, right - left)
        return best

Similar exercises

Max Consecutive Ones III(opens in a new tab)