1552. Magnetic Force Between Two Balls

MediumView on LeetCode

Array Binary Search

Intuition

Binary search on minimum distance. Check if we can place m balls with at least mid distance apart.

Algorithm

1Sort positions. Binary search [1, (max-min)/(m-1)].
2Feasibility: greedily place balls, always as far right as possible while maintaining >= mid distance.

Common Pitfalls

•Same pattern as aggressive cows. Sort first. Check if m balls fit with minimum gap >= mid.

1552.cs

// Approach: Binary search on minimum force; validate each mid by greedy placement.
// Time: O(n log n + n log(max-min)) Space: O(1)

public class Solution
{
    public int MaxDistance(int[] position, int m)
    {
        Array.Sort(position);

        int low = 1, high = position[position.Length - 1] - position[0];

        while (low < high)
        {
            int mid = high - (high - low) / 2;
            if (numBalls(position, mid) >= m)
                low = mid;
            else
                high = mid - 1;
        }

        return low;
    }

    private int numBalls(int[] position, int force)
    {
        int balls = 0;
        int prevPosition = -force;

        foreach (int pos in position)
        {
            if (pos - prevPosition >= force)
            {
                balls++;
                prevPosition = pos;
            }
        }

        return balls;
    }
}

Was this solution helpful?