Magnetic Force Between Two Balls | Simple Thought Process | Leetcode 1552 | codestorywithMIK
Вставка
- Опубліковано 11 жов 2024
- Whatsapp Community Link : www.whatsapp.c...
This is the 30th Video of our Playlist "Binary Search : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a very good and famous Problem on Binary Search on Answer topic : Magnetic Force Between Two Balls | Simple Thought Process | Leetcode 1552 | 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 : Magnetic Force Between Two Balls | Simple Thought Process | Leetcode 1552 | codestorywithMIK
Company Tags : AMAZON
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 :
The approach to finding the maximum minimum distance for placing m balls in an array of positions involves using a combination of binary search and a greedy placement strategy:
Sorting the Positions:
The positions array is sorted to facilitate the calculation of distances between positions.
Binary Search on Distance:
The binary search is used to efficiently find the maximum minimum distance. The search range (minForce to maxForce) starts from 1 to the difference between the maximum and minimum values in the positions array.
Greedy Placement Check:
For a given candidate distance (midpoint in binary search), a helper method possibleToPlace checks if it is possible to place all m balls such that the distance between any two consecutive balls is at least this candidate distance.
The first ball is placed at the first position. Subsequent balls are placed greedily at the next position that is at least the candidate distance away from the last placed ball.
Adjusting the Search Range:
If it is possible to place all m balls with the candidate distance, the search continues with a larger distance by updating the lower bound (minForce).
If it is not possible, the search continues with a smaller distance by updating the upper bound (maxForce).
Result:
The maximum value of the candidate distance that allows placing all m balls is recorded as the result.
This approach ensures that the solution is found efficiently, leveraging the power of binary search to minimize the number of distance checks required.
✨ 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
Sir, aaj bs jaise hi binary search ka intuition hua to 3-4 min mei code krlia and 1st time pe submit hogya, aaj se phle kbhi binary search ka answer khud se ni bna paya sir, thank you so much for yesterday's video.
The moment U told the word BACKTRACK suddenly my heart beats incresed.
A better maxForce value would be (p[n - 1] - p[0]) / (m - 1)
Let's say p[0] is the first element in the array and x is the maxForce. Ideally maxForce should have been the common difference of an arithmetic progression ending at the last element of the sorted array.
So assuming you included p[0] you need (m - 1) more values to make m baskets in total.
The AP would look like p[0], p[0] + x, p[0] + 2x... p[0] + (m - 1)x
To make the best use of the whole array.. the last element of the series should be the last number in the array..
p[0] + (m - 1)x = p[n - 1]
Solve for x and you should get (p[n - 1] - p[0]) / (m - 1)
I have finished your binary search playlist thanks for such a wonderful content
was trying from a while finally got this appreciate your work wish bhai you get more and more success
subh se try kr raha tha alleast video aa hi gaya 🥺🥺 thanku
Hi sir! One request. Can you make a video/ give us a list of all different important patterns in different data structures? maybe with 3-4 good quality problems of each pattern to practice. (eg: binary search on answer and 3-4 quality questions on it). It would help us all a LOT to practice all the essential patterns and cover them at least once.
Question asked by bhaiya to optimize further.
int low = 1, high = (position[position.length - 1] - position[0])/(m-1);
Because m divided itself m-1 times for equals distance.
Bn gya bhaiya bina solution dekhe ❤❤❤ just because of you
I think the better value for maxForce will be maxForce = (maxi-mini)/(m-1);
here, maxi being the max element in the array and mini being the minimum element in the array and m being the number of balls. The intuition being we have to place m balls, and to maximize the minimum distance, the balls should be at max distance from EACH OTHER.
thanks to you. I was able to solve this on my own.
easssssyyy binary search , solved it on my own
Solved it on my own thanks for yesterday's video ❤
Thank you sir. aaj toh khud hi bna liya
This is what I wanted to hear ❤️❤️❤️
No need to see the video. You solved on your own 🙌👌
Thanks to yesterday’s video, i now know the concept and was able to solve this 😬
maxForce can be :
maxForce = (position[n - 1] - position[0] ) / (m - 1)
Assume we have ball a, b, and c
a. b. c
a---b is one part and b---c is one part
If we have m balls then we have m - 1 parts
max difference in the positon can be c - a and to have minimum magnetic force between any two balls to be maximum the balls should be equidistant from each other so the distance between first and last ball i.e. (position[n - 1] - position[0] ) should be equally divided in (m - 1) parts
hence
maxForce = (position[n - 1] - position[0] ) / (m - 1)
What an explanation ❤
Subha subha video aa gya 😂....
Dekhunga nhi abhi, bs comment krne aa gya.
Abhi to try krunga...
usse reach km ho jaegi aagr, youtube algo think ki video aachi nhi h islia log jaldi band kar rhe h
@@kartikforworkvo bhi hai, but solve krne ke baad mai Bhai ka pura solution dekhta hi hu, kuch nya mil jaye sikhne ko
@@kartikforwork😮 aisa bhi hota hai
Thanks for the great video!
I wanted to ask one thing, is there some tag/desc or something that you can add, so when we search "binary search on answer" in your channel, they pop up? (not in thumbnail though, as that reveals the algo when doing leetcode daily challenge)
Sir thank you for the explaination. I have one question though. How do we identify that this is a Binary Search in the Answer type of question?
I was waiting for this solution, I know its bs problem but I was unable to come up with helper function
This problem same as aggressive cow duplicate. Like it if you all agree...
agreed
Here is the code ->
class Solution {
public:
bool canPlace(int force, vector&position,int m)
{
int prev = position[0];
int countBalls = 1;
for(int i = 1; i< position.size();i++)
{
int curr = position[i];
if(curr-prev >= force)
{
countBalls++;
prev=curr;
}
if(countBalls == m)
break;
}
return countBalls == m;
}
public:
int maxDistance(vector& position, int m) {
sort(position.begin(),position.end());
int n= position.size();
int result=0;
int minForce=1;
int maxForce = position[n-1]-position[0];
// Binary Search implementation below
while(minForce O(log(maxForce * n)) , n is the size of the position vector
// sc -> O(1) , no extra space used here
sir next video when segment tree series?
eagerly waiting
maxForce = (position[n - 1] - position[0] )
OR
maxForce = INT_MAX
can you please
make the playlist on BInary Search Problems?
Thoda volume increase kgye sir, full volume pr bhi thk se awaj ni aati
Apologies for the inconvenience.
Will definitely take care of it ❤️
Max force can be max of last elem/2(sir asked for optimisation)
better value for maxForce = position[n-1]/(m-1)
sir aap kitna easy bana dete h Ques or khud se try kro to smjh hi nhi ata h kaise krna h 😢😢
Thanks a lot bhaiya ❤❤
When I used direct loop it gave me tle, but when I used outside function as you did, it gave AC. Why so?
make a video on leetcode 1405 pls
Maxforce value should be position.size()/m where m>2 ...is it correct sir?
ek doubt tha .. is it necessary to keep first ball on first position [0] only?
Thanks bhaiyaan
you are amazing
Same question as aggressive cows....
We can use the same template for this also.
Bhai me solution dekhne aaya tha, tera ye comment dekh ke khud hi solve kar diya
Bhaiya please please please make a video on leetcode 2659 Make array empty I tried to understand it's solution but wasnt able to get it even after 1-2 hrs. Please bhaiya you are my last hope please
int maxForce=(position[n-1]-position[0])/(m-1);
bhaiya dp concepts playlist pura kijiye na
Let me plan this weekend ❤️
@@codestorywithMIK thank you bhaiya ..matrix chain wale concept pe chaiye😄
@@codestorywithMIK ❤️
Thankyou ❤
just apply aggresive cows code
exact same qn as aggressive cows
ty
Bhaiya 9 days ki streak ho gyi but 9 me se 5 days to aapke video dekh kr hi solve Kiya hai
Approach banti hi nhi hai
Meri 33 days ki streak h , meine bas 2 solutions khud se sikhe the 😃 learning is more important and leetcode badge
@@IronmanDon-my6fw but problem khud se kaise solve hoyegi
@@motives748 for that u need to practice very hard , learn all kinds of approaches and problem let's take an example of array , practice all striver sde sheet problems , learn and understand and memorize them , then come on leetcode and practice array questions with brute + optimal and learn from the comments which solution u have never learned
How can we write story for this
this problem is same as aggressive cows problem
does anyone solved it using all combinations -- brute force, then plz send answer , mine is throwing TLE
this is exactly same like agressive cows.
kucch deen se aisa lagg raha hai ki straight forward approach ko ghumaya jaa raha hai🤧😓
Rick and morty got no chill
Indeed 😉
Binary Search on answer smj nhi aa rha
public int maxDistance (int[]position,int m){
Arrays.sort(position);
int s=1,e=(position[position.length-1]-position[0])/(m-1);
while(s=m)
s=mid+1;
else
e=mid-1;
}
return e;
}
private int dist(int[]position,int mid){
int cnt=1,last=position [0];
for(int i=1;i=mid){
cnt++;
last =position[i];
}
return cnt;
}
🎉❤ this is submitted code similar question cocoa eating banana aggressive cow,minimum allocation of books
I dont get why we have to sort?
If you don’t sort, you won’t be able to write the function canPlaceBalls()
Try it without sorting, i am sure you will figure out why sorting is important here
@@codestorywithMIK thanks
🫡🫡🫡
class Solution {
boolean isPossible(int[] position,int mid,int m){
int pre=position[0];
for(int i=1;i=mid){
pre=position[i];
m--;
}
}
return m
bollean ispossible {
---
return m
function me count=1 variable chahiye and count ko increment karna padega
and lets check the condition count==m
try these
I see 2 issues in your code,
1. The return statement of isPossible should be return m == 1. reason is that you have already counted 1 call before the loop starts, so the loop will never be 0.
2. Also, you end position initialization should be end = position[n-1]-position[0].
I ran your code with these 2 modifications and it worked.