Minimum Swaps to Group All 1's Together II | 2 Ways | Dry Runs | Leetcode 2134 | codestorywithMIK
Вставка
- Опубліковано 12 вер 2024
- Whatsapp Community Link : www.whatsapp.c...
This is the 25th Video of our Playlist "Sliding Window : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a good and standard Sliding Window Problem : Minimum Swaps to Group All 1's Together II | 2 Ways | Dry Runs | Leetcode 2134 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Minimum Swaps to Group All 1's Together II | 2 Ways | Dry Runs | Leetcode 2134 | codestorywithMIK
Company Tags : Microsoft
My solutions on Github(C++ & JAVA) : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZ...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1: Using Extra Space and Sliding Window
Time Complexity: O(n)
Space Complexity: O(2n) ~ O(n)
Explanation:
Duplicating the Array: A temporary array temp of size 2*n is created by concatenating the original array with itself. This allows for a circular array approach using a linear array.
Count of 1s: The total number of 1s in the original array is counted using accumulate.
Sliding Window: A sliding window of size equal to the number of 1s is used to find the maximum number of 1s in any subarray of this size. This is done by:
Initializing pointers i and j to the start of the array.
Moving j to expand the window and counting 1s.
If the window size exceeds the number of 1s, moving i to shrink the window and adjusting the count of 1s.
Tracking the maximum number of 1s found in any window of the required size.
Result Calculation: The minimum swaps needed is calculated as the total number of 1s minus the maximum number of 1s found in any window.
Approach 2: Sliding Window without Extra Space
Time Complexity: O(n)
Space Complexity: O(1)
Explanation:
Count of 1s: Similar to Approach 1, the total number of 1s in the original array is counted.
Sliding Window with Modulo Operation: Instead of duplicating the array, the modulo operation (j % n and i % n) is used to handle the circular nature of the array within the same array space.
Sliding Window: The logic for the sliding window remains the same as in Approach 1:
Using pointers i and j to define the window.
Adjusting the count of 1s when expanding or shrinking the window.
Tracking the maximum number of 1s found.
Result Calculation: The result is calculated as the total number of 1s minus the maximum number of 1s found in any window.
Comparison:
Both approaches have the same time complexity of O(n).
Approach 1 uses additional space to create a duplicated array, resulting in O(n) space complexity.
Approach 2 optimizes space usage by leveraging the modulo operation, resulting in O(1) space complexity.
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024
Today's problem was very much easy when you figure it out
Did it myself today!! Sir!
class Solution {
public int minSwaps(int[] nums) {
int numOfOnes = 0;
for (int x : nums) {
if (x == 1)
numOfOnes += 1;
}
int numOfZeroes = 0;
int min = Integer.MAX_VALUE;
int start = 0;
for (int end = 0; end < 2 *nums.length; end++) {
if (nums[end % nums.length] == 0) {
numOfZeroes++;
}
while (end - start + 1 == numOfOnes) {
min = Math.min(numOfZeroes, min);
if (nums[start % nums.length] == 0) numOfZeroes--;
start++;
}
}
return numOfOnes == 0 ? 0 : min;
}
}
You can do it by counting zeroes as well in the sliding window.. The major trick in this problem is to figure size of the window since K is not given. Here it will be equal to number of ones in the window. Once that is figured out, it is a very easy problem..
solved on my own, only possible because i am following you regularly from last 3 months.🙏
sir can u make one video for each data structure on time complexity and space complexity where like for graphs u can tell and little explain time complexities of main things like dfs,bfs,dijikstra and other importat questions
Please can u make 1 such video of time complexities and space complexities for each data structure.....i m facing a lot of difficulty in time complexities
Yesssss
yes please mik
we also be use
int ones = accumulate(begin(nums), end(nums), 0); or
int ones = count(begin(nums), end(nums), 1);
you are one of the best tutors no doubt. I have shared your channel to almost everyone I know in coding groups
As our placement interview are approaching,can you create a video on time and space complexity of ds and major algos
Thanks for the hint, Sir!!
Have a Good Day a head!!!
5 mins into the video and I coded it myself without using extra space☺. My approach is slightly different:
class Solution {
public:
int minSwaps(vector& nums) {
int n=nums.size();
int cntOnes=0;
for(int i=0;i
best question for interview
trust me, you're awesome!
even though I know very little of sliding window was able to code it myself after your explations...
with both of the approaches...
class Solution {
public int minSwaps(int[] nums) {
int n = nums.length;
//int[] arr = new int[2*n];
int totalOnes = 0;
for(int i=0;i
NICE SUPER EXCELLENT MOTIVATED
thx for the effort good explanation.
great explanation, thanks
keep making detailed explaination videos
After a long break 🙂❤
Sir can you mentions those ques in pinned comment which are simiar to this problem
Thanks a lot bhaiya ❤❤
Thanks 😊
thank you sirrr
Here is My solution:
int minSwaps(vector &nums)
{
int n = nums.size();
int totalOnes = count(nums.begin(), nums.end(), 1);
int currOnes = count(nums.begin(), nums.begin() + totalOnes, 1);
int minSwap = totalOnes - currOnes;
int i = 0, j = totalOnes - 1;
while (j < 2 * n - 1)
{
j++;
if (nums[j % n])
{
currOnes++;
}
if (nums[i % n])
{
currOnes--;
}
i++;
minSwap = min(minSwap, totalOnes - currOnes);
}
return minSwap;
}
❤❤
I have been doing Daily leetcode for around 250 days but now i don't want to do it. i am not getting any motivation to do it
and it leads to losing my consistency. I am loosing the patience i just want to see solution now and also after 5 min i don't want to watch and skip it to direct solution. What can i do i don't want to think by myself as it's not pushing me anymore,i want your opinion now. Help me
I am also in kind of same situation.Don't know why, But i could not solve new problems with enthusiasm. Inspite of knowing that i am not that good enough untill now, I am not feeling to put efforts while solving, and i become impatient while solving problem.
This was easy, but after I saw which topic it belonged to.
size of array can be 10^5 for this problem if we make 0 to 2 * 10^5 travel then it should not pass the all test cases as we can run 10^9 operations in 1 sec.
Can you explain like why this is not a problem for us ?
mik bhai, is tarike question mein kyese figure out karunga, ki ye sliding window ka problem hai, kiyuki sliding window ki pattern hota hai, find subarray of length k, etc... but is question mein kyese karunga, sliding window ka aur patterns discuss koro bhai
more practice will let u know all things bro !!
practice practice practice. I had solved a similar problem and hence was able to figure out sliding window
@@aws_handles can you share some similar problems like this one
@@aws_handles Yes, I know practice is only way but I want to know, more types of patterns which are solved using sliding window, like find k length subarray, etc... can you say?
@@zebra-er6xc see problems under leetcode 'similar problems' section in description page
please also provide code in java.
int one=0;
for(auto &i:nums)if(i==1)one++;
int i=0;
int j=one-1;
int cnt=0;
for(int k=i;k
public int minSwaps(int[]nums){
int cntOnes=0;
for(int i=0;i=cntOnes-1)
min=Math.min(min,cntOnes-sum);
}
for(int i=0;i
you should try to upload video of gfg ptod also
IS anyone having problems running leetcode solutions due to the slowness of the site?
yr sliding window ka intuition hi nhi aya...main soch rha tha largest group ko nikalke fir sides ko increase kru...aisa intuition kaise banau itne din hogye fir bhi nhi aya
mai bhi largest ones ka group nikal kar try kar raha tha, video dekh ke sliding window ka idea aaya
we can implement it in our windowSize how many min zero.
public int minSwaps(int[]nums){
int windowSize=0;
for(int num:nums)
windowSize+=num;
int curZeros=0;
for(int i=0;i
Haath beth gaya hai dsa sikhane pe , not many youtubers are like this
Please topic ka approach phle mention mat kiya karo😢 we come here to get overview and poora approach phle pata chal jata🤧
I tried to hide the approach in the beginning.
I will try to increase the duration of initial part for hiding the topic name.
Thank you 🙏😇
Atleast 5 min ke baad bataya karo
@@codestorywithMIK it will help mic
My fear of sliding window is gone. Thanks a lot 🫡