Filling the grid

Let’s state the problem: place a $b \times a \in \N$ grid (rows × columns) into a $w \times h \in \R^{+}$ rectangle which fits $n \in \N$ squares such that the side length of the squares $s \in \R^{+}$ is maximized and the grid does not overflow the rectangle. Since the side length is maximized, the grid will fit in the rectangle’s full width or height, or both if a perfect fit is possible. Formally:

$$\brk[0]{\begin{gather*}} \brk{\begin{align*}} S_w \brk{&}\coloneqq \big\{\, s \in \R^{+} \mid \exist a, b \in \N \text{ . } \brk \brk{&\hspace{2.3em}}n \le ab \land as = w \land bs \le h \,\big\} \\ S_h \brk{&}\coloneqq \big\{\, s \in \R^{+} \mid \exist a, b \in \N \text{ . } \brk \brk{&\hspace{2.3em}}n \le ab \land as \le h \land bs = h \,\big\} \\ s \brk{&}\coloneqq \max (S_w \cup S_h). \brk[0]{\end{gather*}} \brk{\end{align*}}$$$$\begin{array}{c}{S}_w:=\{s\in {\mathbb{R}}^{+}\mid \exists a,b\in \mathbb{N}\text{ . }n\le ab\wedge as=w\wedge bs\le h\}\\ S_h:=\{s\in {\mathbb{R}}^{+}\mid \exists a,b\in \mathbb{N}\text{ . }n\le ab\wedge as\le h\wedge bs=h\}\\ s:=\max (S_w\cup S_h).\end{array}$$$$\begin{array}{rl}{S}_w& :=\{s\in {\mathbb{R}}^{+}\mid \exists a,b\in \mathbb{N}\text{ . }\\ & n\le ab\wedge as=w\wedge bs\le h\}\\ S_h& :=\{s\in {\mathbb{R}}^{+}\mid \exists a,b\in \mathbb{N}\text{ . }\\ & n\le ab\wedge as\le h\wedge bs=h\}\\ s& :=\max (S_w\cup S_h).\end{array}$$

$s_w \in S_w$ is a fit‑width solution, $s_h \in S_h$ a fit‑height solution. The final solution $s$ is the desired maximal side length. Our target is to build an algorithm to find $s$.

Observe that for any fixed $b$ we can always take $a = \left\lceil \frac{n}{b} \right\rceil$ to obtain a grid which fits $n$ squares, since clearly $n \le ab$. For this grid $(a, b)$ let $s' = \min \big\{ \frac{w}{a}, \frac{h}{b} \big\}$ its corresponding side length; it’s easy to see that $s' \in S_w \cup S_h$. We can just test all $1 \le b \le n$ and pick the maximum $s'$ to obtain the solution $s$:

function fillGrid(n, w, h) {
  let s = 0;
  for (let b = 1; b <= n; b++) {
    s = Math.max(s, Math.min(w / Math.ceil(n / b), h / b));
  }
  return s;
}

The asymptotic complexity is $\mathcal{O}(n)$. To improve this, notice that if $a \le \sqrt{n}$ there are obviously $\mathcal{O}(\sqrt{n})$ distinct values of $a$. If $a > \sqrt{n}$:

$$\left\lceil \frac{n}{b} \right\rceil > \sqrt{n} \implies \frac{n}{b} + 1 > \sqrt{n} \implies b < \frac{n}{\sqrt{n} - 1} = \sqrt{n} + 1 + \frac{1}{\sqrt{n} - 1}.$$$$\lceil \frac{n}{b}\rceil >\sqrt{n}⟹\frac{n}{b}+1>\sqrt{n}⟹b<\frac{n}{\sqrt{n}-1}=\sqrt{n}+1+\frac{1}{\sqrt{n}-1}.$$

Therefore $a > \sqrt{n} \implies b \le \mathcal{O}(\sqrt{n})$, so in all cases there are $\mathcal{O}(\sqrt{n})$ distinct $a$ values. Clever incrementing of $b$ could then achieve complexity $\mathcal{O}(\sqrt{n})$. But for my grid with $n = 10^{20}$ squares this isn’t good enough – can we do better?

The solution statement as it stands juggles a lot of variables. We can rewrite the grid dimension constraints using only $a, b, w, h$:

