Magnetic Force Between Two Balls | Simple Thought Process | Leetcode 1552 | codestorywithMIK
Vložit
- čas přidán 18. 06. 2024
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
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/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/magneti...
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/MAZHARMIK/Intervie...
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)
subh se try kr raha tha alleast video aa hi gaya 🥺🥺 thanku
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
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.
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.
Bn gya bhaiya bina solution dekhe ❤❤❤ just because of you
thanks to you. I was able to solve this 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 😬
easssssyyy binary search , solved it on my own
Thanks a lot bhaiya ❤❤
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.
you are amazing
This problem same as aggressive cow duplicate. Like it if you all agree...
agreed
Thankyou ❤
Thanks bhaiyaan
maxForce = (position[n - 1] - position[0] )
OR
maxForce = INT_MAX
ty
better value for maxForce = position[n-1]/(m-1)
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)
Max force can be max of last elem/2(sir asked for optimisation)
int maxForce=(position[n-1]-position[0])/(m-1);
I was waiting for this solution, I know its bs problem but I was unable to come up with helper function
Thoda volume increase kgye sir, full volume pr bhi thk se awaj ni aati
Apologies for the inconvenience.
Will definitely take care of it ❤️
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?
can you please
make the playlist on BInary Search Problems?
Maxforce value should be position.size()/m where m>2 ...is it correct sir?
sir next video when segment tree series?
eagerly waiting
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 ❤
sir aap kitna easy bana dete h Ques or khud se try kro to smjh hi nhi ata h kaise krna h 😢😢
make a video on leetcode 1405 pls
When I used direct loop it gave me tle, but when I used outside function as you did, it gave AC. Why so?
just apply aggresive cows code
exact same qn as aggressive cows
ek doubt tha .. is it necessary to keep first ball on first position [0] only?
this problem is same as aggressive cows problem
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
kucch deen se aisa lagg raha hai ki straight forward approach ko ghumaya jaa raha hai🤧😓
How can we write story for this
this is exactly same like agressive cows.
does anyone solved it using all combinations -- brute force, then plz send answer , mine is throwing TLE
bhaiya dp concepts playlist pura kijiye na
Let me plan this weekend ❤️
@@codestorywithMIK thank you bhaiya ..matrix chain wale concept pe chaiye😄
@@codestorywithMIK ❤️
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
Binary Search on answer smj nhi aa rha
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
Rick and morty got no chill
Indeed 😉
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
🫡🫡🫡
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
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.