Contents
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
- Magic Square : Starting at the middle row of of the last column, we perform placements as such.
- 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.
- 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:
- Amazon OA Online Assessment 2022 Questions and Answers
- Microsoft Online Assessment 2021 Questions and Solution