$$\begin{gather*} as_w = w \land bs_w \le h \brk \iff a \ge \frac{w}{h}b \land s_w = \frac{w}{a}, \brk[0]{\\} \brk{\\[1.2em]} bs_h = h \land as_h \le w \brk \iff b \ge \frac{h}{w}a \land s_h = \frac{h}{b}. \end{gather*}$$$$\begin{array}{c}a{s}_w=w\wedge b{s}_w\le h⟺a\ge \frac{w}{h}b\wedge s_w=\frac{w}{a},\\ b{s}_h=h\wedge a{s}_h\le w⟺b\ge \frac{h}{w}a\wedge s_h=\frac{h}{b}.\end{array}$$$$\begin{array}{c}a{s}_w=w\wedge b{s}_w\le h\\ ⟺a\ge \frac{w}{h}b\wedge s_w=\frac{w}{a},\\ b{s}_h=h\wedge a{s}_h\le w\\ ⟺b\ge \frac{h}{w}a\wedge s_h=\frac{h}{b}.\end{array}$$

$s$ is now dependent on the grid and rectangle dimensions. Using $r \coloneqq \frac{w}{h}$, the rectangle’s aspect ratio:

$$\brk[0]{\begin{gather*}} \brk{\begin{align*}} a_w \brk{&}\coloneqq \min \big\{\, a \in \N \mid \exist b \in \N \text{ . } \brk \brk{&\hspace{4.15em}}n \le ab \land a \ge rb \,\big\} \\ b_h \brk{&}\coloneqq \min \brk[0]{\bigg}\brk{\big}\{\, b \in \N \mid \exist a \in \N \text{ . } \brk \brk{&\hspace{4.15em}}n \le ab \land b \ge \frac{a}{r} \,\bigg\} \\ s \brk{&}= \max \Set{ \frac{w}{a_w}, \frac{h}{b_h}}. \brk[0]{\end{gather*}} \brk{\end{align*}}$$$$\begin{array}{c}{a}_w:=\min \{a\in \mathbb{N}\mid \exists b\in \mathbb{N}\text{ . }n\le ab\wedge a\ge rb\}\\ b_h:=\min \{b\in \mathbb{N}\mid \exists a\in \mathbb{N}\text{ . }n\le ab\wedge b\ge \frac{a}{r}\}\\ s=\max \left\{\frac{w}{a_w},\frac{h}{b_h}\right\}.\end{array}$$$$\begin{array}{rl}{a}_w& :=\min \{a\in \mathbb{N}\mid \exists b\in \mathbb{N}\text{ . }\\ & n\le ab\wedge a\ge rb\}\\ b_h& :=\min \{b\in \mathbb{N}\mid \exists a\in \mathbb{N}\text{ . }\\ & n\le ab\wedge b\ge \frac{a}{r}\}\\ s& =\max \left\{\frac{w}{a_w},\frac{h}{b_h}\right\}.\end{array}$$

$a_w$ is the column count of the fit‑width grid, $b_h$ the row count of the fit‑height grid. They are minimized since the side length is inversely proportional. The side length is a trivial result of the grid dimensions; only the algorithm for finding $a_w$ and $b_h$ remains to be developed.

Let’s take a look at a fit‑width grid with dimensions $(a_w, b_w) \in \N^2$. $b_w$ can be abstracted away:

$${n \le a_wb_w \land a_w \ge rb_w} \iff {\frac{n}{a_w} \le b_w \le \frac{a_w}{r}} \iff {\left\lceil \frac{n}{a_w} \right\rceil \le \left\lfloor \frac{a_w}{r} \right\rfloor}.$$$$n\le a_w{b}_w\wedge a_w\ge r{b}_w⟺\frac{n}{a_w}\le b_w\le \frac{a_w}{r}⟺\lceil \frac{n}{a_w}\rceil \le \lfloor \frac{a_w}{r}\rfloor .$$

This is a range for all $b_w$ corresponding to $a_w$. With an analogous derivation for $b_h$, we get:

$$\begin{gather*} a_w = \min \Set{ a \in \N \mid \left\lfloor \frac{a}{r} \right\rfloor \ge \left\lceil \frac{n}{a} \right\rceil }, \brk[0]{\quad} \brk b_h = \min \Set{ b \in \N \mid \left\lfloor rb \right\rfloor \ge \left\lceil \frac{n}{b} \right\rceil }. \end{gather*}$$$$\begin{array}{c}{a}_w=\min \left\{a\in \mathbb{N}\mid \lfloor \frac{a}{r}\rfloor \ge \lceil \frac{n}{a}\rceil \right\},b_h=\min \left\{b\in \mathbb{N}\mid \lfloor rb\rfloor \ge \lceil \frac{n}{b}\rceil \right\}.\end{array}$$$$\begin{array}{c}{a}_w=\min \left\{a\in \mathbb{N}\mid \lfloor \frac{a}{r}\rfloor \ge \lceil \frac{n}{a}\rceil \right\},\\ b_h=\min \left\{b\in \mathbb{N}\mid \lfloor rb\rfloor \ge \lceil \frac{n}{b}\rceil \right\}.\end{array}$$

