pJain
BAN USERMinor correction -
public int longestStreak(int[] a, int k){
int maxLength = 0;
int endPos = 0;
Stack<Integer> zeroStack = new Stack<>();
int j = 0;
for(int i=0, start=0;i<a.length;i++ ){
if(a[i] ==0 && j==k){
int currentStreakLength = i-start;
if(currentStreakLength >maxLength){
maxLength = currentStreakLength;
endPos = i-1;
}
start = zeroStack.pop();
zeroStack.push(i);
}else if(a[i] ==0 && j<k){
zeroStack.push(i);j++;
}
}
if(j<k){
endPos = a.length-1;
maxLength = a.length;
}
System.out.println("Longest streak (with '"+ k+"' zero's) of length "+maxLength+" found at position: "+endPos);
return maxLength;
}
This will give performance of O(n/2)
- pJain May 27, 2016