Flip

Timestamps:
0:00 Reading the problem
2:30 Explaining intuition
3:30 Kadane Algorithm
6:00 Kadane Code and Dry Run
10:30 Example dry run
13:02 Code CPP
Input Format
First and only argument is a string A.
Output Format
Return an array of integers denoting the answer.
Example Input
Input 1:
A = "010"
Input 2:
A = "111"
Example Output
Output 1:
[1, 1]
Output 2:
[]
Example Explanation
Explanation 1:
A = "010"
Pair of [L, R] | Final string
___________|_________
[1 1] | "110"
[1 2] | "100"
[1 3] | "101"
[2 2] | "000"
[2 3] | "001"
We see that two pairs [1, 1] and [1, 3] give same number of 1s in final string. So, we return [1, 1].
Explanation 2:
No operation can give us more than three 1s in final string. So, we return empty array [].

[@avinashvishwakarma6488]

The best part about your explanation is that you always develop the intuition first. That helps me a lot in solving other similar problems. Keep making more videos of interviewbit problems. Thanks a lot.

[@probabilitycodingisfunis1]

Thanks Avinash!

[@manikmalhotra3903]

Just came across this channel. One of the best and easy-to-understand content. Thank you

[@probabilitycodingisfunis1]

Thank you Manik!

[@attyuttamsaha8]

Really loved the way you have explained the concept and related the two problems.

[@ankit_irl]

Top notch explanation. Thank you for existing

[@probabilitycodingisfunis1]

Glad you liked it!

[@annanyamathur8869]

I really like your way of explaining

[@mrinmoyhalder7293]

thanks for the approach, I understand the concept clearly, but one thing I want to say is that changing input may not be feasible always, so it's better to keep a variable which ++ and -- accordingly.

[@mrinalmadhav8119]

Tysm mam, it was great, loved it, big fan of u mam

[@akashnigam5321]

Just got to know that you are an alumni of my college IIT Bombay, your videos are really helpful.

[@namanagrawal1908]

Great Explanation

[@truptisatsangi6043]

very nice explaination along with related topic so you to go nowhere for 1 question.
Great job

[@raju_bugude]

nice explanation(intution part)

[@probabilitycodingisfunis1]

Thank you so much

[@vikaskumar-kc4jv]

Make more videos you are really awesome

[@pharmacybyanuj2459]

your way of teaching is really superb when ever i understand any problem by you it clear my concepts.
thanks Alisha didi
di can you tell me how should i make dsa notes ? or make a video how to make dsa notes

[@rohankumarshah5679]

fantastic !!

[@raj_kundalia]

Thanks for the video!

[@rithikrk3695]

Beauty with brain....very nice explanation mam!

[@jatinbhatoya8420]

for java users -
public static int[] flip(String A) {
int left = -1, right = -1;
int sum = 0, maxSum = 0, currleft = 0;
for (int i = 0; i < A.length(); i++) {
sum += A.charAt(i) == '0' ? 1 : -1;
if (sum < 0) {
sum = 0;
currleft = i + 1;
}
if (sum > maxSum) {
maxSum = sum;
left = currleft;
right = i;
}
}
if (left == -1 && right == -1) return new int[0];
return new int[]{left + 1, right + 1};
}

[@rajbhardwaj2180]

Hey Alisha Plz tell the way how to remember ,truth table of all flip flops quite confusing

[@aniketkumarsinha2537]

I guess you skip this part "return the lexicographically smallest pair of L and R."

[@avinashvishwakarma6488]

but code still runs. Why?

[@dishantmeena1621]

Actually in this approach, we are considering only the best flipping which will give us the maximum no. of ones. So, we are constantly updating our L and R values and only return the best pos.
Hope this will help.

[@rizwanpolice2741]

At the timestamp 7:22 in the kadane algorighm. the solution will not work for all the negative integer array.
For example if the array is {-2,-4,-9,-3,-1}
The maximum subarray sum will be -1. But with the above pseudo code, it will be 0.

[@sambhavsharma2780]

just init maxSum with arr[0]

[@neerajjoshi1249]

for that take the value of max_sum as INT_MAX

[@siddharthjain4361]

hi , answer could be one or more right ...how did u check lexicographically for the same

[@deepakkapasia1]

More than half test cases failed with this solution. Explaination good for the question and kadane algo but figuring out index not explained.

[@Hadle695]

can u plzz share your code

[@chandraprakashsahu8557]

can you please drop your linkedIn id

[@govinth2462]

hi mam I wanna Connect With you can i get your LinkedIn ID