Since the second comparison term is non‑increasing in $a,$ respectively in $b,$ it follows that every $a > a_w$ and $b > b_h$ would satisfy the solution condition. The algorithm idea is thus the following: starting from an initial guess $a_0 \le a_w$ (and $b_0 \le b_h$) test every value until the solution condition holds, i.e. loop while:

$$\begin{gather*} \left\lfloor \frac{a}{r} \right\rfloor < \left\lceil \frac{n}{a} \right\rceil \iff a < r \left\lceil \frac{n}{a} \right\rceil, \brk[0]{\quad} \brk \left\lfloor rb \right\rfloor < \left\lceil \frac{n}{b} \right\rceil \iff rb < \left\lceil \frac{n}{b} \right\rceil. \end{gather*}$$$$\begin{array}{c}\lfloor \frac{a}{r}\rfloor <\lceil \frac{n}{a}\rceil ⟺a<r\lceil \frac{n}{a}\rceil ,\lfloor rb\rfloor <\lceil \frac{n}{b}\rceil ⟺rb<\lceil \frac{n}{b}\rceil .\end{array}$$$$\begin{array}{c}\lfloor \frac{a}{r}\rfloor <\lceil \frac{n}{a}\rceil ⟺a<r\lceil \frac{n}{a}\rceil ,\\ \lfloor rb\rfloor <\lceil \frac{n}{b}\rceil ⟺rb<\lceil \frac{n}{b}\rceil .\end{array}$$

Only the initial guesses $a_0$ and $b_0$ remain to be made. From the solution condition of $a_w$:

$${a_w \ge r \left\lceil \frac{n}{a_w} \right\rceil} \implies {{a_w}^2 \ge rn} \implies {a_w \ge \sqrt{rn}}.$$$$a_w\ge r\lceil \frac{n}{a_w}\rceil ⟹{a_w}^2\ge rn⟹a_w\ge \sqrt{rn}.$$

Since $a_w \in \N$ it can therefore be no smaller than $a_0 = \left\lceil a^* \right\rceil$, with $a^* \coloneqq \sqrt{rn}$. Likewise, $b_w \ge \left\lceil b^* \right\rceil$, with $b^* \coloneqq \sqrt{\frac{n}{r}}$. Using the loop condition above, an algorithm can finally be built:

function fillGrid(n, w, h) {
  const r = w / h

  let a = Math.ceil(Math.sqrt(r * n))
  for (; a < r * Math.ceil(n / a); a++)

  let b = Math.ceil(Math.sqrt(n / r))
  for (; r * b < Math.ceil(n / b); b++)

  return Math.max(w / a, h / b)
}

To analyze the runtime complexity, observe that since $a_0 \le a < r\left\lceil{\frac{n}{a}}\right\rceil \le r \big\lceil \frac{n}{a_0} \big\rceil$, $a$ is incremented at most $\big\lceil{r\big\lceil{\frac{n}{a_0}}\big\rceil - a_0}\big\rceil$ times. An upper bound on the iteration count is:

$$\begin{align*} \brk{&}\left\lceil{r\left\lceil{\frac{n}{a_0}}\right\rceil - a_0}\right\rceil \brk &< r \left\lceil{\frac{n}{a_0}}\right\rceil - a_0 + 1 \\ &< r \frac{n}{a_0} + r -a_0 + 1 \\ &= r\frac{n}{\left\lceil \sqrt{rn} \right\rceil} + r - \left\lceil\sqrt{rn}\right\rceil + 1 \\ &< \frac{rn}{\sqrt{rn}} + r - \sqrt{rn} + 1 \\ &= r + 1. \end{align*}$$$$\begin{array}{rl}\lceil r\lceil \frac{n}{a_0}\rceil -a_0\rceil & <r\lceil \frac{n}{a_0}\rceil -a_0+1\\ & <r\frac{n}{a_0}+r-a_0+1\\ & =r\frac{n}{\lceil \sqrt{rn}\rceil }+r-\lceil \sqrt{rn}\rceil +1\\ & <\frac{rn}{\sqrt{rn}}+r-\sqrt{rn}+1\\ & =r+1.\end{array}$$$$\begin{array}{rl}& \lceil r\lceil \frac{n}{a_0}\rceil -a_0\rceil \\ & <r\lceil \frac{n}{a_0}\rceil -a_0+1\\ & <r\frac{n}{a_0}+r-a_0+1\\ & =r\frac{n}{\lceil \sqrt{rn}\rceil }+r-\lceil \sqrt{rn}\rceil +1\\ & <\frac{rn}{\sqrt{rn}}+r-\sqrt{rn}+1\\ & =r+1.\end{array}$$

