Fill 2D Array Google OA 2023 Solution

Fill 2D Array Google OA 2023 Solution

Given a N x N matrix. Fill the integers from 1 to n*n to this matrix that makes the sum of each row, each column and the two diagonals equal.

Example 1:

Input: n = 2
Output: null
Explanation: We need to fill [1, 2, 3, 4] into a 2x2 matrix, which is not possible so return null.

Example 2:

Input: n = 3
Output:
[[8, 3, 4],
 [1, 5, 9],
 [6, 7, 2]]
Explanation: We need to fill [1, 2, 3... 9] into a 3x3 matrix. This is one way to do it
Each row [8, 3, 4] [1, 5, 9] [6, 7, 2] sum is 15.
Each column [8, 1, 6] [3, 5, 7] [4, 9, 2] sum is 15.
The two diagonals [8, 5, 2] [4, 5, 6] sum is 15.
int[][] fillMatrix(int n) {}

SOLUTION

Program: Fill 2D Array Google OA Solution in Python

  1. Magic Square : Starting at the middle row of of the last column, we perform placements as such.
  2. Go up and right 1 cell (with wrap-around). If placement has already been done at the cell, revert this movement. Go left 1 cell instead.
  3. Repeat Step 2 until we go OOB (return None) or finish placing up till n^2
from typing import List

def fill_matrix(n: int) -> List[List[int]]:
    """
    Time  : O()
    Space : O(),
    """
    # EDGE CASE
    if n == 1:
        return [[1]]

    # CREATE THE GRID
    grid = [[None for _ in range(n)] for _ in range(n)]

    # PLACEMENT ALWAYS BEGINS WITH 1 AT [n//2, n - 1]
    grid[n // 2][n - 1] = 1

    # KEEP TRACK OF VISITED CELLS
    i, j = n // 2, n - 1

    # LOOP TILL WE'VE FILLED ALL
    for num in range(2, n ** 2 + 1):
        try:
            i, j = getNextCoord(i, j, n, grid)
        except ValueError:
            return None
        grid[i][j] = num

    # for row in grid:
    #     print(row)
    return grid


def getNextCoord(i: int, j: int, n: int, grid: List[List[int]]) -> (int, int):
    # GO UP AND RIGHT, WITH WRAP-AROUND
    ni = (i - 1) % n
    nj = (j + 1) % n

    # CHECK IF WE'VE VISITED THIS ALREADY
    if grid[ni][nj] is not None:
        # GO LEFT
        ni = i
        nj = j - 1

    # CHECK IF OOB
    if nj < 0:
        raise ValueError(f"Cannot form magic square of size {n}")

    return ni, nj


if __name__ == "__main__":
    print(fill_matrix(1) == [[1]])
    print(fill_matrix(2) is None)
    print(fill_matrix(3) == [[2, 7, 6],
                             [9, 5, 1],
                             [4, 3, 8]])
    print(fill_matrix(4) is None)
    print(fill_matrix(5) == [[9, 3, 22, 16, 15],
                             [2, 21, 20, 14, 8],
                             [25, 19, 13, 7, 1],
                             [18, 12, 6, 5, 24],
                             [11, 10, 4, 23, 17]])
    print(fill_matrix(6) is None)
    print(fill_matrix(7) == [[20, 12, 4, 45, 37, 29, 28],
                             [11, 3, 44, 36, 35, 27, 19],
                             [2, 43, 42, 34, 26, 18, 10],
                             [49, 41, 33, 25, 17, 9, 1],
                             [40, 32, 24, 16, 8, 7, 48],
                             [31, 23, 15, 14, 6, 47, 39],
                             [22, 21, 13, 5, 46, 38, 30]])

Back Tracking Method

Program: Fill 2D Array Google OA Solution in Java

    //Backtracking Algorithm
    int[][] fillMatrix(int n) {
		boolean[] picked = new boolean[n*n+1];
		int[][] mat = new int[n][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				mat[i][j] = -1;
			}
		}
		boolean found = fillMatrixHelper(n, mat, picked, 0, 0);
		if(found) {
			return mat;
		}
		else {
			return null;
		}
	}

	public boolean fillMatrixHelper(int n, int[][] mat, boolean[] picked, int ri, int ci) {
		if(ci==n) {
			ci = 0;
			ri++;
		}
		if(ri==n) {
			boolean check = checkIfValid(n, mat);
			return check;
		}
		for(int i=1;i<=n*n;i++) {
			if(!picked[i]) {
				picked[i] = true;
				mat[ri][ci] = i;
				boolean check = fillMatrixHelper(n, mat, picked, ri, ci+1);
				if(check) {
					return true;
				}
				mat[ri][ci] = -1;
				picked[i] = false;
			}
		}
		return false;
	}

	public boolean checkIfValid(int n, int[][] mat) {
		int sum = 0;
		for(int j=0;j<n;j++) {
			sum += mat[0][j];
		}
	        for(int i=1;i<n;i++) {
			int temp = 0;
			for(int j=0;j<n;j++) {
				temp += mat[i][j];
			}
			if(temp!=sum) {
				return false;
			}
		}
		for(int j=0;j<n;j++) {
			int temp = 0;
			for(int i=0;i<n;i++) {
				temp += mat[i][j];
			}
			if(temp!=sum) {
				return false;
			}
		}
		int temp;
		temp = 0;
		for(int i=0,j=0;i<n && j<n;i++,j++) {
			temp += mat[i][j];
		}
		if(temp!=sum) {
			return false;
		}
		temp = 0;
		for(int i=0,j=n-1;i<n && j>=0;i++,j--) {
			temp += mat[i][j];
		}
		if(temp!=sum) {
			return false;
		}
		return true;
	}

