Min Time for Multiple Objects to Meet

Problem Statement

You have K objects on a 1D number line. Object i starts at position positions[i] and can move in either direction at speed speeds[i]. Find the minimum time t >= 0 such that there exists a point on the line that every object can reach by time t.

At time t, object i can be anywhere in the interval [positions[i] - speeds[i] * t, positions[i] + speeds[i] * t]. You are looking for the smallest t where the intersection of all these intervals is non-empty.

Example 1:

Input: positions = [0, 10], speeds = [1, 1]
Output: 5
Explanation: Both meet at position 5 after 5 seconds.

Example 2:

Input: positions = [0, 10, 20], speeds = [1, 2, 4]
Output: ~3.333
Explanation: They can all meet near position ~3.33 after ~3.33 seconds.

Constraints:

• 1 <= K <= 10^5
• 0 <= positions[i], speeds[i] <= 10^6

Difficulty: Hard

---

Pattern Recognition

• What is the structure of the input? Positions and speeds — effectively K 1D intervals that grow with time.
• What are we optimizing? Minimum t such that all intervals intersect.
• What pattern does this suggest? Binary search on the answer, with a feasibility check that computes interval intersection.
• Why does this pattern fit? The feasibility function is monotone: if all intervals intersect at time t, they also intersect at any t' > t (intervals only grow). That monotonicity is exactly what binary search exploits.

---

Approach

Brute Force — Simulate incrementally

Try t = 0, 0.01, 0.02, ... and stop when intervals intersect. Or solve the closed-form in O(K): for each pair, time to meet depends on relative speed. But with K > 2 the pairwise view gets tangled.

Time: O(1/epsilon) for stepping. Space: O(1). Why insufficient: Small epsilons make this impossibly slow for the precision required.

Optimal — Binary Search on Time

Key Insight: The set of t values for which all intervals intersect is an upper-closed half-line (monotone). Binary-search on t; the feasibility check is O(K).

Step-by-step:

1. Define feasible(t):
   • Compute left = max_i(positions[i] - speeds[i] * t).
   • Compute right = min_i(positions[i] + speeds[i] * t).
   • Return left <= right (with a tiny epsilon for floating point).
2. Binary search on t over [0, T_high]. Since time is continuous, iterate a fixed number of times (e.g., 100) which gives ~30 decimal digits of precision.
3. Return hi (tightest upper bound that was feasible).

Time: O(K * iterations) = O(K * log(max_time / epsilon)). Space: O(1).

---

Walkthrough

positions = [0, 10], speeds = [1, 1]. Expected answer: 5.

Iteration	lo	hi	mid	left	right	feasible?
1	0	1e9	5e8	-5e8	5e8	yes -> hi = 5e8
2	0	5e8	2.5e8	...	...	yes -> hi = 2.5e8
...	...	...	...	...	...	binary search converges to 5

For the symmetric case, feasible is true exactly at t=5. After 100 iterations, lo and hi are both ~5 to ~30 digits.

For the three-object case [0,10,20] with [1,2,4], the meeting point satisfies x = p_i + s_i * t signed appropriately — the answer is the tightest meeting time where all three reachable intervals share a point.

---

Implementation

TypeScript

function minTimeToMeet(positions: number[], speeds: number[]): number {
  const n = positions.length;
  const feasible = (t: number): boolean => {
    let left = -Infinity, right = Infinity;
    for (let i = 0; i < n; i++) {
      left = Math.max(left, positions[i] - speeds[i] * t);
      right = Math.min(right, positions[i] + speeds[i] * t);
    }
    return left <= right + 1e-9;
  };

  let lo = 0, hi = 1e9;
  for (let iter = 0; iter < 100; iter++) {
    const mid = (lo + hi) / 2;
    if (feasible(mid)) hi = mid;
    else lo = mid;
  }
  return hi;
}

C++

class Solution {
public:
    double minTimeToMeet(vector<double>& positions, vector<double>& speeds) {
        int n = positions.size();
        auto feasible = [&](double t) {
            double left = -1e18, right = 1e18;
            for (int i = 0; i < n; ++i) {
                left = max(left, positions[i] - speeds[i] * t);
                right = min(right, positions[i] + speeds[i] * t);
            }
            return left <= right + 1e-9;
        };
        double lo = 0, hi = 1e9;
        for (int iter = 0; iter < 100; ++iter) {
            double mid = (lo + hi) / 2;
            if (feasible(mid)) hi = mid;
            else lo = mid;
        }
        return hi;
    }
};

Watch out: Floating point tolerance. Always compare with a small epsilon — strict equality on doubles is a trap.

Watch out: Choosing hi too low. Start with max(positions) - min(positions) divided by min(speeds) or a generous constant like 1e9.

Watch out: Infinite loops if you do while (hi - lo > eps) without a sensible eps. Use a fixed iteration count (100 is plenty for doubles).

---

Complexity Analysis

	Time	Space
Brute Force (step)	O(T / eps)	O(1)
Binary Search	O(K * 100)	O(1)

Bottleneck: The feasibility check is the inner loop; 100 iterations of binary search gives roughly 2^100 precision, more than enough for any reasonable input.

---

Edge Cases

1. One object — Intervals always intersect at its own position. Answer: 0.
2. All objects at same position — Answer: 0.
3. Speed zero for some object — That interval is a point; the answer is whether any single point satisfies all other shrinking windows.
4. All speeds zero and positions differ — Never meet; answer is infinity (or caller-defined). Your hi bound caps it.
5. Two objects moving apart (speed reduces gap) — Works the same; BS still converges.

---

Related Problems

• LC 1011 — Capacity To Ship Packages Within D Days: Binary search on capacity.
• LC 875 — Koko Eating Bananas: Binary search on eating speed.
• LC 1552 — Magnetic Force Between Two Balls: Binary search on minimum distance.
• LC 644 — Maximum Average Subarray II: Binary search on real-valued answer with O(N) feasibility.

---

What Is Expected at Each Level?

Junior / New Grad: May not immediately see binary search. With a nudge to "what quantity grows monotonically?" they get it. Might struggle with floating-point precision.

Mid-level: Identify monotonicity, code up the binary search, and write the O(K) feasibility correctly. Use a fixed iteration count instead of a fragile while loop.

Senior: Discuss the closed-form solutions for K=2 (compare relative speeds, account for direction) and extend to 2D (intersection of disks — the feasibility check becomes harder, typically a convex hull or LP argument). Discuss numeric stability and overflow.