Shift Matrix - C++ Solution

1. Introduction

The "Shift Matrix" problem is a fascinating array manipulation challenge that requires shifting all elements of a matrix by one position in a spiral order. It's a unique problem that tests a developer's ability to implement complex matrix traversal and modification techniques, often seen in advanced programming scenarios.

Problem

Given an M × N integer matrix, the task is to shift all its elements by one position in a spiral order. The spiral order means moving along the matrix in a clockwise spiral, and wrapping the last element to the first position.

2. Solution Steps

1. Extract the elements of the matrix in a spiral order and store them in an array.

2. Perform a right circular shift on this array by one position.

3. Refill the matrix with the shifted elements, placing them back in spiral order.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to extract the elements of a matrix in spiral order
vector<int> getSpiralOrder(const vector<vector<int>>& matrix) {
    vector<int> result;
    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;

    while (top <= bottom && left <= right) {
        // Traverse from left to right
        for (int i = left; i <= right; i++) result.push_back(matrix[top][i]);
        top++;

        // Traverse downwards
        for (int i = top; i <= bottom; i++) result.push_back(matrix[i][right]);
        right--;

        // Check if top or left become out of bounds
        if (!(top <= bottom && left <= right)) break;

        // Traverse from right to left
        for (int i = right; i >= left; i--) result.push_back(matrix[bottom][i]);
        bottom--;

        // Traverse upwards
        for (int i = bottom; i >= top; i--) result.push_back(matrix[i][left]);
        left++;
    }

    return result;
}

// Function to shift the matrix in spiral order
void shiftSpiralMatrix(vector<vector<int>>& matrix) {
    vector<int> spiralOrder = getSpiralOrder(matrix);
    // Perform a circular shift
    spiralOrder.insert(spiralOrder.begin(), spiralOrder.back());
    spiralOrder.pop_back();

    // Refill the matrix in spiral order
    int index = 0, m = matrix.size(), n = matrix[0].size();
    int top = 0, bottom = m - 1, left = 0, right = n - 1;

    while (top <= bottom && left <= right) {
        // Refill from left to right
        for (int i = left; i <= right; i++) matrix[top][i] = spiralOrder[index++];
        top++;

        // Refill downwards
        for (int i = top; i <= bottom; i++) matrix[i][right] = spiralOrder[index++];
        right--;

        // Check if top or left become out of bounds
        if (!(top <= bottom && left <= right)) break;

        // Refill from right to left
        for (int i = right; i >= left; i--) matrix[bottom][i] = spiralOrder[index++];
        bottom--;

        // Refill upwards
        for (int i = bottom; i >= top; i--) matrix[i][left] = spiralOrder[index++];
        left++;
    }
}

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3, 4, 5},
        {16, 17, 18, 19, 6},
        {15, 24, 25, 20, 7},
        {14, 23, 22, 21, 8},
        {13, 12, 11, 10, 9}
    };

    shiftSpiralMatrix(matrix);

    // Print the shifted matrix
    for (const auto& row : matrix) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    return 0;
}

Output:

25 1 2 3 4

Explanation:

The program first extracts elements from the matrix in a spiral order and stores them in an array. 

It then shifts this array to the right by one position, effectively moving the last element to the first position. 

Finally, it refills the matrix with these shifted elements, again placing them in a spiral order. 

This method provides an elegant solution to the problem, ensuring the matrix is shifted as required while maintaining the integrity of its spiral structure.