Longest Subarray of 1's After Deleting One Element | Multiple Approaches | GOOGLE | Leetcode-1493

****Similar Problem : Leetcode - 1004, 487, 485****

Hi everyone, this is the 10th video of our Sliding Window Playlist.
In this video we will try to solve a very good classical Sliding Window problem “Longest Subarray of 1's After Deleting One Element”.

We will write very easy and clean code with intuition building and understanding each line of code.
BRUTE FORCE
SLIDING WINDOW
BETTER SLIDING WINDOW
DRY RUN OF ALL APPROACHES

We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Longest Subarray of 1's After Deleting One Element
Company Tags : GOOGLE, META

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish

[AnjaliKholiya-xc]

Bhaiya ese hi sari leet code ki bnado bhut easy hojyega hm sab k ly

[manimanohar_]

Best ever video on SLIDING WINDOW I've ever seen. 😊☑️❤️🌄

[rounaq_khandelwal]

Thank you so much to upload the video early today, was veryy happy to see when I searched for it!! 🤩🤩😉

[thefinalfit]

My one stop Solution Youtube channel 👌🏻

[AbhijeetMuneshwar]

I liked the way you narrated code story for 3rd solution. This helps to grasp that concept easily.

[atharvpal]

An excellent video mate! loved the third approach. I agree, that the 3rd is obvious yet not that intuitive.
Thanks for the content!

[souravjoshi]

I have no words man.
You always NAIL it. What more can I say. You deserve more subscribers ❤
People will soon be talking about your name almost everywhere

[nishigandhagirishdandekar]

Very good explanation, I was struggling with this problem for a long time but your video helped clear things up! Thank you 🙏

[sujansinhthakor]

Also there is another approach, similar to sliding window. We can count the continuous left_ones and right _one for each index then take max of (left_one+righ_one).
Here is the code-->
public int longestSubarray(int[] nums) {
int[]left_one=new int[nums.length];
for(int i=1;i<nums.length;i++){
if(nums[i-1]==1){
left_one[i]=left_one[i-1]+1;
}
}
int[]right_one=new int[nums.length];
for(int i=nums.length-2;i>=0;i--){
if(nums[i+1]==1){

}
}
int ans=0;
for(int i=0;i<nums.length;i++){
ans=Math.max(ans, left_one[i]+right_one[i]);
}
return ans;
}

[prathamtetgure]

This channel is soon gonna famous, what a great presentation skills you have...hatsoff

[dikshantyadav]

nice explanation and awesome presentation skills.

[priyanshusingh]

and the journey to millions subscribers continues😇

[AlishaKhan-wwio]

What an explanation ❤🔥. 3rd one was too good

[floatingpoint]

thanks for the explanation. it was very helpful. i specially like the last approached which you mentioned

[sauravbiswajit]

Not watched this video when I am commenting on this ...but no doubt it will be as good as previous ones ....for sure... Thanks a lot and please try to make videos on bitmasking and it's implementation and questions on concepts like dp using bitmasking, bfs using Binary search etc....thanks a lot 😊😊

[FanIQQuiz]

Literally the best explanation like always 🔥🔥🔥

[xiaoshen]

My soln : (Beats 100% time and 65% memory)
class Solution {
public:
int longestSubarray(vector<int>& nums) {
int idx = 0;
int ans = 0;
int i = 0, j = 0;
bool chk = false;
while(j<nums.size()) {
if(nums[j]==1)
j++;
else if(!chk){
chk = true;
idx = j;
j++;
}
else {
chk = false;
ans = max(ans, j-i);
i = idx+1;
}
ans = max(ans, j-i);
}
return ans-1;
}
};

[arnabsarkar]

Here are my 4 approaches with thought process : A small tip : First paste my code on an editor or leetcode to understand it better. Thank you

/*

Algorithm : We have to find the longest subarray with max number of 1's. And we can delete one element and after deleting the elemenet, we have to find the longest length of the subarray with all 1's. So we will find the subarray with 1's and count the number of 0's. If count > 1 then we will not include it in our ans but if it is less than 2, then we can include it and the length will be total length of the subarray - 1 because we will be removing the 1 element.

Another thing is, we have to delete one element. Even if there are all 1's, we have to delete a particular element. So if the subarray is from i to j, then we will calculate the length as (j - i) [we will not add 1] and we will compare this with our main ans only if count of zeros is less than 2.

*/
class Solution {
public int longestSubarray(int[] nums) {
return slidingWindowApproach(nums);
}

public int brutforceApproach(int[] nums) {
int n = nums.length, ans = 0;

for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// i to j is the subarray
int count = 0;

for (int k = i; k <= j; k++) {
if (nums[k] == 0) {
count++;
}
}

if (count < 2) {
ans = Math.max(ans, j - i);
}
}
}

return ans;
}

public int betterApproach(int[] nums) {
int n = nums.length, ans = 0;

for (int i = 0; i < n; i++) {
int count = 0;

for (int j = i; j < n; j++) {
if (nums[j] == 0) {
count++;
}

if (count < 2) {
ans = Math.max(ans, j - i);
}
}
}

return ans;
}

public int slidingWindowApproach(int[] nums) {
int i = 0, j = 0, n = nums.length, count = 0, ans = 0;

while (j < n) {
int ele = nums[j];

if (ele == 0) {
count++;
}

while (i < n && count >= 2) {
if (nums[i] == 0) {
count--;
}

i++;
}

if (i > j) {
return 0;
}

ans = Math.max(ans, j - i);

j++;
}

return ans;
}

public int nums) {
int i = 0, j = 0, n = nums.length, count = 0, ans = 0;

while (j < n) {
int ele = nums[j];

if (ele == 0) {
count++;
}

if (count >= 2) {
if (nums[i] == 0) {
count--;
}

i++;
}

ans = Math.max(ans, j - i);

j++;
}

return ans;
}
}

[rajkrishanmahajan]

i am able to solve this question by standard window method but after watching your solution i need to try Hard more 😅.

[Rajdweep]

hey, so i did it in a different way but its also O(n) one loop only, intuition is to have the sum of two parts first part n second part, adding the code below lmk what u think. class Solution {
public int longestSubarray(int[] nums) {

int n=nums.length, flag=0, fp=0, sp=0, sum=0;
for(int i=0;i<n;i++){
if(nums[i]==0){
if(flag==0)flag=1;
else{
sum=Math.max(sum, fp+sp);
fp=sp;
sp=0;
}
}
else{
if(flag==0)fp+=nums[i];
else sp+=nums[i];
}
}
sum=Math.max(sum, fp+sp);
return sum==n ? n-1:sum;
}
}