Coils in Matrix

Problem Overview

The matrix is filled in row order, so the value at row r and column c is r times 4n plus c plus 1, and nothing has to be built.

Intuition

The matrix is filled in row order, so the value at row r and column c is r times 4n plus c plus 1, and nothing has to be built. Every ring splits into two halves: down the left column then along the bottom, and up the right column then back along the top. The coils take those halves in turns from ring to ring. The second half of each ring is the first half rotated 180 degrees, which means the second coil is simply 16n squared plus 1 minus each entry of the first.

Algorithm

1Let size be 4n and walk the rings from the outside in.
2On an even ring, coil 1 goes down the left column, then right along the bottom row, stopping before the corner.
3On an odd ring, coil 1 goes up the right column, then left along the top row, stopping before the corner.
4Compute each value from its row and column instead of reading a stored matrix.
5Build coil 2 by replacing every value v of coil 1 with 16n squared plus 1 minus v.

Example Walkthrough

Input: n = 1

1. The outer ring is even, so coil 1 reads 1, 5, 9, 13 down the left and then 14, 15 along the bottom.
2. The inner ring is odd, so coil 1 reads 11 and then 7 up its right column.
3. Coil 2 subtracts each value from 17, giving 16, 12, 8, 4, 3, 2, 6, 10.

Output: [[1,5,9,13,14,15,11,7],[16,12,8,4,3,2,6,10]]

Common Pitfalls

• Each half ring stops one cell before the next corner, or the two coils share a corner cell.
• The coils swap which half they take on every ring, so check the ring parity.
• Building the full 4n by 4n matrix uses 16n squared extra cells that the row and column formula makes unnecessary.
• Walking both coils separately doubles the work. The 180 degree symmetry gives the second coil from the first.

Coils in Matrix.java

Java

// Approach: The cell at (r, c) holds r * 4n + c + 1, so no matrix is built.
// Each ring has two halves: down the left column then right along the
// bottom, and up the right column then left along the top. Coil 1 takes the
// first half on even rings and the second half on odd rings. The second coil
// is the first rotated 180 degrees, so each entry is 16n^2 + 1 minus the
// matching entry of coil 1.
// Complexity: O(n^2) time, O(1) extra space beyond the two coils.
import java.util.ArrayList;

class Solution {
    public ArrayList<ArrayList<Integer>> formCoils(int n) {
        int size = 4 * n;
        int total = size * size;
        int[] coil = new int[total / 2];
        int k = 0;

        for (int ring = 0; ring < size / 2; ring++) {
            int lo = ring;
            int hi = size - 1 - ring;
            if ((ring & 1) == 0) {
                for (int r = lo; r <= hi; r++)
                    coil[k++] = r * size + lo + 1;
                for (int c = lo + 1; c < hi; c++)
                    coil[k++] = hi * size + c + 1;
            } else {
                for (int r = hi; r >= lo; r--)
                    coil[k++] = r * size + hi + 1;
                for (int c = hi - 1; c > lo; c--)
                    coil[k++] = lo * size + c + 1;
            }
        }

        ArrayList<Integer> first = new ArrayList<>(coil.length);
        ArrayList<Integer> second = new ArrayList<>(coil.length);
        for (int v : coil) {
            first.add(v);
            second.add(total + 1 - v);
        }

        ArrayList<ArrayList<Integer>> ans = new ArrayList<>(2);
        ans.add(first);
        ans.add(second);
        return ans;
    }
}

Was this solution helpful?