Program: Fill 2D Array Google OA Solution in Python

The key idea is that the sum must be checked if the position which is being filled is the last in row/column/diagonal.

def myrow(pos, n):
    # Returns a list of indices of all elements in the row containing position
    output = []
    pos = pos % n
    return list(range(pos,n**2,n))
    
def mycol(pos, n):
    # Returns a list of indices of all elements in the column containing position
    output = []
    pos = (pos // n)*n
    return list(range(pos, pos +n))

def top_diagonal(n):
    # Returns a list of indices of all elements in the top left to bottom right diagonal
    return [i*n + i for i in range(n)]

def other_diagonal(n):
    # Returns a list of indices of all elements in top right to bottom left diagonal
    return [i*n + n - i - 1 for i in range(n)]

def issafe(board, pos, x, n):
    # Returns True if x can be placed on the board
    global global_sum
    if(board[pos] is not None):
        return False
    if(x in board):
        return False
    if(pos == myrow(pos, n)[-1]):
        if(x + sum([board[r] for r in myrow(pos, n)[:-1]]) != global_sum):
            return False
    if(pos == mycol(pos, n)[-1]):
        if(x + sum([board[r] for r in mycol(pos, n)[:-1]]) != global_sum):
            return False
    if(pos == top_diagonal(n)[-1]):
        if(x + sum([board[r] for r in top_diagonal(n)[:-1]]) != global_sum):
            return False
    if(pos == other_diagonal(n)[-1]):
        if(x + sum([board[r] for r in other_diagonal(n)[:-1]]) != global_sum):
            return False
    return True

def fill(board, pos, n):
    #Backtracking through the board
    if(pos >= n**2):
        return True
    for num in range(1, n**2+1):
        if(issafe(board, pos, num, n)):
            board[pos] = num
            if(fill(board, pos+1, n)):
                return True
            else:
                board[pos] = None
    return False

n = 3
global_sum = n*(n**2+1)/2
board = [None]*(n**2)
val = fill(board, 0, n)
output = []
for i in range(n):
    output.append(board[i*n:i*n+n])
print(output)
print(val)

Related:

Google OA 2023 Questions

Leave a Comment

seventeen + twelve =