new year ki shuruwat aache rhe , toh socha leetcode pr esy ques aaya hai solve krunga toh confidence high rahega , yha 1 ghante se shi solution he nhi soch paaya sed life
please make a playlist on recursion concepts and questions it is my humble request. because for recursion I followed my playlist still I am still not getting full confidence on recursion your teaching style and code to story is very helpful for us🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏
bhya if possible ek playlist segment trees pe bhi bnao..its been widely asked topics across all companies nowadays like accolite,walmart,alibaba,Samsung,etc .....
In Approach-2, the time complexity is exactly - O(n + n) = O (2*n) ~= O(n) as per theory where we ignore constant In Approach-3, the time complexity is exactly - O(n)
Bhaiya, I understood the question from the previous video about the problem from leetcodr 376 but while checking if there are other possible solutions, i found this: int maxFrequencyScore(vector& A, long long k) { int i = 0, n = A.size(); sort(A.begin(), A.end()); for (int j = 0; j < n; ++j) if ((k -= A[j] - A[(i + j) / 2]) < 0) k += A[(i + j + 1) / 2] - A[i++]; return n - i; } Can you please explain what is going on here as this approach didn't involves binary search on answer
@codestorywithMIK your third approach DOESN'T work for this test case: s='1111' the problem is that in if loop after the main for loop. Checking for the last character in the string adds 1 in the return statement which doesn't concur with the left 0's and right 1's formula. Do check it and lmk.
It works. The output is 3 which is correct. When we come out of the for loop, the score value will be -1 because we get no zeros inside. The flow would go something like this (initially score = INT_MIN): 1st Iteration Count of Ones = 1 Count of Zeros = 0 score = max(score, Zeros-Ones) = -1 ---------------------------- 2nd Iteration Count of Ones = 2 Count of Zeros = 0 score = max(score, Zeros-Ones) = -1 ---------------------------- 3rd Iteration Count of Ones = 3 Count of Zeros = 0 score = max(score, Zeros-Ones) = -1 ---------------------------- Now, we come out of the for loop and count the last 1 (i.e. s[n-1]) Total ones count = 4; we return score + ones/ //-1 + 4 = 3 This answer is expected as below split is valid : "1111" ---> Left Substring : "1" Right Substring : "111" Score = Zeros in Left + Ones in Right = 0 + 3 = 3
What's the problem in this code?? class Solution { public: int maxScore(string s) { int one = 0,zero = 0,totalOnes; for(auto i:s) { if(i == '1') totalOnes++; } int ans=INT_MIN; int n = s.size(); for(int i=0; i
// In One-pass - Optimal Solution my approach class Solution { public: int maxScore(string s) { int x = 500; int maxi = 0; int n = s.length(); int countZeros = 0; int countOnes = 0; for(int i = 0;i
7:58 -> your daily streak 299 days!! hats off and congratulations
Your story telling + code makes the questions easier . Thanks for teaching so brilliantly 😊.
🙏❤️😇
new year ki shuruwat aache rhe , toh socha leetcode pr esy ques aaya hai solve krunga toh confidence high rahega , yha 1 ghante se shi solution he nhi soch paaya
sed life
please make a playlist on recursion concepts and questions it is my humble request.
Yes , planning in this winter holiday
3rd approach 👌🏻
third approach is just amazing!
Respected MIK Sir,
Happy New Year 🥳🎉
3rd approach is mind blowing.
Thanks a lot 👍
please make a playlist on recursion concepts and questions it is my humble request. because for recursion I followed my playlist still I am still not getting full confidence on recursion your teaching style and code to story is very helpful for us🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏
Yes , planning in this winter holiday
+1
3rd Approach was lit sir. Thanks a lot
Amazing
class Solution {
public:
int maxScore(string s) {
int n=s.size();
vectorpre(n,0);
vectorsuff(n,0);
int maxi=0;
for(int i=0;i=0;i--){
if(s[i]=='1'){
suff[i]=suff[min(n-1,i+1)]+1;
}else{
suff[i]=suff[min(n-1,i+1)];
}
}
for(int i=0;i
3rd one was amazing 🙌
Amazing Explanation bro.
third approach 🤯🤯🤯🤯🤯🤯🤯🤯🤯🤯🤯🤯🤯🤯
Want to see your Leetcode Year Rewind 💪
Please add it to the TH-cam shorts
Thank You sir
Solved on my own using brute force ...came here to see optimal approach.
Sir my request for new year is make DSA sheet of codestorywithmik ❤
Well explained
Done [22.12.23] ✅✅
❤❤
in approach 3 line 20 how can we access ( i ) it is out of scope of for loop
bhya if possible ek playlist segment trees pe bhi bnao..its been widely asked topics across all companies nowadays like accolite,walmart,alibaba,Samsung,etc .....
Thank you so much for this precious suggestion. Let me collect Qns and theory on this topic and make a playlist for that ❤️🙏
public int maxScore (String s){
int ans=0,zeros=0;
int ones=(int)s.chars().filter(c->c=='1').count();
for(int i=0;i+1
class Solution {
public int maxScore(String s) {
int n=s.length();
int ans=Integer.MIN_VALUE;
int[] lz=new int[n];
int[] lo=new int[n];
Arrays.fill(lz,0);
Arrays.fill(lo,0);
for(int i=0;i0 && x==0) lz[i]=lz[i-1]+1;
else lz[i]=lz[i-1];
}
for(int i=n-1;i>=0;i--){
char ch=s.charAt(i);
int x=ch-'0';
if(i==n-1 && x==1) lo[i]=1;
else if(i==n-1 && x!=1)lo[i]=0;
else if(i
I don't understand why are we using n-2. In leetcode editorial also we are using n-1
Why n-2?
will there be a complexity change in approach 2 and 3 ??
In Approach-2, the time complexity is exactly - O(n + n) = O (2*n) ~= O(n) as per theory where we ignore constant
In Approach-3, the time complexity is exactly - O(n)
@@souravjoshi2293I think count function will take o(n) that's why it will be o(2n)
No. Both are O(n)
O(2n) is same as O(n) as we ignore constants in TC and SC
Third one 💛
Bhaiya, I understood the question from the previous video about the problem from leetcodr 376 but
while checking if there are other possible solutions, i found this:
int maxFrequencyScore(vector& A, long long k) {
int i = 0, n = A.size();
sort(A.begin(), A.end());
for (int j = 0; j < n; ++j)
if ((k -= A[j] - A[(i + j) / 2]) < 0)
k += A[(i + j + 1) / 2] - A[i++];
return n - i;
}
Can you please explain what is going on here as this approach didn't involves binary search on answer
This code is a headache. I didn't understand a bit what the author has written.
@@souravjoshi2293 ikr! I tried dry running it and got correct answers but why?
@codestorywithMIK your third approach DOESN'T work for this test case:
s='1111'
the problem is that in if loop after the main for loop. Checking for the last character in the string adds 1 in the return statement which doesn't concur with the left 0's and right 1's formula.
Do check it and lmk.
It works. The output is 3 which is correct.
When we come out of the for loop, the score value will be -1 because we get no zeros inside.
The flow would go something like this (initially score = INT_MIN):
1st Iteration
Count of Ones = 1
Count of Zeros = 0
score = max(score, Zeros-Ones) = -1
----------------------------
2nd Iteration
Count of Ones = 2
Count of Zeros = 0
score = max(score, Zeros-Ones) = -1
----------------------------
3rd Iteration
Count of Ones = 3
Count of Zeros = 0
score = max(score, Zeros-Ones) = -1
----------------------------
Now, we come out of the for loop and count the last 1 (i.e. s[n-1])
Total ones count = 4;
we return score + ones/ //-1 + 4 = 3
This answer is expected as below split is valid :
"1111" --->
Left Substring : "1"
Right Substring : "111"
Score = Zeros in Left + Ones in Right = 0 + 3 = 3
Let me solve and get back to 2 on this one.
@@prxshetty you must have taken score as 0 initially bt it should be int_min
bro please make a video on LC 2967 kahi accha explanation nhi h :(
❤
What's the problem in this code??
class Solution {
public:
int maxScore(string s) {
int one = 0,zero = 0,totalOnes;
for(auto i:s)
{
if(i == '1')
totalOnes++;
}
int ans=INT_MIN;
int n = s.size();
for(int i=0; i
Nothing is wrong with your code. Just need to initialize the totalOnes variable with 0. It is taking garbage value.
So just add
int totalOnes = 0;
@@codestorywithMIK Thanks a lot for replying. BTW I figured it on my own but wasted 30 mins for that.
bhai java m video kyo nhi banate ho?
Hello siddharth,
Actually I post C++ as well as JAVA code in my GitHub. I make videos in C++
@@codestorywithMIK i know that bro but video m java m bhi explain krte code ko to sahi rhta...just suggesting :)
@siddharthmishra8651 Thanks siddharth for your precious suggestions. Let me try this soon.
that one pass solution was worth 20 mins.
Bro in the Brute Force approach, the first loop should be (I = 0 to I < n - 1).
I < n-1
is same as
I
@@thefinalfit Oops Sorry, I made a mistake while watching.
// In One-pass - Optimal Solution
my approach
class Solution {
public:
int maxScore(string s) {
int x = 500;
int maxi = 0;
int n = s.length();
int countZeros = 0;
int countOnes = 0;
for(int i = 0;i
I was able to come up with two pass solution
def maxScore(self, s: str) -> int:
n , prev = len(s) , float('-inf')
count = [[0,0] for i in range(n)]
one,zero = 0,0
for i in range(n):
if s[i]== '0':
zero+=1
elif s[i] == '1':
one += 1
count[i][0],count[i][1] = zero,one
for i in range(n-1):
if prev < count[i][0] - count[i][1] + count[-1][1]:
prev = count[i][0] - count[i][1] + count[-1][1]
return prev
Try to be consistent.
Yes I post daily ♥️
Thank you so much bhaiya for the one pass approach. 🫡