<h1>Maximizing Distance on a Square: Turning Geometry into a Linear Problem</h1>
At first glance, this problem looks geometric: points on the boundary of a square, Manhattan distances, and selecting a subset that stays as far apart as possible.
But the real trick?
This isn’t a 2D geometry problem.
It’s a 1D optimization problem in disguise.
Let’s unpack how we transform it—and why that transformation unlocks an efficient solution.
<hr>
<h2>🔍 Problem Insight</h2>
We’re given:
<ul>
<li>A square of side <code>side</code></li>
<li>Points located only on its boundary</li>
<li>A requirement to pick <code>k</code> points such that the minimum Manhattan distance between any pair is maximized</li>
</ul>
This phrasing hints at a classic pattern:
<blockquote>
“Maximize the minimum distance” → Think binary search on the answer
</blockquote>
But before we can apply that, we need a structure that allows efficient distance checking.
<hr>
<h2>🔄 Key Transformation: From 2D → 1D</h2>
The biggest leap in this problem is realizing:
<blockquote>
All boundary points can be mapped to a single circular line (the square’s perimeter).
</blockquote>
We walk along the square edges in a consistent order and assign each point a linear coordinate:
<pre><code>if (x === 0) return y; // left edge
if (y === side) return side + x; // top edge
if (x === side) return side * 3 - y; // right edge
return side * 4 - x; // bottom edge
</code></pre>
This effectively unwraps the square into a **line of length **<code>4 * side</code>.
Now the problem becomes:
<blockquote>
Pick <code>k</code> points on a circular line such that the minimum distance between any two is maximized.
</blockquote>
<hr>
<h2>📏 Why This Works</h2>
Manhattan distance on the square boundary behaves consistently when walking along edges.
By mapping points to perimeter positions:
<ul>
<li>Distance between two points becomes distance along the perimeter</li>
<li>But since the shape is circular, we must also consider the wrap-around gap</li>
</ul>
This duality is crucial for correctness.
<hr>
<h2>⚖️ Binary Search on the Answer</h2>
We now search for the largest minimum distance <code>d</code>.
Search space:
<pre><code>left = 1
right = perimeter / k
</code></pre>
For each candidate <code>d</code>, we ask:
<blockquote>
Can we pick <code>k</code> points such that every adjacent pair is at least <code>d</code> apart?
</blockquote>
<hr>
<h2>✅ Feasibility Check</h2>
This is where the algorithm gets interesting.
<h3>Step 1: Greedy Placement</h3>
Start from the first point and repeatedly pick the next valid point using binary search:
<pre><code>let j = binarySearch(res, curr + d);
</code></pre>
This ensures:
<ul>
<li>Each selected point is at least <code>d</code> away from the previous</li>
</ul>
<hr>
<h3>Step 2: Handle Circular Wrap</h3>
Even if linear distances look valid, the first and last points might be too close across the wrap.
We verify:
<pre><code>res[last] - res[first] &lt;= perimeter - d
</code></pre>
If not, we shift the starting point and try again.
This simulates different “cuts” of the circle into a line.
<hr>
<h2>⚡ Why Binary Search + Greedy Works</h2>
This combination works because:
<ul>
<li>
The feasibility function is monotonic:
</li>
<li>
If distance <code>d</code> works → smaller distances also work
</li>
<li>
Greedy ensures we always take the earliest valid option, maximizing future choices
</li>
</ul>
<hr>
<h2>🧠 Complexity</h2>
<ul>
<li>Sorting: <code>O(n log n)</code></li>
<li>Binary search: <code>O(log(side))</code></li>
<li>Each check: <code>O(k log n)</code></li>
</ul>
Overall:
<blockquote>
O(n log n + log(side) * k log n)
</blockquote>
Efficient enough even for large <code>side</code> values (up to 1e9).
<hr>
<h2>💡 Key Takeaways</h2>
<h3>1. Geometry → Linearization</h3>
Mapping boundary points to a 1D perimeter simplifies everything.
<h3>2. Circular Constraints Matter</h3>
Ignoring the wrap-around leads to incorrect solutions.
<h3>3. Binary Search on Answer</h3>
A powerful pattern when maximizing minimum values.
<h3>4. Greedy + Binary Search Synergy</h3>
Greedy builds candidates; binary search narrows the answer space.
<hr>
<h2>🧪 Final Thought</h2>
This problem is a great example of how:
<blockquote>
The hardest part isn’t coding—it’s seeing the right representation.
</blockquote>
Once you flatten the square into a line, everything else falls into place.
<hr>
<h2>📌 Code (Reference)</h2>
<pre><code>function maxDistance(side: number, points: number[][], k: number): number {
 const res: number[] = points.map(([x, y]) =&gt; {
 if (x === 0) return y;
 if (y === side) return side + x;
 if (x === side) return side * 3 - y;
 return side * 4 - x;
 }).sort((a, b) =&gt; a - b);

 const perimeter: number = side * 4;

 const binarySearch = (arr: number[], target: number): number =&gt; {
 let l = 0, r = arr.length;
 while (l &lt; r) {
 let mid = Math.floor((l + r) / 2);
 if (arr[mid] &lt; target) l = mid + 1;
 else r = mid;
 }
 return l;
 };

 const check = (n: number): boolean =&gt; {
 const m = res.length;
 let idx: number[] = new Array(k).fill(0);
 let curr = res[0];

 for (let i = 1; i &lt; k; i++) {
 let j = binarySearch(res, curr + n);
 if (j === m) return false;
 idx[i] = j;
 curr = res[j];
 }

 if (res[idx[k - 1]] - res[0] &lt;= perimeter - n) return true;

 for (idx[0] = 1; idx[0] &lt; idx[1]; idx[0]++) {
 for (let j = 1; j &lt; k; j++) {
 while (idx[j] &lt; m &amp;&amp; res[idx[j]] &lt; res[idx[j - 1]] + n) {
 idx[j]++;
 }
 if (idx[j] === m) return false;
 }
 if (res[idx[k - 1]] - res[idx[0]] &lt;= perimeter - n) return true;
 }
 return false;
 };

 let left = 1, right = Math.floor(perimeter / k) + 1;

 while (left + 1 &lt; right) {
 let mid = Math.floor((left + right) / 2);
 if (check(mid)) left = mid;
 else right = mid;
 }

 return left;
}
</code></pre>
<hr>
If you enjoy problems where a clever perspective shift turns complexity into simplicity, this one is worth revisiting.