Maximum Consecutive One's - 2 (Leetcode Medium) | Hashmap Interview Question

NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we discuss the maximum consecutive one's problem with at most one swap using hashmaps in java. In this problem,

1. You are given an array(arr) which contains only 0's and 1's.
2. You have to find the maximum number of consecutive 1's in the given array if you can flip at most one zero.

#hashmaps #datastructure #algorithms

[studytime]

Instead of using while loop to release ones until we find 0, what we can do is we can store the index of the last 0 and update j whenever 0 is found again

[GirishJain]

using acquire release strategy

class Solution {
public int longestOnes(int[] a, int k) {
int n = a.length;
int i = -1, j = -1;
HashMap<Integer, Integer> map = new HashMap<>();
int ans = 0;

while(true){
boolean flag1 = false;
boolean flag2 = false;

while(i < n-1){
flag1 = true;
i++;
if(a[i] == 0){
map.put(a[i], map.getOrDefault(a[i], 0)+1);
if(map.get(a[i]) > k){
break;
}
}
ans = Math.max(ans, i-j);
}
while(j < i){
flag2 = true;
j++;
if(a[j] == 0){
map.put(a[j], map.get(a[j])-1);
if(map.get(a[j]) == k){
break;
}
}
}
if(flag1 == false && flag2 == false){
break;
}
}
return ans;
}
}

[momentumbees]

you saved me time!! Thank you so much sir!!

[sadmanabedin]

It's actually similar to another leetcode problem (Leetcode 1493), where you have to find the longest length of consecutive ones after deleting at most one zero.
I solved it a couple of months ago, so I used the same logic here, changed the code a little bit and it worked for this problem also. Without hashmap, O(n) time, O(1) space.

Here is my solution:

n = int(input())
nums = input()
nums = [int(x) for x in nums.split()]

left, count = 0, 0
res = 0
z = -1
for i in range(0, n):
if nums[i]==0:
res = max(res, left+count+1)
z = i
left = count
count = 0
else:
count+=1
print(max(res, left+count+(z>=0)))

[umayadav]

this channel is a life saver Sir!! Cannot thank you enough for putting out such good explanation 😊

[Hamduvibes]

Sir, Solved this question using priority queue taking exactly O(n) time rather than using hashmap which takes ~O(2n) .

[aman]

is video kaa naaam
Maximum Consecutive One's - 1 hai.

[neerajagarwal]

Please explain problem: Find the index of 0 to be replaced to get the maximum length sequence of continuous ones

[ravikamble]

Sir on line number 15 must be while(count>k).

[ayushgoel]

Sir if possible please try to upload 3-4 hours of content on daily basis