Maximum Consecutive Ones - 1 (Leetcode Medium) | Hashmap Interview Questions

NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we discuss the problem Maximum Consecutive Ones with K flips using hashmaps in java. In this problem,

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

[NatureLover-oquc]

This Man is Just Awesome🥰🥰....Thanks A Lot For Beautiful Explanation.

[sagaradhikari]

thanks a lot sir, your explanation is just top notch.

[joydeepsarkar]

the time complexity here is O(n*count) but using acquire and release method using hashmap we can do it in O(n)

[SumitSingh-uido]

All college teachers should learn from Sumit sir ❤️ to how to teach

[skarwa]

class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
ans = 0
left = 0
flip_count = 0
for right in range(len(nums)):
if(nums[right] == 0):
flip_count +=1
while(flip_count > 1):
if(nums[left] == 0):
flip_count-=1
left+=1
ans = max(ans, right-left+1)
return ans
# readable solution

[sahilnagdev]

see can we use like loops if(a[i]==1){c++}else{c1++} inside the for loop if(c>c1){return c} is it okay one?

[abhinandanraj]

YOU CAN DO IT BY SLIDING WINDOW CONCEPT , FIXED PATTERN

vector<int> Solution::maxone(vector<int> &A, int B) {
int count=B;

int leftindex=-1;
int rightindex=-1;

int lefttraverse=0;
int maxcount=0;
int righttraverse=0;
int totalelement=A.size();


{

if(A[righttraverse]==0 and count>=0)
{
count--;
}

if(count>=0)
{
int
if(total>maxcount)
{
leftindex=lefttraverse;
rightindex= righttraverse;

maxcount=total;
}
}
while(count<0 and lefttraverse<totalelement)
{
if(A[lefttraverse++]==0)
{
count++;
}
}

righttraverse++;


}
vector<int>result;

for(int i=leftindex ;i<=rightindex;i++)
{
result.push_back(i);
}

return result;

}

[ankoor]

Approach similar to previous questions (Python):

A = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1]
k = 3

i = 0
j = 0
freq = {}
n = len(A)
maxCount = 0

while True:

while i < n:
e = A[i]
freq[e] = freq.get(e, 0) + 1
i += 1
if freq.get(0, 0) <= k:
maxCount = max(maxCount, i-j)
if freq.get(0, 0) > k:
break

while j < i:
e = A[j]
freq[e] = freq[e] - 1
if freq[e] == 0:
freq.pop(e)
j += 1
if freq.get(0, 0) == k:
break

if i == n:
break

print(maxCount)

[beandesai]

which can do wiithout count by using k it self
class Solution {
public int longestOnes(int[] nums, int k) {
int i=0, j=0, ans=0, n=nums.length;

while(i<n){
if(nums[i++]==0)k--;

while(k<0){
if(nums[j++]==0)k++;
}
ans = Math.max(ans, i-j);
}
return ans;
}
}

[cyberserker]

int longestOnes(vector<int>& nums, int k) {
//need to find the longest window
int ans = 0; //this will hold the longest window
//k is like our allowed expense
int l = 0, r = 0;
int zeroCount = 0;
while(r < nums.size()){
if(nums[r] == 0){
zeroCount++;
}
while(zeroCount > k){
if(nums[l] == 0){
zeroCount--;
}
l++;
}
ans = max(ans, r-l+1);
r++;
}
return ans;
}

[mickyman]

if want to follow acquire and release strategy code, then the code is

public static int solution(int[] arr, int k){
int maxlen=0;
int i=-1;
int j=-1;
HashMap<Integer, Integer> hm=new HashMap<>();

while(true)
{
boolean loop1=false;
boolean loop2=false;
while(i<arr.length-1)
{
loop1=true;
i++;
hm.put(arr[i], hm.getOrDefault(arr[i], 0)+1);
if(arr[i]==0&&hm.get(0)==k+1)
break;
else
maxlen=Math.max(maxlen, i-j);
}
while(j<i)
{
loop2=true;
j++;
hm.put(arr[j], hm.get(arr[j])-1);

if(hm.get(arr[j])==0)
hm.remove(arr[j]);

if(hm.getOrDefault(0, 0)==k)//valid ho gya
{
maxlen=Math.max(maxlen, i-j);
break;
}
}

break;
}
return maxlen;
}

[aman]

video me or site pr question me naam different hai question ke. 1 wala 2 me hai or 2 wala 1 me

[Anand]

CPP code based on acqiure and release:

int findZeroes(int arr[], int n, int m) {
// code here
vector<int>map1(10, 0);
int i=-1, j=-1;
int maxi=0;
while(true){
bool f1=false, f2=false;
while(i<n-1){
i++;
f1=true;
map1[arr[i]]++;
if(map1[0]<=m){
int len=i-j;
if(len>maxi){
maxi=len;
}
}
else{
break;
}
}
while(j<i){
j++;
f2=true;
if(arr[j]==1){
map1[arr[j]]=0;
}
else{
map1[arr[j]]--;
}
if(map1[0]<=m){
int len=i-j;
if(len>maxi){
maxi=len;
}
break;
}

}
if(f1==false and f2==false)break;
}
return maxi;
}