Creating Rectangle in Square Matrix with Two Filled Positions

Given a square matrix of n order in which two positions are filled. Fill two more positions such that a rectangle is formed by joining all points.

Examples:

Input: n=4
Matrix[][]=  1 0 0 1 
             0 0 0 0
             0 0 0 0
Output:
Matrix[][]= 1 0 0 1 
            1 0 0 1
            0 0 0 0
Input: n=3
Matrix[][]=  1 0 0
             0 0 0
             0 0 1
Output:
Matrix[][]=  1 0 1
             0 0 0
             1 0 1

Approach: 

• If the marked positions are lying on the same row, increase the row by one position and mark the positions as one.
• If the marked positions are lying on the same column, increase the column by one position and mark the next position as one.
• If the marked positions are lying on a different row or different column.
• The position of the first new position is to determine by the row of the second marked position and the position of the second new position is determined by the column of the second marked position.

Below is the implementation of the above approach:

import java.io.*;

public class Cplusplus {
    // Function to print the matrix
    static void print(int matrix1[][]) {
        for (int i = 0; i < matrix1.length; ++i) {
            for (int j = 0; j < matrix1.length; ++j) {
                System.out.print(matrix1[i][j]);
            }
            System.out.println();
        }
    }

    static void fill(int matrix[][], int length) {
        int first = 0;

        // First new position
        int x = 0;
        int y = 0;
        // Second new position
        int x1 = 0;
        int y1 = 0;
        for (int i = 0; i < length; ++i) {

            for (int j = 0; j < length; ++j) {
                // Store the position of first marked position
                if (matrix[i][j] == 1 && first == 0) {
                    x = i;
                    y = j;
                    ++first;
                }
                // Store the position of the second marked position
                else if (matrix[i][j] == 1) {
                    x1 = i;
                    y1 = j;
                }
            }
        }
        // Checking whether the column of marked position is equal
        if (y == y1) {
            // Increase the column
            matrix[x][(y + 1) % length] = 1;
            matrix[x1][(y1 + 1) % length] = 1;
        }
        // Checking whether the rows of marked position is equal
        else if (x == x1) {
            // Increase the rows
            matrix[(x + 1) % length][y] = 1;
            matrix[(x1 + 1) % length][y1] = 1;
        } else {
            // Interchanging the rows and the columns
            matrix[x][y1] = 1;
            matrix[x1][y] = 1;
        }
        // Print the matrix
        print(matrix);
    }

    public static void main(String[] args) {
        int n = 4;

        int matrix[][] = { { 1, 0, 0, 1 },
                           { 0, 0, 0, 0 },
                           { 0, 0, 0, 0 },
                           { 0, 0, 0, 0 } };
        fill(matrix, n);
    }
}

Output:

1001
1001
0000
0000

Time Complexity: O(n^2)
Space Complexity: O(n^2)