1552. Magnetic Force Between Two Balls

Intuition

The problem requires us to place m balls into n baskets such that the minimum magnetic force (|x - y|) between any two balls is maximized. This can be approached by maximizing the minimum distance between the balls placed in the baskets. To achieve this, we can use a binary search strategy on the potential values of this minimum distance.

Approach

1. Sort the Positions: Begin by sorting the position array. This helps in simplifying the problem since it allows us to perform binary search and check possible distances sequentially.
2. Binary Search: Use binary search to find the maximum minimum distance: - Set the initial range for binary search: lo to 0 and hi to the difference between the maximum and minimum positions in the array. - For each midpoint in the binary search (mid), check if it is possible to place all m balls such that the minimum distance between any two balls is at least mid.
3. Feasibility Check: To determine if a given distance mid is feasible: - Place the first ball in the first basket. - For each subsequent basket, place the next ball only if the distance from the last placed ball is at least mid. - If we can place all m balls this way, the distance mid is feasible.
4. Adjust Binary Search Range: Based on the feasibility check: - If the distance mid is feasible, move the lower bound up (lo = mid + 1) to try for a larger minimum distance. - If the distance mid is not feasible, move the upper bound down (hi = mid).
5. Result: The maximum value of the feasible minimum distance found through binary search will be the answer.

Complexity

• Time complexity: O(n log(maxDistance)) - Sorting the position array takes O(n log n). - The binary search runs in O(log(maxDistance)) where maxDistance is the difference between the maximum and minimum positions. - Each feasibility check takes O(n), iterating through the baskets. - Overall, the time complexity is O(n log n + n log(maxDistance)) which simplifies to O(n log(maxDistance)).
• Space complexity: O(1) - The algorithm uses a constant amount of extra space apart from the input array.

Code

C++

class Solution {
public:
    int maxDistance(vector& position, int m) {
        sort(position.begin(), position.end());
        return bisectLeft(position, m - 1);
    }

private:
    int bisectLeft(const vector& arr, int m) {
        int lo = 0;
        int hi = arr.back() - arr.front();
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            if (isPossible(arr, mid, m)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return isPossible(arr, lo, m) ? lo : lo - 1;
    }

    bool isPossible(const vector& arr, int mid, int m) {
        int prev = arr[0];
        for (int x : arr) {
            if (x - prev >= mid) {
                if (m-- == 1)
                    return true;
                prev = x;
            }
        }
        return false;
    }
};

Python

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        return self.bisectLeft(position, m - 1)

    def bisectLeft(self, arr: List[int], m: int) -> int:
        lo, hi = 0, arr[-1] - arr[0]
        while lo < hi:
            mid = (lo + hi) // 2
            if self.isPossible(arr, mid, m):
                lo = mid + 1
            else:
                hi = mid
        return lo if self.isPossible(arr, lo, m) else lo - 1

    def isPossible(self, arr: List[int], mid: int, m: int) -> bool:
        prev = arr[0]
        for x in arr:
            if x - prev >= mid:
                m -= 1
                if m == 0:
                    return True
                prev = x
        return False

Java

class Solution {
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        return bisectLeft(position, m - 1);
    }

    private int bisectLeft(int[] arr, int m) {
        int lo = 0;
        int hi = arr[arr.length - 1] - arr[0];
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            if (isPossible(arr, mid, m)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return isPossible(arr, lo, m) ? lo : lo - 1;
    }

    private boolean isPossible(int[] arr, int mid, int m) {
        int prev = arr[0];
        for (int x : arr) {
            if (x - prev >= mid) {
                if (m-- == 1) {
                    return true;
                }
                prev = x;
            }
        }
        return false;
    }
}

JavaScript

/**
 * @param {number[]} position
 * @param {number} m
 * @return {number}
 */
var maxDistance = function (position, m) {
  position.sort((a, b) => a - b);
  return bisectLeft(position, m - 1);
};

/**
 * @param {number[]} arr
 * @param {number} m
 * @returns {number} Equal or less than equal value
 */
var bisectLeft = function (arr, m) {
  var lo = 0;
  var hi = arr[arr.length - 1] - arr[0];
  while (lo < hi) {
    var mid = (lo + hi) >> 1;
    isPossible(arr, mid, m) ? (lo = mid + 1) : (hi = mid);
  }
  return isPossible(arr, lo, m) ? lo : lo - 1;
};

/**
 * @param {number[]} arr
 * @param {number} mid
 * @param {number} m
 * @returns {number}
 */
var isPossible = function (arr, mid, m) {
  var prev = arr[0];
  for (var x of arr) {
    if (x - prev >= mid) {
      if (m-- === 1) return true;
      prev = x;
    }
  }
  return false;
};

Go

func maxDistance(position []int, m int) int {
	sort.Ints(position)
	return bisectLeft(position, m-1)
}

func bisectLeft(arr []int, m int) int {
	lo := 0
	hi := arr[len(arr)-1] - arr[0]
	for lo < hi {
		mid := (lo + hi) >> 1
		if isPossible(arr, mid, m) {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	if isPossible(arr, lo, m) {
		return lo
	}
	return lo - 1
}

func isPossible(arr []int, mid, m int) bool {
	prev := arr[0]
	for _, x := range arr {
		if x-prev >= mid {
			if m--; m == 0 {
				return true
			}
			prev = x
		}
	}
	return false
}

C#

public class Solution {
    public int MaxDistance(int[] position, int m) {
        Array.Sort(position);
        return BisectLeft(position, m - 1);
    }

    private int BisectLeft(int[] arr, int m) {
        int lo = 0;
        int hi = arr[arr.Length - 1] - arr[0];
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            if (IsPossible(arr, mid, m)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return IsPossible(arr, lo, m) ? lo : lo - 1;
    }

    private bool IsPossible(int[] arr, int mid, int m) {
        int prev = arr[0];
        foreach (int x in arr) {
            if (x - prev >= mid) {
                if (m-- == 1) {
                    return true;
                }
                prev = x;
            }
        }
        return false;
    }
}

Conclusion

By leveraging binary search on the minimum possible distance between balls and employing a greedy approach to check the feasibility of placing balls at a given distance, we can efficiently determine the maximum possible minimum magnetic force between any two balls in the baskets. Sorting the basket positions initially simplifies the problem, allowing us to focus on the core challenge of distance maximization. This method ensures a time complexity of O(n log(maxDistance)) and a space complexity of O(1), making it a robust solution for the problem.