This means at most $\left\lfloor r \right\rfloor + 1$ iterations. This bound is tight: for $n = 33, r = \frac{1}{8.3}$ the fit‑width loop does $1 = \lfloor r \rfloor + 1$ iteration, reaching the upper bound. Similarly for the second loop we get a tight upper bound of $\left\lfloor \frac{1}{r} \right\rfloor + 1$ iterations. The runtime is therefore $\mathcal{O}(R)$ with $R = \max \Set{r, \frac{1}{r}}$. One could binary search over $\left[a_0, a_0 + \lfloor r \rfloor + 1\right]$ and $\left[b_0, b_0 + \left\lfloor \frac{1}{r} \right\rfloor + 1\right]$ to reduce complexity to $\mathcal{O}(\log R)$.

My $n = 10^{20}$ grid is a piece of cake now, but my $r = 2 \uarr \uarr 6$ grid still requires around $10^{19700}$ iterations. There are $10^{80}$ atoms in the observable universe. Can we do better?

Let’s return to the initial algorithm. It iterates through all solutions $\left(a = \left\lceil \frac{n}{b} \right\rceil, b\right)$ for $1 \le b \le n$. It must find the optimal $s$: any other $a' > a$ is worse, as at each step the side length $s' = \min \big\{\frac{w}{a'}, \frac{h}{b} \big\} \le \min \big\{\frac{w}{a}, \frac{h}{b} \big\}$, and any other $b' > n$ does not help, since it would correspond to a solution $(1, b')$ with $s' = \min \big\{ w, \frac{h}{b'} \big\} \le \min \big\{ w, \frac{h}{n} \big\}$, with the latter value being the side length of $(1, n)$, a solution that’s tested.

Consider then what happens when $b \le b^* = \sqrt{\frac{n}{r}}$:

$${b \le \sqrt{\frac{n}{r}}} \implies {rb \le \frac{n}{b} \le a} \implies {\frac{h}{b} \ge \frac{w}{a}} \implies {s' = \frac{w}{\left\lceil \frac{n}{b} \right\rceil}}.$$$$b\le \sqrt{\frac{n}{r}}⟹rb\le \frac{n}{b}\le a⟹\frac{h}{b}\ge \frac{w}{a}⟹s^{\prime }=\frac{w}{\lceil \frac{n}{b}\rceil }.$$

Every solution tested is fit‑width and to maximize the side length we must take $b = \lfloor b^* \rfloor$. Consider now $b \ge b^*$:

$$b \ge \sqrt{\frac{n}{r}} \implies rb \ge \frac{n}{b} \implies {\underbrace{rb > \left\lceil \frac{n}{b} \right\rceil}_{\text{(1)}} \lor \underbrace{\left\lceil \frac{n}{b} \right\rceil \ge rb}_{\text{(2)}}}.$$$$b\ge \sqrt{\frac{n}{r}}⟹rb\ge \frac{n}{b}⟹\underset{\text{(1)}}{\underbrace{rb>\lceil \frac{n}{b}\rceil }}\vee \underset{\text{(2)}}{\underbrace{\lceil \frac{n}{b}\rceil \ge rb}}.$$

In case $(1)$ the solution $(a = \left\lceil \frac{n}{b} \right\rceil, b)$ is clearly fit‑height, so $s' = \frac{h}{b}$ is maximized when $b \ge b^*$ by $b = \lceil b^* \rceil$. To tackle case $(2)$ we’ll assume that $r \ge 1$; it then follows:

$$\begin{align*} \brk[3,]{&}rb \le \left\lceil \frac{n}{b} \right\rceil < \frac{n}{b} + 1 \brk[3,] \implies &rb^2 - b - n < 0 \brk \implies \brk[1,]{&}b < \frac{1}{2r}+\sqrt{\frac{1}{4r^2} + \frac{n}{r}} \\ \implies &b < \frac{1}{2} + \sqrt{\left(\frac{1}{2} + \sqrt{\frac{n}{r}}\right)^2} \brk[,1]{=} \brk[2,]{\\ \implies &b <} \sqrt{\frac{n}{r}} + 1 \end{align*}$$$$\begin{array}{rl}rb\le \lceil \frac{n}{b}\rceil <\frac{n}{b}+1⟹& r{b}^2-b-n<0⟹b<\frac{1}{2r}+\sqrt{\frac{1}{4r^2}+\frac{n}{r}}\\ ⟹& b<\frac{1}{2}+\sqrt{{\left(\frac{1}{2}+\sqrt{\frac{n}{r}}\right)}^2}=\sqrt{\frac{n}{r}}+1\end{array}$$$$\begin{array}{rl}rb\le \lceil \frac{n}{b}\rceil <\frac{n}{b}+1⟹& r{b}^2-b-n<0\\ ⟹& b<\frac{1}{2r}+\sqrt{\frac{1}{4r^2}+\frac{n}{r}}\\ ⟹& b<\frac{1}{2}+\sqrt{{\left(\frac{1}{2}+\sqrt{\frac{n}{r}}\right)}^2}=\sqrt{\frac{n}{r}}+1\end{array}$$$$\begin{array}{rl}rb\le \lceil \frac{n}{b}\rceil <\frac{n}{b}+1⟹& r{b}^2-b-n<0\\ ⟹& b<\frac{1}{2r}+\sqrt{\frac{1}{4r^2}+\frac{n}{r}}\\ ⟹& b<\frac{1}{2}+\sqrt{{\left(\frac{1}{2}+\sqrt{\frac{n}{r}}\right)}^2}\\ ⟹& b<\sqrt{\frac{n}{r}}+1\end{array}$$$$\begin{array}{rl}& rb\le \lceil \frac{n}{b}\rceil <\frac{n}{b}+1\\ ⟹& r{b}^2-b-n<0\\ ⟹& b<\frac{1}{2r}+\sqrt{\frac{1}{4r^2}+\frac{n}{r}}\\ ⟹& b<\frac{1}{2}+\sqrt{{\left(\frac{1}{2}+\sqrt{\frac{n}{r}}\right)}^2}\\ ⟹& b<\sqrt{\frac{n}{r}}+1\end{array}$$

Under both assumptions about $b$ and $r$ we have $b^* \le b < b^* + 1$, thus, simply by definition of the ceiling function, $b = \left\lceil b^* \right\rceil$. Hence when $r \ge 1$ only $b \in \Set{ \lfloor b^* \rfloor, \lceil b^* \rceil }$ can ever maximize the side length.

To tackle $r \le 1$, notice the symmetry of the problem with respect to $r$. Taking $r' \coloneqq \frac{1}{r}$ just rotates the original rectangle by $90^\circ$ – the side length of the squares remains the same, the number of rows and columns swap. Using the result above, for $r \le 1$ the optimal grid $(a, b)$ must have $a \in \Set{ \lfloor a^* \rfloor, \lceil a^* \rceil }$, with $a^* = \sqrt{rn} = \sqrt{\frac{n}{r'}}$, and $(a, b) = (b', a')$, where $(a', b')$ is the optimal grid for $r'$.

With this we have exhaustively covered the input domain. The $\mathcal{O}(1)$ algorithm we’ve all been waiting for is…

function fillGrid(n, w, h) {
  const r = w / h;
  if (r < 1) return fillGrid(n, h, w);
  const s = (b) => Math.min(w / Math.ceil(n / b), h / b);
  const bs = Math.sqrt(n / r);
  return Math.max(s(Math.floor(bs)), s(Math.ceil(bs)));
}

If you’ve found the proofs hard to follow, use a graph: plot the functions $\frac{n}{x}$ and $\frac{x}{r}$ and the solution points $(a, b)$ and interpret geometrically. Here’s Desmos.

For additional context, this problem is a particular case of integer programming. There exist general algorithms to solve such problems but the best time complexity they can achieve here is still $\mathcal{O}(\log R)$.

Lastly, a challenge! Prove that when a fit‑width solution $(a_w, b_w)$ is the best, i.e. $s_w > s_h$ for all $(a_h, b_h)$ fit‑height, there is no $b \ne b_w$ such that $(a_w, b)$ is fit‑width. Check Uniqueness of fit‑width solution if you get stuck.