Loose Screws

How to solve "Matrix Layer Rotation" on HackerRank

January 31, 2025 | 48 Minute Read

The challenge is to split a matrix into concentric rings, and rotate each ring a certain number of places to the left. To do that, all we really need to do is figure out how to look at each ring as if it were a flat array. That can be broken down into two challenges: the mathematics, and the code.

The mathematics

We’re given a matrix mm of width ww and height hh. We want to convert a ring of that matrix inset rr rows and columns into a flat sequence aa. For instance, given a 7×67 \times 6 matrix and an offset r=1r=1:

m=[zzzzzzzza0a1a2a3b0zzd2zzzb1zzd1zzzb2zzd0c3c2c1c0zzzzzzzz]\gdef\ca#1{ {\color{royalblue}#1}} \gdef\cb#1{ {\color{plum}#1}} \gdef\cc#1{ {\color{cyan}#1}} \gdef\cd#1{ {\color{goldenrod}#1}} \gdef\ce#1{ {#1}} m = \left[ \begin{matrix} \ce{z} & \ce{z} & \ce{z} & \ce{z} & \ce{z} & \ce{z} & \ce{z} \\ \ce{z} & \ca{a_0} & \ca{a_1} & \ca{a_2} & \ca{a_3} & \cb{b_0} & \ce{z} \\ \ce{z} & \cd{d_2} & \ce{z} & \ce{z} & \ce{z} & \cb{b_1} & \ce{z} \\ \ce{z} & \cd{d_1} & \ce{z} & \ce{z} & \ce{z} & \cb{b_2} & \ce{z} \\ \ce{z} & \cd{d_0} & \cc{c_3} & \cc{c_2} & \cc{c_1} & \cc{c_0} & \ce{z} \\ \ce{z} & \ce{z} & \ce{z} & \ce{z} & \ce{z} & \ce{z} & \ce{z} \end{matrix} \right]

we want the flat sequence:

a0…13={a0,a1,a2,a3,b0,b1,b2,c0,c1,c2,c3,d0,d1,d2}\gdef\ca#1{ {\color{royalblue}#1}} \gdef\cb#1{ {\color{plum}#1}} \gdef\cc#1{ {\color{cyan}#1}} \gdef\cd#1{ {\color{goldenrod}#1}} \gdef\ce#1{ {#1}} a_{0\dots 13} = \{ \ca{a_0}, \ca{a_1}, \ca{a_2}, \ca{a_3}, \cb{b_0}, \cb{b_1}, \cb{b_2}, \cc{c_0}, \cc{c_1}, \cc{c_2}, \cc{c_3}, \cd{d_0}, \cd{d_1}, \cd{d_2} \}

To construct that sequence, we need matrix coordinates x(n)x(n) and y(n)y(n) for each value of ana_n such that we can define aa as:

an=my(n)x(n)\begin{equation} a_n = m_{y(n)x(n)} \end{equation}

Let’s start by defining the widths of the horizontal segments (aa and cc) and the heights of the vertical segments (bb and dd) as w′w' and h′h' respectively:

w′=w−2r−1h′=h−2r−1\begin{align} w' &= w - 2r - 1 \\ h' &= h - 2r - 1 \\ \end{align}

We can use those either to calculate the xx and yy offset of each nn individually:

