You are given an integer n. Consider an equilateral triangle of side length n, broken up into n2 unit equilateral triangles. The triangle has n 1-indexed rows where the ith row has 2i - 1 unit equilateral triangles.
The triangles in the ith row are also 1-indexed with coordinates from (i, 1) to (i, 2i - 1). The following image shows a triangle of side length 4 with the indexing of its triangle.
Two triangles are neighbors if they share a side. For example:
(1,1) and (2,2) are neighbors(3,2) and (3,3) are neighbors.(2,2) and (3,3) are not neighbors because they do not share any side.Initially, all the unit triangles are white. You want to choose k triangles and color them red. We will then run the following algorithm:
Choose the minimum k possible and set k triangles red before running this algorithm such that after the algorithm stops, all unit triangles are colored red.
Return a 2D list of the coordinates of the triangles that you will color red initially. The answer has to be of the smallest size possible. If there are multiple valid solutions, return any.
Example 1:
Input: n = 3 Output: [[1,1],[2,1],[2,3],[3,1],[3,5]] Explanation: Initially, we choose the shown 5 triangles to be red. Then, we run the algorithm: - Choose (2,2) that has three red neighbors and color it red. - Choose (3,2) that has two red neighbors and color it red. - Choose (3,4) that has three red neighbors and color it red. - Choose (3,3) that has three red neighbors and color it red. It can be shown that choosing any 4 triangles and running the algorithm will not make all triangles red.
Example 2:
Input: n = 2 Output: [[1,1],[2,1],[2,3]] Explanation: Initially, we choose the shown 3 triangles to be red. Then, we run the algorithm: - Choose (2,2) that has three red neighbors and color it red. It can be shown that choosing any 2 triangles and running the algorithm will not make all triangles red.
Constraints:
1 <= n <= 1000Problem Overview: You are given an integer n representing the height of a triangular grid. Cells are colored according to a specific rule, and the task is to determine how many cells end up red. A direct simulation quickly becomes expensive as n grows, so the goal is to identify the mathematical pattern behind the coloring process.
Approach 1: Direct Simulation (O(n2) time, O(1) space)
The most straightforward way is to explicitly model the triangle row by row. Row i contains i cells, so you iterate through all rows and apply the coloring rule to each position. This approach mirrors the problem statement and is useful for understanding how the pattern forms. However, the triangle contains n(n+1)/2 cells, which makes simulation quadratic in time. For large values of n, this quickly becomes impractical.
Approach 2: Find the Pattern (O(1) time, O(1) space)
Observing small values of n reveals that the arrangement of red cells follows a repeating mathematical pattern. If you compute the number of red cells for the first several triangle sizes, the results repeat in a fixed cycle. The key insight is that the coloring rule depends only on the relative position of cells, which causes the triangle to repeat its structure every few rows.
Once the repeating structure is identified, you can derive a closed‑form formula based on n. Typically this involves analyzing the triangle size modulo the cycle length (for example n % k) and applying the corresponding arithmetic expression. Instead of iterating through cells, the algorithm directly computes the answer using triangular number relationships and a small constant number of arithmetic operations.
This converts the problem from a grid simulation into a pure math calculation. The implementation becomes a few lines of arithmetic and conditional logic, making it extremely efficient even for very large inputs.
The reasoning relies on recognizing structural repetition in the triangle and translating that observation into a formula. Problems like this commonly appear in math and array pattern questions where brute force is possible but unnecessary.
Recommended for interviews: Interviewers expect the pattern‑based mathematical solution. Starting with a small simulation demonstrates understanding of the grid structure, but recognizing the repeating pattern and reducing the solution to O(1) arithmetic shows stronger problem‑solving ability.
We draw a graph to observe, and we can find that the first row only has one triangle and must be colored, and from the last row to the second row, the coloring scheme of every four rows is the same:
(n, 1), (n, 3), ..., (n, 2n - 1).n - 1 row is colored at (n - 1, 2).n - 2 row is colored at (n - 2, 3), (n - 2, 5), ..., (n - 2, 2n - 5).n - 3 row is colored at (n - 3, 1).
Therefore, we can color the first row according to the above rules, and then start from the last row, and color every four rows once until the second row ends.
The time complexity is (n^2), where n is the parameter given in the problem. Ignoring the space consumption of the answer array, the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation | O(n²) | O(1) | Useful for understanding how the coloring rule behaves on small inputs |
| Pattern / Mathematical Formula | O(1) | O(1) | Best approach when the repeating structure of the triangle is identified |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,262 views views
Watch 9 more video solutions →Practice Color the Triangle Red with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor