Changing a Matrix in Place
Editorial
Rotating by writing over it
Rotate Image turns an n × n matrix a quarter turn clockwise, and asks for it in place: no second matrix. A quarter turn sends the value at (r, c) to (c, n − 1 − r), so the first idea is one pass that writes every value straight to its new place. Here it is on 1 to 9, then the same move into a new matrix, in every language the judge runs:
def show(m):
return " | ".join(" ".join(map(str, row)) for row in m)
m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
n = len(m)
for r in range(n): # each value written straight to its new place, over what's there
for c in range(n):
m[c][n - 1 - r] = m[r][c]
print("one pass in place:", show(m))
src = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotated = [[0] * n for _ in range(n)]
for r in range(n): # into a new matrix: right, with n * n more cells
for c in range(n):
rotated[c][n - 1 - r] = src[r][c]
print("into a new matrix:", show(rotated))
# one pass in place: 7 4 1 | 2 5 2 | 1 2 1
# into a new matrix: 7 4 1 | 8 5 2 | 9 6 3public class Main {
static String show(int[][] m) {
StringBuilder sb = new StringBuilder();
for (int[] row : m) {
if (sb.length() > 0) sb.append(" | ");
for (int c = 0; c < row.length; c++) sb.append(c == 0 ? "" : " ").append(row[c]);
}
return sb.toString();
}
public static void main(String[] args) {
int[][] m = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int n = m.length;
for (int r = 0; r < n; r++) // each value written straight to its new place, over what's there
for (int c = 0; c < n; c++)
m[c][n - 1 - r] = m[r][c];
System.out.println("one pass in place: " + show(m));
int[][] src = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int[][] rotated = new int[n][n];
for (int r = 0; r < n; r++) // into a new matrix: right, with n * n more cells
for (int c = 0; c < n; c++)
rotated[c][n - 1 - r] = src[r][c];
System.out.println("into a new matrix: " + show(rotated));
}
}
// one pass in place: 7 4 1 | 2 5 2 | 1 2 1
// into a new matrix: 7 4 1 | 8 5 2 | 9 6 3#include <bits/stdc++.h>
using namespace std;
string show(const vector<vector<int>>& m) {
string s;
for (auto& row : m) {
if (!s.empty()) s += " | ";
for (size_t c = 0; c < row.size(); c++) s += (c ? " " : "") + to_string(row[c]);
}
return s;
}
int main() {
vector<vector<int>> m = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int n = m.size();
for (int r = 0; r < n; r++) // each value written straight to its new place, over what's there
for (int c = 0; c < n; c++)
m[c][n - 1 - r] = m[r][c];
cout << "one pass in place: " << show(m) << "\n";
vector<vector<int>> src = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
vector<vector<int>> rotated(n, vector<int>(n));
for (int r = 0; r < n; r++) // into a new matrix: right, with n * n more cells
for (int c = 0; c < n; c++)
rotated[c][n - 1 - r] = src[r][c];
cout << "into a new matrix: " << show(rotated) << "\n";
}
// one pass in place: 7 4 1 | 2 5 2 | 1 2 1
// into a new matrix: 7 4 1 | 8 5 2 | 9 6 3const show = m => m.map(row => row.join(" ")).join(" | ");
const m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
const n = m.length;
for (let r = 0; r < n; r++) // each value written straight to its new place, over what's there
for (let c = 0; c < n; c++)
m[c][n - 1 - r] = m[r][c];
console.log("one pass in place:", show(m));
const src = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
const rotated = Array.from({ length: n }, () => Array(n).fill(0));
for (let r = 0; r < n; r++) // into a new matrix: right, with n * n more cells
for (let c = 0; c < n; c++)
rotated[c][n - 1 - r] = src[r][c];
console.log("into a new matrix:", show(rotated));
// one pass in place: 7 4 1 | 2 5 2 | 1 2 1
// into a new matrix: 7 4 1 | 8 5 2 | 9 6 3const show = (m: number[][]): string => m.map(row => row.join(" ")).join(" | ");
const m: number[][] = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
const n: number = m.length;
for (let r = 0; r < n; r++) // each value written straight to its new place, over what's there
for (let c = 0; c < n; c++)
m[c][n - 1 - r] = m[r][c];
console.log("one pass in place:", show(m));
const src: number[][] = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
const rotated: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
for (let r = 0; r < n; r++) // into a new matrix: right, with n * n more cells
for (let c = 0; c < n; c++)
rotated[c][n - 1 - r] = src[r][c];
console.log("into a new matrix:", show(rotated));
// one pass in place: 7 4 1 | 2 5 2 | 1 2 1
// into a new matrix: 7 4 1 | 8 5 2 | 9 6 3using System;
using System.Linq;
class Program {
static string Show(int[][] m) => string.Join(" | ", m.Select(row => string.Join(" ", row)));
static void Main() {
int[][] m = { new[] {1, 2, 3}, new[] {4, 5, 6}, new[] {7, 8, 9} };
int n = m.Length;
for (int r = 0; r < n; r++) // each value written straight to its new place, over what's there
for (int c = 0; c < n; c++)
m[c][n - 1 - r] = m[r][c];
Console.WriteLine("one pass in place: " + Show(m));
int[][] src = { new[] {1, 2, 3}, new[] {4, 5, 6}, new[] {7, 8, 9} };
int[][] rotated = Enumerable.Range(0, n).Select(_ => new int[n]).ToArray();
for (int r = 0; r < n; r++) // into a new matrix: right, with n * n more cells
for (int c = 0; c < n; c++)
rotated[c][n - 1 - r] = src[r][c];
Console.WriteLine("into a new matrix: " + Show(rotated));
}
}
// one pass in place: 7 4 1 | 2 5 2 | 1 2 1
// into a new matrix: 7 4 1 | 8 5 2 | 9 6 3package main
import (
"fmt"
"strings"
)
func show(m [][]int) string {
rows := make([]string, len(m))
for i, row := range m {
rows[i] = strings.Trim(fmt.Sprint(row), "[]")
}
return strings.Join(rows, " | ")
}
func main() {
m := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
n := len(m)
for r := 0; r < n; r++ { // each value written straight to its new place, over what's there
for c := 0; c < n; c++ {
m[c][n-1-r] = m[r][c]
}
}
fmt.Println("one pass in place:", show(m))
src := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
rotated := make([][]int, n)
for i := range rotated {
rotated[i] = make([]int, n)
}
for r := 0; r < n; r++ { // into a new matrix: right, with n * n more cells
for c := 0; c < n; c++ {
rotated[c][n-1-r] = src[r][c]
}
}
fmt.Println("into a new matrix:", show(rotated))
}
// one pass in place: 7 4 1 | 2 5 2 | 1 2 1
// into a new matrix: 7 4 1 | 8 5 2 | 9 6 3Into a new matrix it's right, 7 4 1 | 8 5 2 | 9 6 3, at the price of n² more cells. In place, all seven printed 7 4 1 | 2 5 2 | 1 2 1: the first row is right, and the rest is wrong. Writing 1 into (0, 2) wiped out the 3 before it was read, and every write after that does the same to a value still waiting its turn. To change a matrix in place, every value has to be read before anything overwrites it. This lesson is three ways to arrange that: move values in pairs that swap, in cycles of four with one saved, or keep the new value beside the old one in the same cell.
A turn is two flips
Two in-place moves you already know make a quarter turn. The transpose sends (r, c) to (c, r), each pair swapped across the diagonal (Introduction to Matrices). Reversing each row then sends (c, r) to (c, n − 1 − r), which is exactly where a clockwise quarter turn puts the value from (r, c). Both moves swap pairs, and a swap reads both values before it writes either, so nothing is lost:
def show(m):
return " | ".join(" ".join(map(str, row)) for row in m)
def transpose(m): # each pair above the diagonal swapped once
n = len(m)
for r in range(n):
for c in range(r + 1, n):
m[r][c], m[c][r] = m[c][r], m[r][c]
m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
transpose(m)
print("transposed:", show(m))
for row in m:
row.reverse() # then each row reversed: a quarter turn clockwise
print("clockwise:", show(m))
m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
transpose(m)
m.reverse() # the order of the rows reversed instead: a quarter turn the other way
print("counter-clockwise:", show(m))
# transposed: 1 4 7 | 2 5 8 | 3 6 9
# clockwise: 7 4 1 | 8 5 2 | 9 6 3
# counter-clockwise: 3 6 9 | 2 5 8 | 1 4 7public class Main {
static String show(int[][] m) {
StringBuilder sb = new StringBuilder();
for (int[] row : m) {
if (sb.length() > 0) sb.append(" | ");
for (int c = 0; c < row.length; c++) sb.append(c == 0 ? "" : " ").append(row[c]);
}
return sb.toString();
}
static void transpose(int[][] m) { // each pair above the diagonal swapped once
int n = m.length;
for (int r = 0; r < n; r++)
for (int c = r + 1; c < n; c++) {
int keep = m[r][c];
m[r][c] = m[c][r];
m[c][r] = keep;
}
}
static void reverse(int[] a) {
for (int i = 0, j = a.length - 1; i < j; i++, j--) {
int keep = a[i];
a[i] = a[j];
a[j] = keep;
}
}
public static void main(String[] args) {
int[][] m = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
transpose(m);
System.out.println("transposed: " + show(m));
for (int[] row : m) reverse(row); // then each row reversed: a quarter turn clockwise
System.out.println("clockwise: " + show(m));
m = new int[][] {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
transpose(m);
for (int i = 0, j = m.length - 1; i < j; i++, j--) { // the rows' order reversed instead: the other way
int[] keep = m[i];
m[i] = m[j];
m[j] = keep;
}
System.out.println("counter-clockwise: " + show(m));
}
}
// transposed: 1 4 7 | 2 5 8 | 3 6 9
// clockwise: 7 4 1 | 8 5 2 | 9 6 3
// counter-clockwise: 3 6 9 | 2 5 8 | 1 4 7#include <bits/stdc++.h>
using namespace std;
string show(const vector<vector<int>>& m) {
string s;
for (auto& row : m) {
if (!s.empty()) s += " | ";
for (size_t c = 0; c < row.size(); c++) s += (c ? " " : "") + to_string(row[c]);
}
return s;
}
void transpose(vector<vector<int>>& m) { // each pair above the diagonal swapped once
int n = m.size();
for (int r = 0; r < n; r++)
for (int c = r + 1; c < n; c++) swap(m[r][c], m[c][r]);
}
int main() {
vector<vector<int>> m = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
transpose(m);
cout << "transposed: " << show(m) << "\n";
for (auto& row : m) reverse(row.begin(), row.end()); // then each row reversed: a quarter turn clockwise
cout << "clockwise: " << show(m) << "\n";
m = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
transpose(m);
reverse(m.begin(), m.end()); // the order of the rows reversed instead: a quarter turn the other way
cout << "counter-clockwise: " << show(m) << "\n";
}
// transposed: 1 4 7 | 2 5 8 | 3 6 9
// clockwise: 7 4 1 | 8 5 2 | 9 6 3
// counter-clockwise: 3 6 9 | 2 5 8 | 1 4 7const show = m => m.map(row => row.join(" ")).join(" | ");
function transpose(m) { // each pair above the diagonal swapped once
const n = m.length;
for (let r = 0; r < n; r++)
for (let c = r + 1; c < n; c++) [m[r][c], m[c][r]] = [m[c][r], m[r][c]];
}
let m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
transpose(m);
console.log("transposed:", show(m));
for (const row of m) row.reverse(); // then each row reversed: a quarter turn clockwise
console.log("clockwise:", show(m));
m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
transpose(m);
m.reverse(); // the order of the rows reversed instead: a quarter turn the other way
console.log("counter-clockwise:", show(m));
// transposed: 1 4 7 | 2 5 8 | 3 6 9
// clockwise: 7 4 1 | 8 5 2 | 9 6 3
// counter-clockwise: 3 6 9 | 2 5 8 | 1 4 7const show = (m: number[][]): string => m.map(row => row.join(" ")).join(" | ");
function transpose(m: number[][]): void { // each pair above the diagonal swapped once
const n = m.length;
for (let r = 0; r < n; r++)
for (let c = r + 1; c < n; c++) [m[r][c], m[c][r]] = [m[c][r], m[r][c]];
}
let m: number[][] = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
transpose(m);
console.log("transposed:", show(m));
for (const row of m) row.reverse(); // then each row reversed: a quarter turn clockwise
console.log("clockwise:", show(m));
m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
transpose(m);
m.reverse(); // the order of the rows reversed instead: a quarter turn the other way
console.log("counter-clockwise:", show(m));
// transposed: 1 4 7 | 2 5 8 | 3 6 9
// clockwise: 7 4 1 | 8 5 2 | 9 6 3
// counter-clockwise: 3 6 9 | 2 5 8 | 1 4 7using System;
using System.Linq;
class Program {
static string Show(int[][] m) => string.Join(" | ", m.Select(row => string.Join(" ", row)));
static void Transpose(int[][] m) { // each pair above the diagonal swapped once
int n = m.Length;
for (int r = 0; r < n; r++)
for (int c = r + 1; c < n; c++) (m[r][c], m[c][r]) = (m[c][r], m[r][c]);
}
static void Main() {
int[][] m = { new[] {1, 2, 3}, new[] {4, 5, 6}, new[] {7, 8, 9} };
Transpose(m);
Console.WriteLine("transposed: " + Show(m));
foreach (int[] row in m) Array.Reverse(row); // then each row reversed: a quarter turn clockwise
Console.WriteLine("clockwise: " + Show(m));
m = new[] { new[] {1, 2, 3}, new[] {4, 5, 6}, new[] {7, 8, 9} };
Transpose(m);
Array.Reverse(m); // the order of the rows reversed instead: a quarter turn the other way
Console.WriteLine("counter-clockwise: " + Show(m));
}
}
// transposed: 1 4 7 | 2 5 8 | 3 6 9
// clockwise: 7 4 1 | 8 5 2 | 9 6 3
// counter-clockwise: 3 6 9 | 2 5 8 | 1 4 7package main
import (
"fmt"
"slices"
"strings"
)
func show(m [][]int) string {
rows := make([]string, len(m))
for i, row := range m {
rows[i] = strings.Trim(fmt.Sprint(row), "[]")
}
return strings.Join(rows, " | ")
}
func transpose(m [][]int) { // each pair above the diagonal swapped once
n := len(m)
for r := 0; r < n; r++ {
for c := r + 1; c < n; c++ {
m[r][c], m[c][r] = m[c][r], m[r][c]
}
}
}
func main() {
m := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
transpose(m)
fmt.Println("transposed:", show(m))
for _, row := range m {
slices.Reverse(row) // then each row reversed: a quarter turn clockwise
}
fmt.Println("clockwise:", show(m))
m = [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
transpose(m)
slices.Reverse(m) // the order of the rows reversed instead: a quarter turn the other way
fmt.Println("counter-clockwise:", show(m))
}
// transposed: 1 4 7 | 2 5 8 | 3 6 9
// clockwise: 7 4 1 | 8 5 2 | 9 6 3
// counter-clockwise: 3 6 9 | 2 5 8 | 1 4 7Transposed, 1 to 9 became 1 4 7 | 2 5 8 | 3 6 9; with each row reversed, 7 4 1 | 8 5 2 | 9 6 3, the copy's answer. Reversing the order of the rows instead of each row turns it the other way: 3 6 9 | 2 5 8 | 1 4 7. Each cell is touched a fixed number of times, so it's O(n²) time and O(1) extra space. Reversing in place is the two-pointer swap from Rearranging Arrays in Place.
Four cells at a time
The quarter turn can also be done in one pass. A square matrix is a set of layers, rings from the outside in, and a quarter turn keeps each value in its layer. In a layer, the values move in cycles of four: top to right, right to bottom, bottom to left, left to top. Save the top value, move the other three round, and put the saved one in the last place. A 4 × 4 matrix has two layers:
def show(m):
return " | ".join(" ".join(map(str, row)) for row in m)
def rotate(m): # a quarter turn clockwise, layer by layer from the outside
n = len(m)
for layer in range(n // 2):
first, last = layer, n - 1 - layer
for i in range(first, last): # one cycle of four cells for each place along the layer
offset = i - first
keep = m[first][i] # the top cell, saved
m[first][i] = m[last - offset][first] # left to top
m[last - offset][first] = m[last][last - offset] # bottom to left
m[last][last - offset] = m[i][last] # right to bottom
m[i][last] = keep # top to right
print(f"after layer {layer}:", show(m))
rotate([[r * 4 + c + 1 for c in range(4)] for r in range(4)])
# after layer 0: 13 9 5 1 | 14 6 7 2 | 15 10 11 3 | 16 12 8 4
# after layer 1: 13 9 5 1 | 14 10 6 2 | 15 11 7 3 | 16 12 8 4public class Main {
static String show(int[][] m) {
StringBuilder sb = new StringBuilder();
for (int[] row : m) {
if (sb.length() > 0) sb.append(" | ");
for (int c = 0; c < row.length; c++) sb.append(c == 0 ? "" : " ").append(row[c]);
}
return sb.toString();
}
static void rotate(int[][] m) { // a quarter turn clockwise, layer by layer from the outside
int n = m.length;
for (int layer = 0; layer < n / 2; layer++) {
int first = layer, last = n - 1 - layer;
for (int i = first; i < last; i++) { // one cycle of four cells for each place along the layer
int offset = i - first;
int keep = m[first][i]; // the top cell, saved
m[first][i] = m[last - offset][first]; // left to top
m[last - offset][first] = m[last][last - offset]; // bottom to left
m[last][last - offset] = m[i][last]; // right to bottom
m[i][last] = keep; // top to right
}
System.out.println("after layer " + layer + ": " + show(m));
}
}
public static void main(String[] args) {
int[][] m = new int[4][4];
for (int r = 0; r < 4; r++)
for (int c = 0; c < 4; c++) m[r][c] = r * 4 + c + 1;
rotate(m);
}
}
// after layer 0: 13 9 5 1 | 14 6 7 2 | 15 10 11 3 | 16 12 8 4
// after layer 1: 13 9 5 1 | 14 10 6 2 | 15 11 7 3 | 16 12 8 4#include <bits/stdc++.h>
using namespace std;
string show(const vector<vector<int>>& m) {
string s;
for (auto& row : m) {
if (!s.empty()) s += " | ";
for (size_t c = 0; c < row.size(); c++) s += (c ? " " : "") + to_string(row[c]);
}
return s;
}
void rotate(vector<vector<int>>& m) { // a quarter turn clockwise, layer by layer from the outside
int n = m.size();
for (int layer = 0; layer < n / 2; layer++) {
int first = layer, last = n - 1 - layer;
for (int i = first; i < last; i++) { // one cycle of four cells for each place along the layer
int offset = i - first;
int keep = m[first][i]; // the top cell, saved
m[first][i] = m[last - offset][first]; // left to top
m[last - offset][first] = m[last][last - offset]; // bottom to left
m[last][last - offset] = m[i][last]; // right to bottom
m[i][last] = keep; // top to right
}
cout << "after layer " << layer << ": " << show(m) << "\n";
}
}
int main() {
vector<vector<int>> m(4, vector<int>(4));
for (int r = 0; r < 4; r++)
for (int c = 0; c < 4; c++) m[r][c] = r * 4 + c + 1;
rotate(m);
}
// after layer 0: 13 9 5 1 | 14 6 7 2 | 15 10 11 3 | 16 12 8 4
// after layer 1: 13 9 5 1 | 14 10 6 2 | 15 11 7 3 | 16 12 8 4const show = m => m.map(row => row.join(" ")).join(" | ");
function rotate(m) { // a quarter turn clockwise, layer by layer from the outside
const n = m.length;
for (let layer = 0; layer < Math.floor(n / 2); layer++) {
const first = layer, last = n - 1 - layer;
for (let i = first; i < last; i++) { // one cycle of four cells for each place along the layer
const offset = i - first;
const keep = m[first][i]; // the top cell, saved
m[first][i] = m[last - offset][first]; // left to top
m[last - offset][first] = m[last][last - offset]; // bottom to left
m[last][last - offset] = m[i][last]; // right to bottom
m[i][last] = keep; // top to right
}
console.log(`after layer ${layer}:`, show(m));
}
}
rotate(Array.from({ length: 4 }, (_, r) => Array.from({ length: 4 }, (_, c) => r * 4 + c + 1)));
// after layer 0: 13 9 5 1 | 14 6 7 2 | 15 10 11 3 | 16 12 8 4
// after layer 1: 13 9 5 1 | 14 10 6 2 | 15 11 7 3 | 16 12 8 4const show = (m: number[][]): string => m.map(row => row.join(" ")).join(" | ");
function rotate(m: number[][]): void { // a quarter turn clockwise, layer by layer from the outside
const n = m.length;
for (let layer = 0; layer < Math.floor(n / 2); layer++) {
const first = layer, last = n - 1 - layer;
for (let i = first; i < last; i++) { // one cycle of four cells for each place along the layer
const offset = i - first;
const keep = m[first][i]; // the top cell, saved
m[first][i] = m[last - offset][first]; // left to top
m[last - offset][first] = m[last][last - offset]; // bottom to left
m[last][last - offset] = m[i][last]; // right to bottom
m[i][last] = keep; // top to right
}
console.log(`after layer ${layer}:`, show(m));
}
}
rotate(Array.from({ length: 4 }, (_, r) => Array.from({ length: 4 }, (_, c) => r * 4 + c + 1)));
// after layer 0: 13 9 5 1 | 14 6 7 2 | 15 10 11 3 | 16 12 8 4
// after layer 1: 13 9 5 1 | 14 10 6 2 | 15 11 7 3 | 16 12 8 4using System;
using System.Linq;
class Program {
static string Show(int[][] m) => string.Join(" | ", m.Select(row => string.Join(" ", row)));
static void Rotate(int[][] m) { // a quarter turn clockwise, layer by layer from the outside
int n = m.Length;
for (int layer = 0; layer < n / 2; layer++) {
int first = layer, last = n - 1 - layer;
for (int i = first; i < last; i++) { // one cycle of four cells for each place along the layer
int offset = i - first;
int keep = m[first][i]; // the top cell, saved
m[first][i] = m[last - offset][first]; // left to top
m[last - offset][first] = m[last][last - offset]; // bottom to left
m[last][last - offset] = m[i][last]; // right to bottom
m[i][last] = keep; // top to right
}
Console.WriteLine($"after layer {layer}: " + Show(m));
}
}
static void Main() {
int[][] m = Enumerable.Range(0, 4).Select(r => Enumerable.Range(0, 4).Select(c => r * 4 + c + 1).ToArray()).ToArray();
Rotate(m);
}
}
// after layer 0: 13 9 5 1 | 14 6 7 2 | 15 10 11 3 | 16 12 8 4
// after layer 1: 13 9 5 1 | 14 10 6 2 | 15 11 7 3 | 16 12 8 4package main
import (
"fmt"
"strings"
)
func show(m [][]int) string {
rows := make([]string, len(m))
for i, row := range m {
rows[i] = strings.Trim(fmt.Sprint(row), "[]")
}
return strings.Join(rows, " | ")
}
func rotate(m [][]int) { // a quarter turn clockwise, layer by layer from the outside
n := len(m)
for layer := 0; layer < n/2; layer++ {
first, last := layer, n-1-layer
for i := first; i < last; i++ { // one cycle of four cells for each place along the layer
offset := i - first
keep := m[first][i] // the top cell, saved
m[first][i] = m[last-offset][first] // left to top
m[last-offset][first] = m[last][last-offset] // bottom to left
m[last][last-offset] = m[i][last] // right to bottom
m[i][last] = keep // top to right
}
fmt.Printf("after layer %d: %s\n", layer, show(m))
}
}
func main() {
m := make([][]int, 4)
for r := range m {
m[r] = make([]int, 4)
for c := range m[r] {
m[r][c] = r*4 + c + 1
}
}
rotate(m)
}
// after layer 0: 13 9 5 1 | 14 6 7 2 | 15 10 11 3 | 16 12 8 4
// after layer 1: 13 9 5 1 | 14 10 6 2 | 15 11 7 3 | 16 12 8 4
After the outer layer, 13 9 5 1 | 14 6 7 2 | 15 10 11 3 | 16 12 8 4: the outside has turned and the middle 6, 7, 10, 11 hasn't moved. After the inner layer, 13 9 5 1 | 14 10 6 2 | 15 11 7 3 | 16 12 8 4, the same as the two flips give. Each value is moved once, n² moves in all, against two moves for most cells with the flips. An n × n matrix has n / 2 layers, rounded down; an odd n leaves the centre cell where it is.
Rotate by Layers. Turn a matrix yourself, one cycle of four at a time: pick a cell, then tap where its value goes.
Set Matrix Zeroes
Set Matrix Zeroes clears the whole row and column of every 0, in place. Two lists of flags, one per row and one per column, are a first pass to note where the 0s are and a second to clear, in O(m + n) extra space. The follow-up asks for O(1), and the flags fit in the matrix itself: row 0 holds the column marks and column 0 the row marks. One cell is in both, (0, 0), so it marks row 0, and column 0 gets a flag of its own. Clear the inner cells from the marks first, row 0 and column 0 last, so no mark is wiped before it's used:
def show(m):
return " | ".join(" ".join(map(str, row)) for row in m)
def set_zeroes(m): # O(1) extra: row 0 and column 0 hold the marks
rows, cols = len(m), len(m[0])
first_col = any(m[r][0] == 0 for r in range(rows)) # column 0's own flag: m[0][0] marks row 0
for r in range(rows):
for c in range(1, cols):
if m[r][c] == 0:
m[r][0] = 0 # mark row r
m[0][c] = 0 # mark column c
for r in range(1, rows): # clear from the marks, row 0 and column 0 last
for c in range(1, cols):
if m[r][0] == 0 or m[0][c] == 0:
m[r][c] = 0
if m[0][0] == 0: # row 0 had a 0
for c in range(cols):
m[0][c] = 0
if first_col: # column 0 had a 0
for r in range(rows):
m[r][0] = 0
for grid in ([[1, 1, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1]], [[1, 1, 1], [0, 1, 1], [1, 1, 1]]):
set_zeroes(grid)
print(show(grid))
# 1 1 0 1 | 0 0 0 0 | 1 1 0 1
# 0 1 1 | 0 0 0 | 0 1 1public class Main {
static String show(int[][] m) {
StringBuilder sb = new StringBuilder();
for (int[] row : m) {
if (sb.length() > 0) sb.append(" | ");
for (int c = 0; c < row.length; c++) sb.append(c == 0 ? "" : " ").append(row[c]);
}
return sb.toString();
}
static void setZeroes(int[][] m) { // O(1) extra: row 0 and column 0 hold the marks
int rows = m.length, cols = m[0].length;
boolean firstCol = false; // column 0's own flag: m[0][0] marks row 0
for (int r = 0; r < rows; r++) if (m[r][0] == 0) firstCol = true;
for (int r = 0; r < rows; r++)
for (int c = 1; c < cols; c++)
if (m[r][c] == 0) {
m[r][0] = 0; // mark row r
m[0][c] = 0; // mark column c
}
for (int r = 1; r < rows; r++) // clear from the marks, row 0 and column 0 last
for (int c = 1; c < cols; c++)
if (m[r][0] == 0 || m[0][c] == 0) m[r][c] = 0;
if (m[0][0] == 0) // row 0 had a 0
for (int c = 0; c < cols; c++) m[0][c] = 0;
if (firstCol) // column 0 had a 0
for (int r = 0; r < rows; r++) m[r][0] = 0;
}
public static void main(String[] args) {
int[][][] grids = {{{1, 1, 1, 1}, {1, 1, 0, 1}, {1, 1, 1, 1}}, {{1, 1, 1}, {0, 1, 1}, {1, 1, 1}}};
for (int[][] grid : grids) {
setZeroes(grid);
System.out.println(show(grid));
}
}
}
// 1 1 0 1 | 0 0 0 0 | 1 1 0 1
// 0 1 1 | 0 0 0 | 0 1 1#include <bits/stdc++.h>
using namespace std;
string show(const vector<vector<int>>& m) {
string s;
for (auto& row : m) {
if (!s.empty()) s += " | ";
for (size_t c = 0; c < row.size(); c++) s += (c ? " " : "") + to_string(row[c]);
}
return s;
}
void setZeroes(vector<vector<int>>& m) { // O(1) extra: row 0 and column 0 hold the marks
int rows = m.size(), cols = m[0].size();
bool firstCol = false; // column 0's own flag: m[0][0] marks row 0
for (int r = 0; r < rows; r++) if (m[r][0] == 0) firstCol = true;
for (int r = 0; r < rows; r++)
for (int c = 1; c < cols; c++)
if (m[r][c] == 0) {
m[r][0] = 0; // mark row r
m[0][c] = 0; // mark column c
}
for (int r = 1; r < rows; r++) // clear from the marks, row 0 and column 0 last
for (int c = 1; c < cols; c++)
if (m[r][0] == 0 || m[0][c] == 0) m[r][c] = 0;
if (m[0][0] == 0) // row 0 had a 0
for (int c = 0; c < cols; c++) m[0][c] = 0;
if (firstCol) // column 0 had a 0
for (int r = 0; r < rows; r++) m[r][0] = 0;
}
int main() {
vector<vector<vector<int>>> grids = {{{1, 1, 1, 1}, {1, 1, 0, 1}, {1, 1, 1, 1}}, {{1, 1, 1}, {0, 1, 1}, {1, 1, 1}}};
for (auto& grid : grids) {
setZeroes(grid);
cout << show(grid) << "\n";
}
}
// 1 1 0 1 | 0 0 0 0 | 1 1 0 1
// 0 1 1 | 0 0 0 | 0 1 1const show = m => m.map(row => row.join(" ")).join(" | ");
function setZeroes(m) { // O(1) extra: row 0 and column 0 hold the marks
const rows = m.length, cols = m[0].length;
const firstCol = m.some(row => row[0] === 0); // column 0's own flag: m[0][0] marks row 0
for (let r = 0; r < rows; r++)
for (let c = 1; c < cols; c++)
if (m[r][c] === 0) {
m[r][0] = 0; // mark row r
m[0][c] = 0; // mark column c
}
for (let r = 1; r < rows; r++) // clear from the marks, row 0 and column 0 last
for (let c = 1; c < cols; c++)
if (m[r][0] === 0 || m[0][c] === 0) m[r][c] = 0;
if (m[0][0] === 0) // row 0 had a 0
for (let c = 0; c < cols; c++) m[0][c] = 0;
if (firstCol) // column 0 had a 0
for (let r = 0; r < rows; r++) m[r][0] = 0;
}
for (const grid of [[[1, 1, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1]], [[1, 1, 1], [0, 1, 1], [1, 1, 1]]]) {
setZeroes(grid);
console.log(show(grid));
}
// 1 1 0 1 | 0 0 0 0 | 1 1 0 1
// 0 1 1 | 0 0 0 | 0 1 1const show = (m: number[][]): string => m.map(row => row.join(" ")).join(" | ");
function setZeroes(m: number[][]): void { // O(1) extra: row 0 and column 0 hold the marks
const rows = m.length, cols = m[0].length;
const firstCol = m.some(row => row[0] === 0); // column 0's own flag: m[0][0] marks row 0
for (let r = 0; r < rows; r++)
for (let c = 1; c < cols; c++)
if (m[r][c] === 0) {
m[r][0] = 0; // mark row r
m[0][c] = 0; // mark column c
}
for (let r = 1; r < rows; r++) // clear from the marks, row 0 and column 0 last
for (let c = 1; c < cols; c++)
if (m[r][0] === 0 || m[0][c] === 0) m[r][c] = 0;
if (m[0][0] === 0) // row 0 had a 0
for (let c = 0; c < cols; c++) m[0][c] = 0;
if (firstCol) // column 0 had a 0
for (let r = 0; r < rows; r++) m[r][0] = 0;
}
const grids: number[][][] = [[[1, 1, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1]], [[1, 1, 1], [0, 1, 1], [1, 1, 1]]];
for (const grid of grids) {
setZeroes(grid);
console.log(show(grid));
}
// 1 1 0 1 | 0 0 0 0 | 1 1 0 1
// 0 1 1 | 0 0 0 | 0 1 1using System;
using System.Linq;
class Program {
static string Show(int[][] m) => string.Join(" | ", m.Select(row => string.Join(" ", row)));
static void SetZeroes(int[][] m) { // O(1) extra: row 0 and column 0 hold the marks
int rows = m.Length, cols = m[0].Length;
bool firstCol = m.Any(row => row[0] == 0); // column 0's own flag: m[0][0] marks row 0
for (int r = 0; r < rows; r++)
for (int c = 1; c < cols; c++)
if (m[r][c] == 0) {
m[r][0] = 0; // mark row r
m[0][c] = 0; // mark column c
}
for (int r = 1; r < rows; r++) // clear from the marks, row 0 and column 0 last
for (int c = 1; c < cols; c++)
if (m[r][0] == 0 || m[0][c] == 0) m[r][c] = 0;
if (m[0][0] == 0) // row 0 had a 0
for (int c = 0; c < cols; c++) m[0][c] = 0;
if (firstCol) // column 0 had a 0
for (int r = 0; r < rows; r++) m[r][0] = 0;
}
static void Main() {
int[][][] grids = {
new[] { new[] {1, 1, 1, 1}, new[] {1, 1, 0, 1}, new[] {1, 1, 1, 1} },
new[] { new[] {1, 1, 1}, new[] {0, 1, 1}, new[] {1, 1, 1} },
};
foreach (var grid in grids) {
SetZeroes(grid);
Console.WriteLine(Show(grid));
}
}
}
// 1 1 0 1 | 0 0 0 0 | 1 1 0 1
// 0 1 1 | 0 0 0 | 0 1 1package main
import (
"fmt"
"strings"
)
func show(m [][]int) string {
rows := make([]string, len(m))
for i, row := range m {
rows[i] = strings.Trim(fmt.Sprint(row), "[]")
}
return strings.Join(rows, " | ")
}
func setZeroes(m [][]int) { // O(1) extra: row 0 and column 0 hold the marks
rows, cols := len(m), len(m[0])
firstCol := false // column 0's own flag: m[0][0] marks row 0
for r := 0; r < rows; r++ {
if m[r][0] == 0 {
firstCol = true
}
}
for r := 0; r < rows; r++ {
for c := 1; c < cols; c++ {
if m[r][c] == 0 {
m[r][0] = 0 // mark row r
m[0][c] = 0 // mark column c
}
}
}
for r := 1; r < rows; r++ { // clear from the marks, row 0 and column 0 last
for c := 1; c < cols; c++ {
if m[r][0] == 0 || m[0][c] == 0 {
m[r][c] = 0
}
}
}
if m[0][0] == 0 { // row 0 had a 0
for c := 0; c < cols; c++ {
m[0][c] = 0
}
}
if firstCol { // column 0 had a 0
for r := 0; r < rows; r++ {
m[r][0] = 0
}
}
}
func main() {
grids := [][][]int{{{1, 1, 1, 1}, {1, 1, 0, 1}, {1, 1, 1, 1}}, {{1, 1, 1}, {0, 1, 1}, {1, 1, 1}}}
for _, grid := range grids {
setZeroes(grid)
fmt.Println(show(grid))
}
}
// 1 1 0 1 | 0 0 0 0 | 1 1 0 1
// 0 1 1 | 0 0 0 | 0 1 1
The 0 at (1, 2) cleared its row and column: 1 1 0 1 | 0 0 0 0 | 1 1 0 1. In the second grid the only 0 is in column 0, at (1, 0): 0 1 1 | 0 0 0 | 0 1 1. Column 0's flag cleared column 0, and row 0 kept its 1s, because its mark at (0, 0) was never set. Two passes over m × n cells, O(m · n) time, and one flag besides the matrix: O(1) extra space.
Game of Life
Game of Life moves a board of live (1) and dead (0) cells one generation on, all at once: a live cell with two or three live neighbours lives, a dead one with exactly three comes alive, and every other cell is dead next. Each cell's fate depends on its neighbours as they are now, so writing a new value over an old one corrupts the counts of the cells after it. In place, give each cell two bits: bit 0 is now and bit 1 is next. Count with & 1, set bit 1 for the cells alive next, then shift every cell right once (Introduction to Bit Manipulation). The neighbour loop is the one from Introduction to Matrices:
def show(m):
return " | ".join(" ".join(map(str, row)) for row in m)
def game_of_life(board): # bit 0: alive now; bit 1: alive next
rows, cols = len(board), len(board[0])
for r in range(rows):
for c in range(cols):
live = 0
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
nr, nc = r + dr, c + dc
if (dr or dc) and 0 <= nr < rows and 0 <= nc < cols:
live += board[nr][nc] & 1 # the neighbour as it is now
if live == 3 or (board[r][c] & 1 and live == 2):
board[r][c] |= 2 # alive next
for r in range(rows):
for c in range(cols):
board[r][c] >>= 1 # next becomes now
for board in ([[0, 1, 0], [0, 1, 0], [0, 1, 0]], [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]]):
game_of_life(board)
print(show(board))
# 0 0 0 | 1 1 1 | 0 0 0
# 0 0 0 | 1 0 1 | 0 1 1 | 0 1 0public class Main {
static String show(int[][] m) {
StringBuilder sb = new StringBuilder();
for (int[] row : m) {
if (sb.length() > 0) sb.append(" | ");
for (int c = 0; c < row.length; c++) sb.append(c == 0 ? "" : " ").append(row[c]);
}
return sb.toString();
}
static void gameOfLife(int[][] board) { // bit 0: alive now; bit 1: alive next
int rows = board.length, cols = board[0].length;
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) {
int live = 0;
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if ((dr != 0 || dc != 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += board[nr][nc] & 1; // the neighbour as it is now
}
if (live == 3 || ((board[r][c] & 1) == 1 && live == 2)) board[r][c] |= 2; // alive next
}
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) board[r][c] >>= 1; // next becomes now
}
public static void main(String[] args) {
int[][][] boards = {{{0, 1, 0}, {0, 1, 0}, {0, 1, 0}}, {{0, 1, 0}, {0, 0, 1}, {1, 1, 1}, {0, 0, 0}}};
for (int[][] board : boards) {
gameOfLife(board);
System.out.println(show(board));
}
}
}
// 0 0 0 | 1 1 1 | 0 0 0
// 0 0 0 | 1 0 1 | 0 1 1 | 0 1 0#include <bits/stdc++.h>
using namespace std;
string show(const vector<vector<int>>& m) {
string s;
for (auto& row : m) {
if (!s.empty()) s += " | ";
for (size_t c = 0; c < row.size(); c++) s += (c ? " " : "") + to_string(row[c]);
}
return s;
}
void gameOfLife(vector<vector<int>>& board) { // bit 0: alive now; bit 1: alive next
int rows = board.size(), cols = board[0].size();
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) {
int live = 0;
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if ((dr != 0 || dc != 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += board[nr][nc] & 1; // the neighbour as it is now
}
if (live == 3 || ((board[r][c] & 1) && live == 2)) board[r][c] |= 2; // alive next
}
for (auto& row : board)
for (int& v : row) v >>= 1; // next becomes now
}
int main() {
vector<vector<vector<int>>> boards = {{{0, 1, 0}, {0, 1, 0}, {0, 1, 0}}, {{0, 1, 0}, {0, 0, 1}, {1, 1, 1}, {0, 0, 0}}};
for (auto& board : boards) {
gameOfLife(board);
cout << show(board) << "\n";
}
}
// 0 0 0 | 1 1 1 | 0 0 0
// 0 0 0 | 1 0 1 | 0 1 1 | 0 1 0const show = m => m.map(row => row.join(" ")).join(" | ");
function gameOfLife(board) { // bit 0: alive now; bit 1: alive next
const rows = board.length, cols = board[0].length;
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++) {
let live = 0;
for (let dr = -1; dr <= 1; dr++)
for (let dc = -1; dc <= 1; dc++) {
const nr = r + dr, nc = c + dc;
if ((dr !== 0 || dc !== 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += board[nr][nc] & 1; // the neighbour as it is now
}
if (live === 3 || ((board[r][c] & 1) === 1 && live === 2)) board[r][c] |= 2; // alive next
}
for (const row of board)
for (let c = 0; c < cols; c++) row[c] >>= 1; // next becomes now
}
for (const board of [[[0, 1, 0], [0, 1, 0], [0, 1, 0]], [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]]]) {
gameOfLife(board);
console.log(show(board));
}
// 0 0 0 | 1 1 1 | 0 0 0
// 0 0 0 | 1 0 1 | 0 1 1 | 0 1 0const show = (m: number[][]): string => m.map(row => row.join(" ")).join(" | ");
function gameOfLife(board: number[][]): void { // bit 0: alive now; bit 1: alive next
const rows = board.length, cols = board[0].length;
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++) {
let live = 0;
for (let dr = -1; dr <= 1; dr++)
for (let dc = -1; dc <= 1; dc++) {
const nr = r + dr, nc = c + dc;
if ((dr !== 0 || dc !== 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += board[nr][nc] & 1; // the neighbour as it is now
}
if (live === 3 || ((board[r][c] & 1) === 1 && live === 2)) board[r][c] |= 2; // alive next
}
for (const row of board)
for (let c = 0; c < cols; c++) row[c] >>= 1; // next becomes now
}
const boards: number[][][] = [[[0, 1, 0], [0, 1, 0], [0, 1, 0]], [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]]];
for (const board of boards) {
gameOfLife(board);
console.log(show(board));
}
// 0 0 0 | 1 1 1 | 0 0 0
// 0 0 0 | 1 0 1 | 0 1 1 | 0 1 0using System;
using System.Linq;
class Program {
static string Show(int[][] m) => string.Join(" | ", m.Select(row => string.Join(" ", row)));
static void GameOfLife(int[][] board) { // bit 0: alive now; bit 1: alive next
int rows = board.Length, cols = board[0].Length;
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) {
int live = 0;
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if ((dr != 0 || dc != 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += board[nr][nc] & 1; // the neighbour as it is now
}
if (live == 3 || ((board[r][c] & 1) == 1 && live == 2)) board[r][c] |= 2; // alive next
}
foreach (int[] row in board)
for (int c = 0; c < cols; c++) row[c] >>= 1; // next becomes now
}
static void Main() {
int[][][] boards = {
new[] { new[] {0, 1, 0}, new[] {0, 1, 0}, new[] {0, 1, 0} },
new[] { new[] {0, 1, 0}, new[] {0, 0, 1}, new[] {1, 1, 1}, new[] {0, 0, 0} },
};
foreach (var board in boards) {
GameOfLife(board);
Console.WriteLine(Show(board));
}
}
}
// 0 0 0 | 1 1 1 | 0 0 0
// 0 0 0 | 1 0 1 | 0 1 1 | 0 1 0package main
import (
"fmt"
"strings"
)
func show(m [][]int) string {
rows := make([]string, len(m))
for i, row := range m {
rows[i] = strings.Trim(fmt.Sprint(row), "[]")
}
return strings.Join(rows, " | ")
}
func gameOfLife(board [][]int) { // bit 0: alive now; bit 1: alive next
rows, cols := len(board), len(board[0])
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
live := 0
for dr := -1; dr <= 1; dr++ {
for dc := -1; dc <= 1; dc++ {
nr, nc := r+dr, c+dc
if (dr != 0 || dc != 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols {
live += board[nr][nc] & 1 // the neighbour as it is now
}
}
}
if live == 3 || (board[r][c]&1 == 1 && live == 2) {
board[r][c] |= 2 // alive next
}
}
}
for _, row := range board {
for c := range row {
row[c] >>= 1 // next becomes now
}
}
}
func main() {
boards := [][][]int{{{0, 1, 0}, {0, 1, 0}, {0, 1, 0}}, {{0, 1, 0}, {0, 0, 1}, {1, 1, 1}, {0, 0, 0}}}
for _, board := range boards {
gameOfLife(board)
fmt.Println(show(board))
}
}
// 0 0 0 | 1 1 1 | 0 0 0
// 0 0 0 | 1 0 1 | 0 1 1 | 0 1 0The vertical bar of three, the blinker, turned on its side: 0 0 0 | 1 1 1 | 0 0 0. The second board moved as the problem's first example does: 0 0 0 | 1 0 1 | 0 1 1 | 0 1 0. Each cell counts at most 8 neighbours, then shifts once, so it's O(m · n) time, and the second bit costs no extra space.
Spotting it
The clues: "in place", "O(1) extra space", "modify the matrix", "do not return anything", "rotate the image", or a rule applied to every cell "simultaneously". Then ask what each write destroys, and keep it: in a pair that swaps, in one saved value, or in a spare bit. Near misses:
- Rotating a one-dimensional array by k places: Rearranging Arrays in Place.
- Filling a region or counting islands on a grid: a graph search on the cells (Graphs).
- Updating many sub-rectangles of a grid at once: Difference Arrays and 2D Prefix Sums.
Mistakes that cost an interview
Writing a rotation over itself in one pass. The first program in this lesson: past the first row it printed 2 5 2 | 1 2 1 where 8 5 2 | 9 6 3 belongs. Read every value before anything is written over it.
Clearing while scanning. Set Matrix Zeroes clearing each 0's row and column the moment it finds it:
def show(m):
return " | ".join(" ".join(map(str, row)) for row in m)
m = [[1, 1, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1]]
rows, cols = len(m), len(m[0])
for r in range(rows):
for c in range(cols):
if m[r][c] == 0: # clear its row and column straight away
for k in range(cols):
m[r][k] = 0
for k in range(rows):
m[k][c] = 0
print(show(m))
# 1 1 0 0 | 0 0 0 0 | 0 0 0 0public class Main {
static String show(int[][] m) {
StringBuilder sb = new StringBuilder();
for (int[] row : m) {
if (sb.length() > 0) sb.append(" | ");
for (int c = 0; c < row.length; c++) sb.append(c == 0 ? "" : " ").append(row[c]);
}
return sb.toString();
}
public static void main(String[] args) {
int[][] m = {{1, 1, 1, 1}, {1, 1, 0, 1}, {1, 1, 1, 1}};
int rows = m.length, cols = m[0].length;
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
if (m[r][c] == 0) { // clear its row and column straight away
for (int k = 0; k < cols; k++) m[r][k] = 0;
for (int k = 0; k < rows; k++) m[k][c] = 0;
}
System.out.println(show(m));
}
}
// 1 1 0 0 | 0 0 0 0 | 0 0 0 0#include <bits/stdc++.h>
using namespace std;
string show(const vector<vector<int>>& m) {
string s;
for (auto& row : m) {
if (!s.empty()) s += " | ";
for (size_t c = 0; c < row.size(); c++) s += (c ? " " : "") + to_string(row[c]);
}
return s;
}
int main() {
vector<vector<int>> m = {{1, 1, 1, 1}, {1, 1, 0, 1}, {1, 1, 1, 1}};
int rows = m.size(), cols = m[0].size();
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
if (m[r][c] == 0) { // clear its row and column straight away
for (int k = 0; k < cols; k++) m[r][k] = 0;
for (int k = 0; k < rows; k++) m[k][c] = 0;
}
cout << show(m) << "\n";
}
// 1 1 0 0 | 0 0 0 0 | 0 0 0 0const show = m => m.map(row => row.join(" ")).join(" | ");
const m = [[1, 1, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1]];
const rows = m.length, cols = m[0].length;
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (m[r][c] === 0) { // clear its row and column straight away
for (let k = 0; k < cols; k++) m[r][k] = 0;
for (let k = 0; k < rows; k++) m[k][c] = 0;
}
console.log(show(m));
// 1 1 0 0 | 0 0 0 0 | 0 0 0 0const show = (m: number[][]): string => m.map(row => row.join(" ")).join(" | ");
const m: number[][] = [[1, 1, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1]];
const rows: number = m.length, cols: number = m[0].length;
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (m[r][c] === 0) { // clear its row and column straight away
for (let k = 0; k < cols; k++) m[r][k] = 0;
for (let k = 0; k < rows; k++) m[k][c] = 0;
}
console.log(show(m));
// 1 1 0 0 | 0 0 0 0 | 0 0 0 0using System;
using System.Linq;
class Program {
static string Show(int[][] m) => string.Join(" | ", m.Select(row => string.Join(" ", row)));
static void Main() {
int[][] m = { new[] {1, 1, 1, 1}, new[] {1, 1, 0, 1}, new[] {1, 1, 1, 1} };
int rows = m.Length, cols = m[0].Length;
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
if (m[r][c] == 0) { // clear its row and column straight away
for (int k = 0; k < cols; k++) m[r][k] = 0;
for (int k = 0; k < rows; k++) m[k][c] = 0;
}
Console.WriteLine(Show(m));
}
}
// 1 1 0 0 | 0 0 0 0 | 0 0 0 0package main
import (
"fmt"
"strings"
)
func show(m [][]int) string {
rows := make([]string, len(m))
for i, row := range m {
rows[i] = strings.Trim(fmt.Sprint(row), "[]")
}
return strings.Join(rows, " | ")
}
func main() {
m := [][]int{{1, 1, 1, 1}, {1, 1, 0, 1}, {1, 1, 1, 1}}
rows, cols := len(m), len(m[0])
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if m[r][c] == 0 { // clear its row and column straight away
for k := 0; k < cols; k++ {
m[r][k] = 0
}
for k := 0; k < rows; k++ {
m[k][c] = 0
}
}
}
}
fmt.Println(show(m))
}
// 1 1 0 0 | 0 0 0 0 | 0 0 0 0It printed 1 1 0 0 | 0 0 0 0 | 0 0 0 0, where the answer is 1 1 0 1 | 0 0 0 0 | 1 1 0 1. The 0s it wrote were found later in the scan and cleared their own rows and columns, so they spread to most of the matrix. Find every 0 first, then clear.
One mark for the shared corner. Letting column 0's 0s mark (0, 0) too, and then clearing row 0 and column 0 together when (0, 0) is 0:
def show(m):
return " | ".join(" ".join(map(str, row)) for row in m)
m = [[1, 1, 1], [0, 1, 1], [1, 1, 1]]
rows, cols = len(m), len(m[0])
for r in range(rows):
for c in range(cols): # column 0 too: its mark goes into m[0][0], row 0's mark
if m[r][c] == 0:
m[r][0] = 0
m[0][c] = 0
for r in range(1, rows):
for c in range(1, cols):
if m[r][0] == 0 or m[0][c] == 0:
m[r][c] = 0
if m[0][0] == 0: # meant for row 0 and column 0 at once
for c in range(cols):
m[0][c] = 0
for r in range(rows):
m[r][0] = 0
print(show(m))
# 0 0 0 | 0 0 0 | 0 1 1public class Main {
static String show(int[][] m) {
StringBuilder sb = new StringBuilder();
for (int[] row : m) {
if (sb.length() > 0) sb.append(" | ");
for (int c = 0; c < row.length; c++) sb.append(c == 0 ? "" : " ").append(row[c]);
}
return sb.toString();
}
public static void main(String[] args) {
int[][] m = {{1, 1, 1}, {0, 1, 1}, {1, 1, 1}};
int rows = m.length, cols = m[0].length;
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) // column 0 too: its mark goes into m[0][0], row 0's mark
if (m[r][c] == 0) {
m[r][0] = 0;
m[0][c] = 0;
}
for (int r = 1; r < rows; r++)
for (int c = 1; c < cols; c++)
if (m[r][0] == 0 || m[0][c] == 0) m[r][c] = 0;
if (m[0][0] == 0) { // meant for row 0 and column 0 at once
for (int c = 0; c < cols; c++) m[0][c] = 0;
for (int r = 0; r < rows; r++) m[r][0] = 0;
}
System.out.println(show(m));
}
}
// 0 0 0 | 0 0 0 | 0 1 1#include <bits/stdc++.h>
using namespace std;
string show(const vector<vector<int>>& m) {
string s;
for (auto& row : m) {
if (!s.empty()) s += " | ";
for (size_t c = 0; c < row.size(); c++) s += (c ? " " : "") + to_string(row[c]);
}
return s;
}
int main() {
vector<vector<int>> m = {{1, 1, 1}, {0, 1, 1}, {1, 1, 1}};
int rows = m.size(), cols = m[0].size();
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) // column 0 too: its mark goes into m[0][0], row 0's mark
if (m[r][c] == 0) {
m[r][0] = 0;
m[0][c] = 0;
}
for (int r = 1; r < rows; r++)
for (int c = 1; c < cols; c++)
if (m[r][0] == 0 || m[0][c] == 0) m[r][c] = 0;
if (m[0][0] == 0) { // meant for row 0 and column 0 at once
for (int c = 0; c < cols; c++) m[0][c] = 0;
for (int r = 0; r < rows; r++) m[r][0] = 0;
}
cout << show(m) << "\n";
}
// 0 0 0 | 0 0 0 | 0 1 1const show = m => m.map(row => row.join(" ")).join(" | ");
const m = [[1, 1, 1], [0, 1, 1], [1, 1, 1]];
const rows = m.length, cols = m[0].length;
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++) // column 0 too: its mark goes into m[0][0], row 0's mark
if (m[r][c] === 0) {
m[r][0] = 0;
m[0][c] = 0;
}
for (let r = 1; r < rows; r++)
for (let c = 1; c < cols; c++)
if (m[r][0] === 0 || m[0][c] === 0) m[r][c] = 0;
if (m[0][0] === 0) { // meant for row 0 and column 0 at once
for (let c = 0; c < cols; c++) m[0][c] = 0;
for (let r = 0; r < rows; r++) m[r][0] = 0;
}
console.log(show(m));
// 0 0 0 | 0 0 0 | 0 1 1const show = (m: number[][]): string => m.map(row => row.join(" ")).join(" | ");
const m: number[][] = [[1, 1, 1], [0, 1, 1], [1, 1, 1]];
const rows: number = m.length, cols: number = m[0].length;
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++) // column 0 too: its mark goes into m[0][0], row 0's mark
if (m[r][c] === 0) {
m[r][0] = 0;
m[0][c] = 0;
}
for (let r = 1; r < rows; r++)
for (let c = 1; c < cols; c++)
if (m[r][0] === 0 || m[0][c] === 0) m[r][c] = 0;
if (m[0][0] === 0) { // meant for row 0 and column 0 at once
for (let c = 0; c < cols; c++) m[0][c] = 0;
for (let r = 0; r < rows; r++) m[r][0] = 0;
}
console.log(show(m));
// 0 0 0 | 0 0 0 | 0 1 1using System;
using System.Linq;
class Program {
static string Show(int[][] m) => string.Join(" | ", m.Select(row => string.Join(" ", row)));
static void Main() {
int[][] m = { new[] {1, 1, 1}, new[] {0, 1, 1}, new[] {1, 1, 1} };
int rows = m.Length, cols = m[0].Length;
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) // column 0 too: its mark goes into m[0][0], row 0's mark
if (m[r][c] == 0) {
m[r][0] = 0;
m[0][c] = 0;
}
for (int r = 1; r < rows; r++)
for (int c = 1; c < cols; c++)
if (m[r][0] == 0 || m[0][c] == 0) m[r][c] = 0;
if (m[0][0] == 0) { // meant for row 0 and column 0 at once
for (int c = 0; c < cols; c++) m[0][c] = 0;
for (int r = 0; r < rows; r++) m[r][0] = 0;
}
Console.WriteLine(Show(m));
}
}
// 0 0 0 | 0 0 0 | 0 1 1package main
import (
"fmt"
"strings"
)
func show(m [][]int) string {
rows := make([]string, len(m))
for i, row := range m {
rows[i] = strings.Trim(fmt.Sprint(row), "[]")
}
return strings.Join(rows, " | ")
}
func main() {
m := [][]int{{1, 1, 1}, {0, 1, 1}, {1, 1, 1}}
rows, cols := len(m), len(m[0])
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ { // column 0 too: its mark goes into m[0][0], row 0's mark
if m[r][c] == 0 {
m[r][0] = 0
m[0][c] = 0
}
}
}
for r := 1; r < rows; r++ {
for c := 1; c < cols; c++ {
if m[r][0] == 0 || m[0][c] == 0 {
m[r][c] = 0
}
}
}
if m[0][0] == 0 { // meant for row 0 and column 0 at once
for c := 0; c < cols; c++ {
m[0][c] = 0
}
for r := 0; r < rows; r++ {
m[r][0] = 0
}
}
fmt.Println(show(m))
}
// 0 0 0 | 0 0 0 | 0 1 1It printed 0 0 0 | 0 0 0 | 0 1 1: row 0 was cleared, though it never held a 0. The right answer is 0 1 1 | 0 0 0 | 0 1 1. (0, 0) can't stand for both row 0 and column 0: give one of them its own flag.
Game of Life updated in place, one bit per cell. The blinker again, with each new value written straight over the old:
def show(m):
return " | ".join(" ".join(map(str, row)) for row in m)
board = [[0, 1, 0], [0, 1, 0], [0, 1, 0]]
rows, cols = len(board), len(board[0])
for r in range(rows):
for c in range(cols):
live = 0
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
nr, nc = r + dr, c + dc
if (dr or dc) and 0 <= nr < rows and 0 <= nc < cols:
live += board[nr][nc] # some of these already hold the next generation
board[r][c] = 1 if live == 3 or (board[r][c] == 1 and live == 2) else 0
print(show(board))
# 0 0 0 | 0 0 0 | 0 0 0public class Main {
static String show(int[][] m) {
StringBuilder sb = new StringBuilder();
for (int[] row : m) {
if (sb.length() > 0) sb.append(" | ");
for (int c = 0; c < row.length; c++) sb.append(c == 0 ? "" : " ").append(row[c]);
}
return sb.toString();
}
public static void main(String[] args) {
int[][] board = {{0, 1, 0}, {0, 1, 0}, {0, 1, 0}};
int rows = board.length, cols = board[0].length;
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) {
int live = 0;
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if ((dr != 0 || dc != 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += board[nr][nc]; // some of these already hold the next generation
}
board[r][c] = live == 3 || (board[r][c] == 1 && live == 2) ? 1 : 0;
}
System.out.println(show(board));
}
}
// 0 0 0 | 0 0 0 | 0 0 0#include <bits/stdc++.h>
using namespace std;
string show(const vector<vector<int>>& m) {
string s;
for (auto& row : m) {
if (!s.empty()) s += " | ";
for (size_t c = 0; c < row.size(); c++) s += (c ? " " : "") + to_string(row[c]);
}
return s;
}
int main() {
vector<vector<int>> board = {{0, 1, 0}, {0, 1, 0}, {0, 1, 0}};
int rows = board.size(), cols = board[0].size();
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) {
int live = 0;
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if ((dr != 0 || dc != 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += board[nr][nc]; // some of these already hold the next generation
}
board[r][c] = live == 3 || (board[r][c] == 1 && live == 2) ? 1 : 0;
}
cout << show(board) << "\n";
}
// 0 0 0 | 0 0 0 | 0 0 0const show = m => m.map(row => row.join(" ")).join(" | ");
const board = [[0, 1, 0], [0, 1, 0], [0, 1, 0]];
const rows = board.length, cols = board[0].length;
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++) {
let live = 0;
for (let dr = -1; dr <= 1; dr++)
for (let dc = -1; dc <= 1; dc++) {
const nr = r + dr, nc = c + dc;
if ((dr !== 0 || dc !== 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += board[nr][nc]; // some of these already hold the next generation
}
board[r][c] = live === 3 || (board[r][c] === 1 && live === 2) ? 1 : 0;
}
console.log(show(board));
// 0 0 0 | 0 0 0 | 0 0 0const show = (m: number[][]): string => m.map(row => row.join(" ")).join(" | ");
const board: number[][] = [[0, 1, 0], [0, 1, 0], [0, 1, 0]];
const rows: number = board.length, cols: number = board[0].length;
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++) {
let live = 0;
for (let dr = -1; dr <= 1; dr++)
for (let dc = -1; dc <= 1; dc++) {
const nr = r + dr, nc = c + dc;
if ((dr !== 0 || dc !== 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += board[nr][nc]; // some of these already hold the next generation
}
board[r][c] = live === 3 || (board[r][c] === 1 && live === 2) ? 1 : 0;
}
console.log(show(board));
// 0 0 0 | 0 0 0 | 0 0 0using System;
using System.Linq;
class Program {
static string Show(int[][] m) => string.Join(" | ", m.Select(row => string.Join(" ", row)));
static void Main() {
int[][] board = { new[] {0, 1, 0}, new[] {0, 1, 0}, new[] {0, 1, 0} };
int rows = board.Length, cols = board[0].Length;
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) {
int live = 0;
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if ((dr != 0 || dc != 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += board[nr][nc]; // some of these already hold the next generation
}
board[r][c] = live == 3 || (board[r][c] == 1 && live == 2) ? 1 : 0;
}
Console.WriteLine(Show(board));
}
}
// 0 0 0 | 0 0 0 | 0 0 0package main
import (
"fmt"
"strings"
)
func show(m [][]int) string {
rows := make([]string, len(m))
for i, row := range m {
rows[i] = strings.Trim(fmt.Sprint(row), "[]")
}
return strings.Join(rows, " | ")
}
func main() {
board := [][]int{{0, 1, 0}, {0, 1, 0}, {0, 1, 0}}
rows, cols := len(board), len(board[0])
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
live := 0
for dr := -1; dr <= 1; dr++ {
for dc := -1; dc <= 1; dc++ {
nr, nc := r+dr, c+dc
if (dr != 0 || dc != 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols {
live += board[nr][nc] // some of these already hold the next generation
}
}
}
if live == 3 || (board[r][c] == 1 && live == 2) {
board[r][c] = 1
} else {
board[r][c] = 0
}
}
}
fmt.Println(show(board))
}
// 0 0 0 | 0 0 0 | 0 0 0The blinker vanished, 0 0 0 | 0 0 0 | 0 0 0, where it should have turned on its side. The top cell died first, so the cells after it counted one live neighbour too few. Keep both generations: two bits per cell.
Check yourself
Quiz
1 / 6Multiple choice
[[1, 2], [3, 4]] is transposed, then each row is reversed. Which turn is that?
Multiple choice
Rotating a 5 × 5 matrix layer by layer: how many layers are turned?
Multiple choice
In a 4 × 4 matrix turned a quarter clockwise, where does the value at (0, 1) go?
Multiple choice
Set Matrix Zeroes on [[1, 0], [1, 1]]: what comes out?
Multiple choice
In Game of Life with two bits per cell, a cell holds 2, binary 10. What is it?
Multiple choice
Game of Life on [[1, 1, 1], [0, 0, 0], [0, 0, 0]], a row of three along the top edge: what's the next board?
Practice
In this section, easy to hard:
- Rotate Image: a transpose, then each row reversed, or the layers' cycles of four.
- Set Matrix Zeroes: row 0 and column 0 as the marks, and column 0's own flag.
- Game of Life: two bits per cell, then one shift.
Matrix Quiz, at the end of this section, mixes both lessons.