Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Yes, this is another way of solving it. You should just say it's O(MN) -- that's still correct and is simpler.
As a example,
For input
1 2 1 3 4
2 1 3 1 4
1 5 6 7 8
1 2 1 2 1
Sum matrix is
1 3 4 7 11
3 6 10 14 22
4 12 22 33 49
5 21 26 39 55
if k=2, consider a matrix starts at location 2, 3
Then input value is
3,1
6,7
=17.
Corresponding sum matrix calculation is 33+3-12-7= 37-19 =17
Which is actually
=a[i+k-1][j+k-1]+a[i-1][j-1]-a[i+k-1][j]-a[i][j+k-1]
Please correct me if i'm wrong. But the answer of above should be 18. Considering the matrix 7,8
2,1
first add the k columns of each row like in robinkarp resulting in (m-k+1)*n;
now add the k rows of each column resulting in (m-k+1)(n-k+1);
find the highest element indx;
that will be the starting index of k*k matrix with highest sum O(m*n)
// This code has the order of O(n*m + (n-k)*(m-k)). But an extra array is needed.
public int maxMatSum(int[][] mat, int k) {
int res = 0;
int[][] num = new int[mat.length][mat[0].length];
int sum = 0;
for (int i = 0; i < mat.length; i++) {
sum += mat[i][0];
num[i][0] = sum;
}
sum = 0;
for (int j = 0; j < mat[0].length; j++) {
sum += mat[0][j];
num[0][j] = sum;
}
for (int m = 1; m < mat.length; m++) {
for (int n = 1; n < mat[0].length; n++) {
num[m][n] = mat[m][n] + num[m-1][n] + num[m][n-1] - num[m-1][n-1];
}
}
for (int m = 0; m < num.length - k; m++) {
for (int n = 0; n < num[0].length - k; n++) {
if(res < num[m+k][n+k] + num[m][n] - num[m+k][n] - num[m][n+k]) {
res = num[m+k][n+k] + num[m][n] - num[m+k][n] - num[m][n+k];
}
}
}
return res;
}
(Edited to reflect that there are 2 parameters, M and N, and the input is not just N*N).
We can do this in O(MN). High level outline:
1. Use a sliding window approach to create an auxiliary "sum matrix" where sum_matrix[i][j] = sum (input_matrix[i][j] + input_matrix[i][j + 1] + ... input_matrix [i][j+ k - 1]. By "sliding window", I mean that we should exploit the fact that sum_matrix[i][j] = sum_matrix[i][j - 1] + input_matrix [i][j+ k - 1] - input_matrix[i][j-1]. This reuse of previous results will allow the computation of the sum matrix in O(MN) time. (The sum matrix is of size m * (n-k), to avoid going out of bounds)
2. Now, the sum_matrix represents sums of k consecutive columns in the same row. So the remaining problem now is to find where in sum_matrix we get a maximum sum if we sum k consecutive rows in the same column. This can be done by a similar sliding window approach, again in O(MN) time.
Now we're done. The algorithm can be designed to just return the max sum or also keep track of where it was found. Since both steps above are O(MN), the algo is O(MN) overall. I should also mention that O(MN) is optimal because that is how much data we have, and we must look at all the data at least once.
How is step 2 O(M*N), i think it should be O(M*N*M) ( we have to consider all pair of rows to use sliding window approach )
Since the sum_array already has k-consecutive column sums, checking k consecutive rows in the same column of sum_matrix is checking k * k squares in the original input. You consider the columns one at a time in step 2, keeping track of where you saw the maximum as you go from column to column.
It is O(MN) as promised.
This problem can be solved by using dynamic programming, Let A be the matrix of size mXn , and we need to find maximum sum sub matrix,
Let us define S(i,j) = sum of elements in row i from column j to j+k-1 ,
we first calculate this S(i,j) for i from 1 to m and j from 1 to n-k+1
now we have vector sums for each row
Then we come to sub matrix sum which is sum of k row vectors
Let KSum(i,j) = sum of elements in sub matrix of size kXk with top left corner as A[i,j]
Then we can write
KSum(i,j) = KSum(i-1,j) - S(i-1,j) + S(i+k-1,j)
i<= i <= m-k+1
1<= j <= n-k+1
I think dynamic programming is a little excessive here. Dynamic programming is most appropriate when you have subproblems whose solutions are re-used multiple times. Here there's no such thing. KSum(i,j) is only used in evaluating KSum(i+1, j).
You're better off just evaluating your recurrence iteratively. Of course you never say in your video how you intended to evaluate the recursion, so maybe your plan was to decompose it into iteration (and also not memorize solutions to subproblems, since that would also be a waste).
What is the complexity going to be? As far as i can see this is going to be expensive compared to first solution. When you i initialize the Sum array, its going to take O((m-k)*(n-k)) time to initialize it..
here we are just moving the matrix
first from 0,0 to k-1,k-1
then calculating the sum
we are having two more sums that are leftcolumnsum and top row sum
when we move the column
new sum = oldsum - leftcolumnsum+ new column(sum)
when we move by one row
new sum = oldsum - toprowsum + newrowaddedsum;
#include<iostream>
#include<stdlib.h>
using namespace std;
int main(){
int m=10;
int n=10;
int** array = (int**)malloc(sizeof(int*)*m);
// allocating the space to the array
for(int i=0;i<m;i++){
array[i] = (int*)malloc(sizeof(int)*n);
}
// initializing the array
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cin>>array[i][j];
}
}
int topRowSum, leftColumnSum;
int k = 3;
// printing the array
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cout<<array[i][j]<<" ";
}
cout<<endl;
}
// we are checking for 3*3 matrix having the largest sum
int baseColumnSum;
int baseRowSum;
int baseSum;
int baseRow;
int baseColumn;
baseRow = 0;
baseColumn = 0;
baseSum = 0;
topRowSum = 0;
leftColumnSum = 0;
//initializing the base sum
for(int i=0;i<k;i++){
for(int j=0;j<k;j++){
baseSum += array[i][j];
}
}
baseColumnSum = baseSum;
baseRowSum = baseSum;
// initializing the top row sum and the left column sum
for(int i=0;i<k;i++){
topRowSum += array[0][i];
leftColumnSum += array[i][0];
}
// i,j corrospondes to the starting index of the square matrix
cout<<baseRowSum<<endl;
for(int i=0;i<(m-k);i++){
for(int j=1;j<=(n-k);j++){
baseColumnSum = baseColumnSum - leftColumnSum;
leftColumnSum = 0;
for(int m=0;m<k;m++){
baseColumnSum += array[i+m][k+j-1];
leftColumnSum += array[i+m][j];
}
if(baseColumnSum > baseSum){ //update the base values
baseSum = baseColumnSum;
baseRow = i;
baseColumn = j;
}
}// checking for a particular row and the all other columns
baseRowSum = baseRowSum - topRowSum;
topRowSum = 0;
for(int m=0;m<k;m++){
baseRowSum += array[k+i][m];
topRowSum += array[i+1][m];
}
cout<<baseRowSum<<endl;
if(baseRowSum > baseSum){
baseSum = baseRowSum;
baseRow = i+1;
baseColumn =0;
}
baseColumnSum = baseRowSum;
leftColumnSum = 0;
for(int m=0;m<k;m++){
leftColumnSum += array[i+1+m][0];
}
}
cout<<"maximum sum is"<<baseSum<<endl;
cout<<"i = "<<baseRow<<" j = "<<baseColumn<<endl;
return 0;
}
This code is working correct. Code is in C#. To verify just run it.
namespace MaxSumKxKMatrixInNxNMatrix
{
class Program
{
static void Main(string[] args)
{
int[,] abc= new int[5,6]{{6,4,7,2,-9,12} , {8, -2,5,3,1,9}, {9,3,1,8,5, -2}, {-2,4,6,8,10,12} , {1,3,5,7,-9,11} };
int[] ans = MaxKxKMatrix(abc, 5, 6, 3);
foreach (int item in ans)
{
Console.WriteLine(item);
}
Console.ReadLine();
}
static int[] MaxKxKMatrix(int[,] matrix, int n, int m, int k)
{
int[] max_mat_index = new int[3];
int max_sum = 0;
for (int i = 0; i <= n-k; i++)
{
for (int x = 0; x <= m - k; x++)
{
int row=0, col=0;
int this_matrix_sum = 0;
for (int j = i; j <= i+ k-1; j++)
{
for (int y = x; y <= x+k-1; y++)
{
this_matrix_sum = this_matrix_sum + matrix[j, y];
col = y;
}
row = j;
}
if (this_matrix_sum > max_sum)
{
max_sum = this_matrix_sum;
max_mat_index[0] = row;
max_mat_index[1] = col;
max_mat_index[2] = this_matrix_sum;
}
}
}
max_mat_index[0] = max_mat_index[0] - 2;
max_mat_index[1] = max_mat_index[1] - 2;
return max_mat_index;
}
}
}
def findMaxKxK( matrix, k ):
print( matrix )
if k == 0 or len( matrix ) < k or len( matrix[0] ) < k :
print( "Invalid k!" )
return None
m1_columns = len( matrix[0] ) - k + 1
m1 = []
for i in range( len( matrix ) ) :
m1.append( [0]*m1_columns )
for i in range( len( matrix ) ) :
for j in range( m1_columns ):
m1[i][j] = sum( matrix[i][j:j+k] )
m2 = []
m2_rows = len( m1 ) - k + 1
for i in range( m2_rows ) :
m2.append( [0]*m1_columns )
for i in range( m2_rows ) :
for j in range( m1_columns ):
add = 0
for iter in range( k ) :
add = add + m1[i+iter][j]
m2[i][j] = add
i_max = 0
j_max = 0
max = 0
for i in range( m2_rows ):
for j in range( m1_columns ):
if m2[i][j] > max:
max = m2[i][j]
i_max = i
j_max = j
max_matrix = []
for i in range( k ) :
max_matrix.append( [0]*k )
for i in range( k ) :
for j in range( k ) :
max_matrix[i][j] = matrix[i_max+i][j_max+j]
print( str(k) + "_max = ", max_matrix )
return max_matrix
if __name__ == "__main__":
findMaxKxK( [ [3,2,1,0], [5,6,4,0], [1,2,3,0] ], 2 )
findMaxKxK( [ [3,2,1,0], [5,6,4,0], [1,2,3,0] ], 1 )
findMaxKxK( [ [3,2,1,0], [5,6,4,0], [1,2,3,0], [1,2,3,0] ], 4 )
findMaxKxK( [ [3,2,1,0], [5,6,4,0], [1,2,3,0], [1,2,3,0] ], 2 )
findMaxKxK( [ [3,2,1,0], [5,6,4,0], [1,2,3,0], [1,2,3,0] ], 0 )
Traverse the matrix and keep inserting all elements of k*k matrix in an array. This traversal will be O(m*n). Now traverse the array, adding k*k elements and calculating max sum for those. For ex:
Matrix:
1 2 3
4 5 6
7 8 9
Array:
1,2,4,5,2,3,5,6,4,5,7,8,5,6,8,9
Sum of 1+2+4+5=12 (max_so_far)
next sum of 2+3+5+6=16(now max_so_far)
We can do it using O[ mn ] space complexity & O[ (m-k)*(n-k) + mn] time complexity.
- Navin August 12, 2012we can create a sum matrix of dimension (m x n) .
matrix [i][j] stores the sum of elements in input matrix of rows : 1 to i and cols: 1 to j.
Now to get the sum of elements in matrix in rows : i1 to i2 and cols : j1 to j2 ,
we can get this sum in O(1) time.
sum{ in[i1 to i2][j1 to j2] } = sum_Matrix[i2][j2] - sum_Matrix[i1-1][j2] - sum_Matrix[i2][j1-1] +sum_Matrix[i1 - 1][ j1 -1]
Now we can iterate in the Sum_Matrix to get the maximum amon all the k*k matrix elements sum.
This can be done in O( m-k * n-k)