Color the Triangle Red - Solution & Explanation

Q: Is Color the Triangle Red easy or hard?

The problem is rated Hard because the intended solution requires recognizing a non‑obvious mathematical pattern. The coding portion is simple once the pattern is derived, but discovering the formula without brute force experimentation can be challenging.

Q: Color the Triangle Red Python/Java solution

The implementation is short once the pattern is known. The code simply checks the remainder of n within the repeating cycle and returns the corresponding formula result. FleetCode provides implementations in Python, Java, C++, Go, and TypeScript.

Q: How to solve Color the Triangle Red in O(1)?

Compute the number of red cells for the first few triangle sizes and observe the repeating pattern. The result follows a fixed cycle based on n modulo a small constant. Once that relationship is identified, use a closed‑form expression that depends only on n and its remainder in the cycle, eliminating any loops.

Q: What is the best approach for Color the Triangle Red?

The optimal approach is to detect the repeating mathematical pattern in how red cells appear as the triangle grows. After computing results for the first few values of n, a cycle emerges that allows the answer to be derived using a constant‑time formula. This reduces the complexity from quadratic simulation to O(1) time with O(1) space.

Q: Is Color the Triangle Red asked at Google/Amazon/Meta?

Pattern‑recognition and mathematical reasoning problems like this appear frequently in technical interviews at companies such as Google, Amazon, and Meta. While the exact problem may vary, identifying repeating structures and converting simulations into formulas is a common interview skill.

Q: What data structure is used in Color the Triangle Red?

The optimized solution does not require complex data structures. It relies mainly on arithmetic operations and pattern recognition. During exploration you might use arrays or simple loops to compute early values, but the final solution uses constant space.

Q: What is the time complexity of Color the Triangle Red?

A naive simulation checks every cell in the triangular grid, which takes O(n^2) time because the triangle contains n(n+1)/2 cells. The optimized pattern‑based solution computes the answer directly using arithmetic, giving O(1) time and O(1) space complexity.

HardPremiumFree on FleetCodeArray Math11 min read

Practice this problem

Problem Statement

You are given an integer n. Consider an equilateral triangle of side length n, broken up into n² unit equilateral triangles. The triangle has n 1-indexed rows where the i^th row has 2i - 1 unit equilateral triangles.

The triangles in the i^th 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:

Triangles (1,1) and (2,2) are neighbors
Triangles (3,2) and (3,3) are neighbors.
Triangles (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 a white triangle that has at least two red neighbors.
- If there is no such triangle, stop the algorithm.
Color that triangle red.
Go to step 1.

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 <= 1000

Approach Overview

Problem 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(n²) 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.

Solution

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:

The last row is colored at (n, 1), (n, 3), ..., (n, 2n - 1).
The n - 1 row is colored at (n - 1, 2).
The n - 2 row is colored at (n - 2, 3), (n - 2, 5), ..., (n - 2, 2n - 5).
The 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).

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

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

Video Solution

LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,262 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Color the Triangle Red easy or hard?

The problem is rated Hard because the intended solution requires recognizing a non‑obvious mathematical pattern. The coding portion is simple once the pattern is derived, but discovering the formula without brute force experimentation can be challenging.

Color the Triangle Red Python/Java solution

The implementation is short once the pattern is known. The code simply checks the remainder of n within the repeating cycle and returns the corresponding formula result. FleetCode provides implementations in Python, Java, C++, Go, and TypeScript.

How to solve Color the Triangle Red in O(1)?

Compute the number of red cells for the first few triangle sizes and observe the repeating pattern. The result follows a fixed cycle based on n modulo a small constant. Once that relationship is identified, use a closed‑form expression that depends only on n and its remainder in the cycle, eliminating any loops.

What is the best approach for Color the Triangle Red?

The optimal approach is to detect the repeating mathematical pattern in how red cells appear as the triangle grows. After computing results for the first few values of n, a cycle emerges that allows the answer to be derived using a constant‑time formula. This reduces the complexity from quadratic simulation to O(1) time with O(1) space.

Is Color the Triangle Red asked at Google/Amazon/Meta?

Pattern‑recognition and mathematical reasoning problems like this appear frequently in technical interviews at companies such as Google, Amazon, and Meta. While the exact problem may vary, identifying repeating structures and converting simulations into formulas is a common interview skill.

What data structure is used in Color the Triangle Red?

The optimized solution does not require complex data structures. It relies mainly on arithmetic operations and pattern recognition. During exploration you might use arrays or simple loops to compute early values, but the final solution uses constant space.

What is the time complexity of Color the Triangle Red?

A naive simulation checks every cell in the triangular grid, which takes O(n^2) time because the triangle contains n(n+1)/2 cells. The optimized pattern‑based solution computes the answer directly using arithmetic, giving O(1) time and O(1) space complexity.

Ready to solve this problem?

Practice Color the Triangle Red with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyHard

Acceptance58.0%

Approaches1

Reading time11 min