Counting Squares in an N x N Grid

Combinatorics · Easy · Free problem

You have an $n \times n$ grid made up of $n^2$ unit squares (

\times 1$). How many squares of any size (from
\times 1$ up to $n \times n$) can be formed on this grid?

Give a closed-form formula in terms of $n$, and compute the answer for $n = 10$.

Hints

  1. Count squares by size: how many $k \times k$ squares fit in the $n \times n$ grid?
  2. A $k \times k$ square has $(n - k + 1)^2$ possible positions. Sum this over $k = 1$ to $n$.
  3. Use the sum of squares formula: $\sum_{m=1}^n m^2 = n(n+1)(2n+1)/6$.

Worked Solution

How to Think About It: Break the count by square size. A $k \times k$ square needs to fit inside the $n \times n$ grid, so its top-left corner can be placed at any position $(i, j)$ where

\leq i \leq n - k + 1$ and
\leq j \leq n - k + 1$. That gives $(n - k + 1)^2$ placements for each size $k$. Sum over all sizes.

Quick Estimate: The total is $\sum_{k=1}^n (n-k+1)^2 = \sum_{m=1}^n m^2$. For $n = 10$:

+ 4 + 9 + 16 + 25 + 36 + 49 + 64 + 81 + 100 = 385$.

Approach: Count by square size and apply the sum of squares formula.

Formal Solution:

For each $k = 1, 2, \ldots, n$, a $k \times k$ square can be placed with its top-left corner at any of $(n - k + 1)$ rows and $(n - k + 1)$ columns. So there are $(n - k + 1)^2$ squares of size $k \times k$.

The total count is:

$\sum_{k=1}^{n} (n - k + 1)^2 = \sum_{m=1}^{n} m^2 = \frac{n(n+1)(2n+1)}{6}$

where we substituted $m = n - k + 1$.

For $n = 10$:

$\frac{10 \cdot 11 \cdot 21}{6} = \frac{2310}{6} = 385$

Verification by direct count: -

\times 1$:
00$ -
\times 2$: $81$ - $3 \times 3$: $64$ - $4 \times 4$: $49$ - $5 \times 5$: $36$ - $6 \times 6$: 5$ - $7 \times 7$:
6$ - $8 \times 8$: $9$ - $9 \times 9$: $4$ -
0 \times 10$:
$ - Total:
00 + 81 + 64 + 49 + 36 + 25 + 16 + 9 + 4 + 1 = 385$ .

Answer: The total number of squares is $\dfrac{n(n+1)(2n+1)}{6}$. For $n = 10$, the answer is $385$.

Intuition

This is a counting exercise that teaches a universally useful technique: when objects come in different sizes, count each size separately and sum. The key observation is that a $k \times k$ square in an $n \times n$ grid has $(n-k+1)^2$ valid placements, because the top-left corner is constrained to a smaller grid. The re-indexing $m = n - k + 1$ turns the sum into the familiar $\sum m^2$, which has the clean closed form $n(n+1)(2n+1)/6$.

This problem appears in interviews because it tests whether you can systematically decompose a combinatorial question. The same "count by size and sum" strategy applies to counting rectangles in a grid (which gives $\binom{n+1}{2}^2$ for an $n \times n$ grid), counting substrings of a string, or counting subarrays -- all common algorithmic building blocks.

Open the full interactive solver →