SeniorCodeRareNot answered yet
Longest run of 1s after deleting exactly one element
Given a binary array, return the length of the longest run of 1s obtainable after deleting EXACTLY one element. The deletion is mandatory even when there are no zeros, so an all-ones array of length L yields L-1.
Requirements:
- O(n) time, O(1) extra space; do not modify the input.
int maxOnesAfterOneDeletion(const std::vector<int>& a) {
// your code here
}Write the implementation.
Sliding window allowing at most one zero inside it; the answer is the largest window size minus one (one element is always removed). When there are no zeros, that minus-one still applies, giving L-1 for an all-ones array. One pass, O(n), O(1).
- ✗Returning the window size without subtracting one for the mandatory deletion
- ✗Failing the all-ones case where one element must still be removed (answer L-1)
- ✗Allowing more than one zero in the window
- →How does 'exactly one' deletion differ from 'at most one' for an all-ones array?
- →How would the window generalize to deleting up to k elements?
Contents
Task
Find the longest run of ones after deleting exactly one element, in O(n).
Solution
int maxOnesAfterOneDeletion(const std::vector<int>& a) {
int left = 0, zeros = 0, best = 0;
for (int right = 0; right < static_cast<int>(a.size()); ++right) {
if (a[right] == 0) ++zeros;
while (zeros > 1) { if (a[left++] == 0) --zeros; }
best = std::max(best, right - left + 1);
}
return best - 1; // exactly one deletion is mandatory
}Key points
- The window allows at most one zero.
- The answer is the best window size minus one.
- An all-ones array still deletes one element: L-1.
Contents
