Skip to content

2647. Color the Triangle Red 👎

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  vector<vector<int>> colorRed(int n) {
    vector<vector<int>> ans;
    const int tipSize = n % 4;

    // Tip of the triangle is always painted red.
    if (tipSize >= 1)
      ans.push_back({1, 1});

    // Paint most right and most left elements at the following rows.
    for (int i = 2; i <= tipSize; ++i) {
      ans.push_back({i, 1});
      ans.push_back({i, 2 * i - 1});
    }

    // Paint 4-row chunks.
    for (int i = tipSize + 1; i < n; i += 4) {
      // Fill the 1st row of the chunk.
      ans.push_back({i, 1});
      // Fill the 2nd row.
      for (int j = 1; j <= i; ++j)
        ans.push_back({i + 1, 2 * j + 1});
      // Fill the 3rd row.
      ans.push_back({i + 2, 2});
      // Fill the 4th row.
      for (int j = 0; j <= i + 2; ++j)
        ans.push_back({i + 3, 2 * j + 1});
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public int[][] colorRed(int n) {
    List<int[]> ans = new ArrayList<>();
    final int tipSize = n % 4;
    // Tip of the triangle is always painted red.
    if (tipSize >= 1)
      ans.add(new int[] {1, 1});

    // Paint most right and most left elements at the following rows.
    for (int i = 2; i <= tipSize; ++i) {
      ans.add(new int[] {i, 1});
      ans.add(new int[] {i, 2 * i - 1});
    }

    // Paint 4-row chunks.
    for (int i = tipSize + 1; i < n; i += 4) {
      // Fill the 1st row of the chunk.
      ans.add(new int[] {i, 1});
      // Fill the 2nd row.
      for (int j = 1; j <= i; ++j)
        ans.add(new int[] {i + 1, 2 * j + 1});
      // Fill the 3rd row.
      ans.add(new int[] {i + 2, 2});
      // Fill the 4th row.
      for (int j = 0; j <= i + 2; ++j)
        ans.add(new int[] {i + 3, 2 * j + 1});
    }

    return ans.stream().toArray(int[][] ::new);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
  def colorRed(self, n: int) -> List[List[int]]:
    ans = []
    tipSize = n % 4

    # Tip of the triangle is always painted red.
    if tipSize >= 1:
      ans.append([1, 1])

    # Pamost right and most left elements at the following rows.
    for i in range(2, tipSize + 1):
      ans.append([i, 1])
      ans.append([i, 2 * i - 1])

    # Pa4-row chunks.
    for i in range(tipSize + 1, n, 4):
      # Fill the 1st row of the chunk.
      ans.append([i, 1])
      # Fill the 2nd row.
      for j in range(1, i + 1):
        ans.append([i + 1, 2 * j + 1])
      # Fill the 3rd row.
      ans.append([i + 2, 2])
      # Fill the 4th row.
      for j in range(i + 2 + 1):
        ans.append([i + 3, 2 * j + 1])

    return ans