1493. Longest Subarray of 1's After Deleting One Element
Longest Subarray of 1's After Deleting One Element (LeetCode 1493) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
How to solve Longest Subarray of 1's After Deleting One Element
Longest Subarray of 1's After Deleting One Element is a Variable Size Sliding Window problem, part of Sliding Window. Master variable-size sliding window for condition-based problems like longest substring without repeating characters.
Work towards the solution in these steps:
- Maintain a sliding window where there is at most one zero in it.
The reference solution runs in O(n) time and O(1) space.
The Longest Subarray of 1's After Deleting One Element solution and editorial walks through the full approach with reference code.
Problem statement
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 <= 105
- nums[i] is either 0 or 1.
Topics and companies
Topics: Array, Dynamic Programming, Sliding Window.
Reported in interviews at Yandex.
How to practise Longest Subarray of 1's After Deleting One Element on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Longest Subarray of 1's After Deleting One Element in the code editor, or read the Longest Subarray of 1's After Deleting One Element editorial for a worked solution with its approach and complexity analysis.
Where Longest Subarray of 1's After Deleting One Element sits in the DSA pattern sheet
Problems related to Longest Subarray of 1's After Deleting One Element
Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:
- Contains Duplicate II — Easy, same subpattern
- Continuous Subarrays — Medium, same subpattern
- Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
- Frequency of the Most Frequent Element — Medium, same subpattern
- Fruit Into Baskets — Medium, same subpattern
- Jump Game VII — Medium, same subpattern
Longest Subarray of 1's After Deleting One Element FAQ
What is the LeetCode number of Longest Subarray of 1's After Deleting One Element?
Longest Subarray of 1's After Deleting One Element is LeetCode problem 1493, rated Medium.
What pattern is used to solve Longest Subarray of 1's After Deleting One Element?
Longest Subarray of 1's After Deleting One Element is a Variable Size Sliding Window problem. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
What is the time complexity of Longest Subarray of 1's After Deleting One Element?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Longest Subarray of 1's After Deleting One Element?
Longest Subarray of 1's After Deleting One Element has been reported in interviews at Yandex.