x(n)=r+{nif n<w′w′if n≥w′ and n<w′+h′2w′+h′−n ⁣if n≥w′+h′ and n<2w′+h′0if n≥2w′+h′y(n)=r+{0if n<w′n−w′if n≥w′ and n<w′+h′h′if n≥w′+h′ and n<2w′+h′2(w′+h′)−nif n≥2w′+h′\begin{align} x(n) &= r + \begin{cases} n & \text{if } n < w' \\ w' & \text{if } n \ge w' \text{ and } n < w'+h' \\ 2w' + h' - n\quad\! & \text{if } n \ge w'+h' \text{ and } n < 2w'+h' \\ 0 & \text{if } n \ge 2w'+h' \end{cases} \\ y(n) &= r + \begin{cases} 0 & \text{if } n < w' \\ n - w' & \text{if } n \ge w' \text{ and } n < w'+h' \\ h' & \text{if } n \ge w'+h' \text{ and } n < 2w'+h' \\ 2(w' + h') - n & \text{if } n \ge 2w'+h' \end{cases} \end{align}

Or we can calculate them somewhat more simply by looking at each segment in sequence, keeping track of the value of nn relative to its start, and incrementing and decrementing xx and yy as appropriate:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

size_t x = r;
size_t y = r;

x += min(n, w_);
if (n > w_) {
    n -= w_;
    y += min(n, h_);

    if (n > h_) {
        n -= h_;
        x -= min(n, w_);

        if (n > w_) {
            n -= w_;
            y -= n;
        }
    }
}

C++ helper class

In C++, things will be easiest if we can simply treat each matrix ring as a flat array. To do that, we need a helper class that we can initialize with a matrix and an offset, and then access as an array:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

using Coord = tuple<size_t, size_t>;

class MatrixRing {
    vector<vector<int>>& matrix_;
    size_t offset_;
    size_t len_;
    size_t w_;
    size_t h_;

  public:
    MatrixRing(vector<vector<int>>& matrix, size_t offset)
        : matrix_(matrix), offset_(offset)
    {
        h_ = matrix.size() - 2 * offset - 1;
        w_ = matrix[0].size() - 2 * offset - 1;
        len_ = 2 * (w_ + h_);
    }

    size_t size() const { return len_; }

    Coord coord(size_t ord) const {
        ord %= len_;

        size_t x = offset_;
        size_t y = offset_;

        x += min(ord, w_);
        if (ord > w_) {
            ord -= w_;
            y += min(ord, h_);

            if (ord > h_) {
                ord -= h_;
                x -= min(ord, w_);

                if (ord > w_) {
                    ord -= w_;
                    y -= ord;
                }
            }
        }
        return {x, y};
    }

    int& operator[](size_t ord) {
        auto [x, y] = coord(ord);

        return matrix_[y][x];
    }

    const int& operator[](size_t ord) const {
        auto [x, y] = coord(ord);

        return matrix_[y][x];
    }
};

This helper has the added feature of efficiently treating each ring as a circle. Accessing elements past the end of the ring will simply circle back around to the beginning.

Now, we could use this helper to solve the challenge without any further modifications. However, as with many things in C++, it would benefit from iterator support, which we can add fairly simply:

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
34
35
36
37
38
39
40
41
42

template<typename MatrixRing>
class iterator_base {
    MatrixRing& ring_;
    size_t ord_;
public:
    using reference = decltype(declval<MatrixRing>()[0]);

    using iterator_category = std::random_access_iterator_tag;
    using value_type = std::decay_t<reference>;
    using difference_type = size_t;
    using pointer = std::remove_reference_t<reference>*;

    explicit iterator_base(MatrixRing& ring, size_t ord)
        : ring_(ring), ord_(ord)
    {}

    iterator_base& operator++() { ord_++; return *this; }
    iterator_base operator++(int) { iterator_base retval = *this; ++(*this); return retval; }

    iterator_base& operator--() { ord_--; return *this; }
    iterator_base operator--(int) { iterator_base retval = *this; --(*this); return retval; }

    iterator_base& operator+=(size_t val) { ord_ += val; return *this; }
    iterator_base operator+(size_t val) const { iterator_base retval = *this; retval += val; return retval; }

    iterator_base& operator-=(size_t val) { ord_ -= val; return *this; }
    iterator_base operator-(size_t val) const { iterator_base retval = *this; retval -= val; return retval; }

    bool operator==(const iterator_base& other) const { return ord_ == other.ord_; }
    bool operator!=(const iterator_base& other) const { return !(*this == other); }

    size_t operator-(const iterator_base& other) const { return ord_ - other.ord_; }

    reference operator*() const { return ring_[ord_]; }
};
using iterator = iterator_base<MatrixRing>;
using const_iterator = iterator_base<const MatrixRing>;

iterator begin() { return iterator(*this, 0); }
iterator end() { return iterator(*this, len_); }
const_iterator cbegin() const { return const_iterator(*this, 0); }
const_iterator cend() const { return const_iterator(*this, len_); }

The matrix rotation

With those helpers out of the way, the solution to the challenge becomes fairly simple:

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
34

void matrixRotation(vector<vector<int>> matrix, int r) {
    int h = matrix.size();
    int w = matrix[0].size();
    int m = min(w, h) / 2;

    // Rotate each ring r places to the left
    for (int i = 0; i < m; i++) {
        MatrixRing ring(matrix, i);

        // Factor out any complete rotations to figure out the number of
        // places we need to rotate
        int n = r % ring.size();

        // Figure out the starting position for the rotation.
        // We'll rotate left from this position, so element n becomes element
        // 0, n+1 becomes 1, ...
        auto start = ring.begin() + n;

        // Create a temporary array of the ring contents rotated n positions
        // to the left
        vector<int> rot(start, start + ring.size());

        // Copy the rotated values back into the ring
        copy(rot.begin(), rot.end(), ring.begin());
    }

    // Print the result
    for (auto& row : matrix) {
        for (auto& val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
}

The complete code

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

#include <bits/stdc++.h>
#include <iterator>

using namespace std;

using Coord = tuple<size_t, size_t>;

class MatrixRing {
    vector<vector<int>>& matrix_;
    size_t offset_;
    size_t len_;
    size_t w_;
    size_t h_;

  public:
    template<typename MatrixRing>
    class iterator_base {
        MatrixRing& ring_;
        size_t ord_;
    public:
        using reference = decltype(declval<MatrixRing>()[0]);

        using iterator_category = std::random_access_iterator_tag;
        using value_type = std::decay_t<reference>;
        using difference_type = size_t;
        using pointer = std::remove_reference_t<reference>*;

        explicit iterator_base(MatrixRing& ring, size_t ord)
            : ring_(ring), ord_(ord)
        {}

        iterator_base& operator++() { ord_++; return *this; }
        iterator_base operator++(int) { iterator_base retval = *this; ++(*this); return retval; }

        iterator_base& operator--() { ord_--; return *this; }
        iterator_base operator--(int) { iterator_base retval = *this; --(*this); return retval; }

        iterator_base& operator+=(size_t val) { ord_ += val; return *this; }
        iterator_base operator+(size_t val) const { iterator_base retval = *this; retval += val; return retval; }

        iterator_base& operator-=(size_t val) { ord_ -= val; return *this; }
        iterator_base operator-(size_t val) const { iterator_base retval = *this; retval -= val; return retval; }

        bool operator==(const iterator_base& other) const { return ord_ == other.ord_; }
        bool operator!=(const iterator_base& other) const { return !(*this == other); }

        size_t operator-(const iterator_base& other) const { return ord_ - other.ord_; }

        reference operator*() const { return ring_[ord_]; }
    };
    using iterator = iterator_base<MatrixRing>;
    using const_iterator = iterator_base<const MatrixRing>;

    iterator begin() { return iterator(*this, 0); }
    iterator end() { return iterator(*this, len_); }
    const_iterator cbegin() const { return const_iterator(*this, 0); }
    const_iterator cend() const { return const_iterator(*this, len_); }

    MatrixRing(vector<vector<int>>& matrix, size_t offset)
        : matrix_(matrix), offset_(offset)
    {
        h_ = matrix.size() - 2 * offset - 1;
        w_ = matrix[0].size() - 2 * offset - 1;
        len_ = 2 * (w_ + h_);
    }

    size_t size() const { return len_; }

    Coord coord(size_t ord) const {
        ord %= len_;

        size_t x = offset_;
        size_t y = offset_;

        x += min(ord, w_);
        if (ord > w_) {
            ord -= w_;
            y += min(ord, h_);

            if (ord > h_) {
                ord -= h_;
                x -= min(ord, w_);

                if (ord > w_) {
                    ord -= w_;
                    y -= ord;
                }
            }
        }
        return {x, y};
    }

    int& operator[](size_t ord) {
        auto [x, y] = coord(ord);

        return matrix_[y][x];
    }

    const int& operator[](size_t ord) const {
        auto [x, y] = coord(ord);

        return matrix_[y][x];
    }
};

void matrixRotation(vector<vector<int>> matrix, int r) {
    int h = matrix.size();
    int w = matrix[0].size();
    int m = min(w, h) / 2;

    for (int i = 0; i < m; i++) {
        MatrixRing ring(matrix, i);

        int n = r % ring.size();
        auto start = ring.begin() + n;

        vector<int> rot(start, start + ring.size());
        copy(rot.begin(), rot.end(), ring.begin());
    }

    for (auto& row : matrix) {
        for (auto& val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
}

© 2013–2025 Kris Maglione Powered by Jekyll