vector_2d_operations.cpp

/*
 * ============================================================================
 *  2D Vector Operations — Comprehensive Demo
 *  File: vector_2d_operations.cpp
 *
 *  A 2D array in C++ is commonly represented as vector<vector<int>>.
 *  This file covers:
 *    1.  Construction & initialization (various ways)
 *    2.  Accessing elements
 *    3.  Modifying size (add/remove rows and columns)
 *    4.  Iterating (nested loops, range-based for, iterators)
 *    5.  Row-wise and column-wise operations
 *    6.  Transpose
 *    7.  Matrix addition and multiplication
 *    8.  Searching in a 2D vector
 *    9.  Sorting rows and columns
 *   10.  Practical example: spiral order traversal
 *
 *  Compile: g++ -std=c++11 -Wall -o vector_2d_operations vector_2d_operations.cpp
 *  Run:     ./vector_2d_operations
 * ============================================================================
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iomanip>    // setw for aligned printing

using namespace std;

// Helper: print a 2D vector as a matrix with a label
void printMatrix(const string& label, const vector<vector<int>>& mat) {
    cout << label << " (" << mat.size() << " rows";
    if (!mat.empty()) cout << " x " << mat[0].size() << " cols";
    cout << "):" << endl;

    for (size_t i = 0; i < mat.size(); ++i) {
        cout << "  [ ";
        for (size_t j = 0; j < mat[i].size(); ++j) {
            cout << setw(4) << mat[i][j];
            if (j + 1 < mat[i].size()) cout << ", ";
        }
        cout << " ]" << endl;
    }
    cout << endl;
}

// Helper: print a 1D vector
void printVec(const string& label, const vector<int>& v) {
    cout << label << " [";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i > 0) cout << ", ";
        cout << v[i];
    }
    cout << "]" << endl;
}

int main() {
    cout << "============================================" << endl;
    cout << "  2D std::vector Operations Demo" << endl;
    cout << "============================================\n" << endl;

    // ──────────────────────────────────────────────
    // 1. Construction & Initialization
    // ──────────────────────────────────────────────
    cout << "--- 1. Construction & Initialization ---\n" << endl;

    // Method A: Empty 2D vector (0 rows)
    vector<vector<int>> m1;
    printMatrix("m1 (empty)", m1);

    // Method B: R rows x C cols, all initialized to 0
    int R = 3, C = 4;
    vector<vector<int>> m2(R, vector<int>(C, 0));
    printMatrix("m2 (3x4, all 0)", m2);

    // Method C: R rows x C cols with a specific fill value
    vector<vector<int>> m3(2, vector<int>(3, -1));
    printMatrix("m3 (2x3, all -1)", m3);

    // Method D: Initializer list (C++11)
    vector<vector<int>> m4 = {
        {1,  2,  3,  4},
        {5,  6,  7,  8},
        {9, 10, 11, 12}
    };
    printMatrix("m4 (init list 3x4)", m4);

    // Method E: Build row by row using push_back
    vector<vector<int>> m5;
    for (int i = 0; i < 3; ++i) {
        vector<int> row;
        for (int j = 0; j < 4; ++j) {
            row.push_back(i * 4 + j + 1);  // 1, 2, 3, ..., 12
        }
        m5.push_back(row);
    }
    printMatrix("m5 (built row-by-row)", m5);

    // Method F: Jagged array — rows of different lengths
    vector<vector<int>> jagged = {
        {1, 2, 3},
        {4, 5},
        {6, 7, 8, 9}
    };
    cout << "jagged (different row lengths):" << endl;
    for (size_t i = 0; i < jagged.size(); ++i) {
        cout << "  row " << i << " (len " << jagged[i].size() << "): ";
        for (int x : jagged[i]) cout << x << " ";
        cout << endl;
    }
    cout << endl;

    // ──────────────────────────────────────────────
    // 2. Accessing Elements
    // ──────────────────────────────────────────────
    cout << "--- 2. Accessing Elements ---\n" << endl;

    // mat[row][col] — no bounds checking
    cout << "m4[0][0] = " << m4[0][0] << "  (top-left)"  << endl;
    cout << "m4[1][2] = " << m4[1][2] << "  (row 1, col 2)" << endl;
    cout << "m4[2][3] = " << m4[2][3] << "  (bottom-right)" << endl;

    // .at(row).at(col) — with bounds checking
    cout << "m4.at(0).at(3) = " << m4.at(0).at(3) << endl;

    // Access an entire row (it's just a vector<int>)
    const vector<int>& row1 = m4[1];
    printVec("m4 row 1", row1);

    // Get dimensions
    cout << "m4 rows = " << m4.size() << ", cols = " << m4[0].size() << endl;

    cout << endl;

    // ──────────────────────────────────────────────
    // 3. Modifying Size (add/remove rows and columns)
    // ──────────────────────────────────────────────
    cout << "--- 3. Modifying Size ---\n" << endl;

    vector<vector<int>> mat = {
        {1, 2, 3},
        {4, 5, 6}
    };
    printMatrix("original", mat);

    // Add a new row at the bottom
    mat.push_back({7, 8, 9});
    printMatrix("after push_back row {7,8,9}", mat);

    // Insert a row at the top
    mat.insert(mat.begin(), {0, 0, 0});
    printMatrix("after insert row {0,0,0} at top", mat);

    // Remove the last row
    mat.pop_back();
    printMatrix("after pop_back (remove last row)", mat);

    // Erase row at index 1
    mat.erase(mat.begin() + 1);
    printMatrix("after erase row at index 1", mat);

    // Add a column to the right of every row
    for (auto& row : mat) {
        row.push_back(99);
    }
    printMatrix("after adding col 99 to each row", mat);

    // Remove the last column from every row
    for (auto& row : mat) {
        row.pop_back();
    }
    printMatrix("after removing last col", mat);

    // Insert a column at index 1 in every row
    for (auto& row : mat) {
        row.insert(row.begin() + 1, -1);
    }
    printMatrix("after inserting col -1 at index 1", mat);

    cout << endl;

    // ──────────────────────────────────────────────
    // 4. Iterating
    // ──────────────────────────────────────────────
    cout << "--- 4. Iterating ---\n" << endl;

    mat = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    // Method A: Classic index-based
    cout << "Index-based:" << endl;
    for (size_t i = 0; i < mat.size(); ++i) {
        for (size_t j = 0; j < mat[i].size(); ++j) {
            cout << mat[i][j] << " ";
        }
        cout << endl;
    }

    // Method B: Range-based for (C++11) — cleanest
    cout << "\nRange-based for:" << endl;
    for (const auto& row : mat) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }

    // Method C: Iterator-based
    cout << "\nIterator-based:" << endl;
    for (auto rowIt = mat.begin(); rowIt != mat.end(); ++rowIt) {
        for (auto colIt = rowIt->begin(); colIt != rowIt->end(); ++colIt) {
            cout << *colIt << " ";
        }
        cout << endl;
    }

    cout << endl;

    // ──────────────────────────────────────────────
    // 5. Row-wise and Column-wise Operations
    // ──────────────────────────────────────────────
    cout << "--- 5. Row-wise and Column-wise Operations ---\n" << endl;

    mat = {
        {3, 1, 4},
        {1, 5, 9},
        {2, 6, 5}
    };
    printMatrix("mat", mat);

    // Row sums
    cout << "Row sums: ";
    for (size_t i = 0; i < mat.size(); ++i) {
        int sum = accumulate(mat[i].begin(), mat[i].end(), 0);
        cout << "row" << i << "=" << sum << "  ";
    }
    cout << endl;

    // Column sums (need to traverse column-major)
    int cols = (int)mat[0].size();
    int rows = (int)mat.size();
    cout << "Col sums: ";
    for (int j = 0; j < cols; ++j) {
        int sum = 0;
        for (int i = 0; i < rows; ++i) {
            sum += mat[i][j];
        }
        cout << "col" << j << "=" << sum << "  ";
    }
    cout << endl;

    // Row max
    cout << "Row max:  ";
    for (size_t i = 0; i < mat.size(); ++i) {
        int mx = *max_element(mat[i].begin(), mat[i].end());
        cout << "row" << i << "=" << mx << "  ";
    }
    cout << "\n" << endl;

    // ──────────────────────────────────────────────
    // 6. Transpose
    // ──────────────────────────────────────────────
    cout << "--- 6. Transpose ---\n" << endl;

    vector<vector<int>> original = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };
    printMatrix("original (3x4)", original);

    // Transpose: swap rows and columns
    int r = (int)original.size();
    int c = (int)original[0].size();
    vector<vector<int>> transposed(c, vector<int>(r));
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            transposed[j][i] = original[i][j];
        }
    }
    printMatrix("transposed (4x3)", transposed);

    // ──────────────────────────────────────────────
    // 7. Matrix Addition and Multiplication
    // ──────────────────────────────────────────────
    cout << "--- 7. Matrix Addition and Multiplication ---\n" << endl;

    vector<vector<int>> A = {
        {1, 2},
        {3, 4}
    };
    vector<vector<int>> B = {
        {5, 6},
        {7, 8}
    };
    printMatrix("A", A);
    printMatrix("B", B);

    // Addition: C[i][j] = A[i][j] + B[i][j]
    int ra = (int)A.size(), ca = (int)A[0].size();
    vector<vector<int>> C(ra, vector<int>(ca));
    for (int i = 0; i < ra; ++i) {
        for (int j = 0; j < ca; ++j) {
            C[i][j] = A[i][j] + B[i][j];
        }
    }
    printMatrix("A + B", C);

    // Multiplication: D[i][j] = sum(A[i][k] * B[k][j]) for all k
    // A is (ra x ca), B is (rb x cb), result is (ra x cb), requires ca == rb
    int rb = (int)B.size(), cb = (int)B[0].size();
    vector<vector<int>> D(ra, vector<int>(cb, 0));
    for (int i = 0; i < ra; ++i) {
        for (int j = 0; j < cb; ++j) {
            for (int k = 0; k < ca; ++k) {
                D[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    printMatrix("A * B", D);
    (void)rb; // suppress unused warning

    // ──────────────────────────────────────────────
    // 8. Searching in a 2D Vector
    // ──────────────────────────────────────────────
    cout << "--- 8. Searching in a 2D Vector ---\n" << endl;

    mat = {
        {10, 20, 30},
        {40, 50, 60},
        {70, 80, 90}
    };
    printMatrix("mat", mat);

    // Linear search for a target value
    int target = 50;
    bool found = false;
    for (int i = 0; i < (int)mat.size() && !found; ++i) {
        for (int j = 0; j < (int)mat[i].size() && !found; ++j) {
            if (mat[i][j] == target) {
                cout << "Found " << target << " at (" << i << ", " << j << ")" << endl;
                found = true;
            }
        }
    }
    if (!found) cout << target << " not found." << endl;

    // Search in row-sorted and column-sorted matrix (staircase search) — O(R+C)
    // Start from top-right corner
    target = 40;
    int si = 0, sj = (int)mat[0].size() - 1;
    found = false;
    while (si < (int)mat.size() && sj >= 0) {
        if (mat[si][sj] == target) {
            cout << "Staircase search: found " << target << " at (" << si << ", " << sj << ")" << endl;
            found = true;
            break;
        } else if (mat[si][sj] > target) {
            --sj;  // eliminate current column (all below are larger)
        } else {
            ++si;  // eliminate current row (all to the left are smaller)
        }
    }
    if (!found) cout << target << " not found." << endl;

    cout << endl;

    // ──────────────────────────────────────────────
    // 9. Sorting Rows and Columns
    // ──────────────────────────────────────────────
    cout << "--- 9. Sorting Rows and Columns ---\n" << endl;

    mat = {
        {9, 3, 7},
        {1, 8, 2},
        {5, 4, 6}
    };
    printMatrix("unsorted", mat);

    // Sort each row individually
    for (auto& row : mat) {
        sort(row.begin(), row.end());
    }
    printMatrix("each row sorted", mat);

    // Sort rows by their first element
    mat = {
        {9, 3, 7},
        {1, 8, 2},
        {5, 4, 6}
    };
    sort(mat.begin(), mat.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });
    printMatrix("rows sorted by first element", mat);

    // Sort columns: transpose → sort rows → transpose back
    mat = {
        {9, 1, 5},
        {3, 8, 4},
        {7, 2, 6}
    };
    printMatrix("before column sort", mat);

    int nr = (int)mat.size(), nc = (int)mat[0].size();
    // Transpose
    vector<vector<int>> t(nc, vector<int>(nr));
    for (int i = 0; i < nr; ++i)
        for (int j = 0; j < nc; ++j)
            t[j][i] = mat[i][j];
    // Sort each (transposed) row = original column
    for (auto& row : t)
        sort(row.begin(), row.end());
    // Transpose back
    for (int i = 0; i < nr; ++i)
        for (int j = 0; j < nc; ++j)
            mat[i][j] = t[j][i];
    printMatrix("each column sorted", mat);

    // ──────────────────────────────────────────────
    // 10. Practical Example: Spiral Order Traversal
    // ──────────────────────────────────────────────
    cout << "--- 10. Spiral Order Traversal ---\n" << endl;

    mat = {
        { 1,  2,  3,  4},
        { 5,  6,  7,  8},
        { 9, 10, 11, 12},
        {13, 14, 15, 16}
    };
    printMatrix("mat", mat);

    // Spiral traversal: top row → right column → bottom row (reversed) → left column (reversed)
    // Shrink boundaries each time.
    vector<int> spiral;
    int top = 0, bottom = (int)mat.size() - 1;
    int left = 0, right = (int)mat[0].size() - 1;

    while (top <= bottom && left <= right) {
        // Traverse top row left → right
        for (int j = left; j <= right; ++j)
            spiral.push_back(mat[top][j]);
        ++top;

        // Traverse right column top → bottom
        for (int i = top; i <= bottom; ++i)
            spiral.push_back(mat[i][right]);
        --right;

        // Traverse bottom row right → left
        if (top <= bottom) {
            for (int j = right; j >= left; --j)
                spiral.push_back(mat[bottom][j]);
            --bottom;
        }

        // Traverse left column bottom → top
        if (left <= right) {
            for (int i = bottom; i >= top; --i)
                spiral.push_back(mat[i][left]);
            ++left;
        }
    }

    printVec("Spiral order", spiral);

    cout << "\n============================================" << endl;
    cout << "  Done." << endl;
    cout << "============================================" << endl;

    return 0;
}