Amazon Interview Question SDE1s
Country: United States
Interview Type: In-Person
had a naive solution...
Step 1: first go over row by row, finding the max and min both. put them into separate arrays, would take O(n^2)
Step 2: sort both max array and min array, in O(n*lgn) time
Step 3: start from the biggest value in max array. subtract each one from min array from it until that c > a and d > b holds. then move down the max array by one, and repeat the same thing. would take O(n^2)
Step 4: step 3 would give a collection of n elements, find the biggest one in O(n).
I know it's complicated but does work in O(n^2) time.
how about:
1. create two dimensional array arrMax(x,y) and var res to store the result
2. for( x=n-1;x>0;x--) for (y=n-1;y>0;y--)
2.1 var maximumForY=if (y==n-1) then A(x,y) else max(arrMax(x,y+1),A(x,y))
2.2 arrMax(x,y)=max(maximumForY, (if(x==n-1) then A(x,y) else max(arrMax(x+1,y),A(x,y))))
2.3 if(x!=n-1 and y!=n-1) then (if((x==n-2 and y=n-2) or A(x,y)-arrMax(x+1,y+1)>res) then res=A(x,y)-arrMax(x+1,y+1)
3. return res
this solution? I haven't tried to code clearly, but the overall idea is somehow like this
Sorry that just read Yang's reply. Mine is basically same as Yang's but use the same loop to calculate the value of maximum value A(c,d) - A(a,b) only.
Sort the matrix elements. store these with the indexes(linear or 2D). complexity - nlogn. search the elements for max diff starting with max - min from the sorted array. solution is the for which indexes c,d > a,b. worst case complexity n^2. for most cases the overall complexity would be better than n^2
It seems to me that it's more or less like: for a one dimensional array A[n], find maximum value A[a] - A[b], where a < b in O(n) time.
I think the array version can be solved by DP through distinguishing the ascension and descension of the values of elements in one-traversing, so does the matrix.
What I understood from this question is as follows:
For a given nxn matrix(array), the value A[i][j] represents value in ith row and jth column. Now, c and d (from A(c,d)) are to considered in such a way that their values should be greater than a and b (from A(a,b)) respectively. So, we can conclude that values of a and b cannot be equal to n( n-1 since arrays are zero indexed). Also, the values of c and d should be at least greater than a and b respectively by 1. So, considering these facts, I created following logic:
public static void max(int [][]arr)
{
int max = Integer.MIN_VALUE;
int n = arr.length;
int temp=0;
for(int a=0; a<(n-1); a++)
{
for(int b=0; b<(n-1); b++)
{
for(int c=a+1; c<n;c++)
{
for(int d=b+1; d<n;d++)
{
//System.out.println(a+" "+b+" "+c+" "+d+": value:"+(arr[c][d]-arr[a][b]));
if(max<(arr[c][d]-arr[a][b]))
max = arr[c][d]-arr[a][b];
}
}
}
}
System.out.println("Max:"+max);
}
Sample output for your reference:
Matrix input:
14 17 65
79 27 22
71 62 16
0 0 1 1: value:13
0 0 1 2: value:8
0 0 2 1: value:48
0 0 2 2: value:2
0 1 1 2: value:5
0 1 2 2: value:-1
1 0 2 1: value:-17
1 0 2 2: value:-63
1 1 2 2: value:-11
Max:48
Please suggest me if this code can be improvised further. Though it may seem that the complexity is worse than O(n^2), these iterations would only pic valid combinations only.
In the above since u already have a comparision between 0011 and 1122, I think you can skip the 0022 comparision. If 1122 is negative then its not the max if positive then add the difference to 0011.
Similarly you can skip many comparisions.
<?php
//$num = array(3,8,5,9,7,1,2,4,6);
$num = array (
array (8,5,2),
array (1,4,7),
array (3,9,6)
);
$n = count($num);
$result = $num[1][1] - $num[0][0];
$min_value = $num[0][0];
//Complexity O(n^2)
for($i = 0; $i < $n-1; $i++) {
for($j = 0; $j < $n-1; $j++) {
$min_value = min($min_value, $num[$i][$j]);
$result = max($result, $num[$i+1][$j+1] - $min_value);
printf("i:$i j:$j min_value: $min_value result:$result");
}
}
var_dump($result);
?>
<?php
$m = array
(
array(9,8,1,6),
array(5,2,2,3),
array(7,4,16,11),
array(6,1,8,15)
);
$n = count($m);
$max_diff = $m[1][1] - $m[0][0];
for($i = 0; $i < $n-1; $i ++) {
for($j = 0; $j < $n-1; $j ++) {
if ($i == 0 && $j == 0) {
$min_value = $m [0] [0];
}
elseif ($i == 0 && $j > 0) {
$min_value = min ($min_value, $m[0][$j]);
}
elseif ($j == 0 && $i > 0) {
$min_value = min ($min_value, $m[$j][0]);
} else {
$min_value = min ( $m[$i][$j], $m [$i-1][$j], $m[$i][$j - 1] );
}
$max_diff = max ($max_diff, $m[$i+1][$j+1] - $min_value );
echo "i:$i j:$j min_value:$min_value max_diff:$max_diff" . "<br>";
}
}
int findMaxDiff(vector<vector<int>> M)
{
int row = M.size();
if(row == 0)
return INT_MIN;
int col = M[0].size();
if(row == 1 || col == 1)
return INT_MIN;
int A[row][col];
int retV = INT_MIN;
for(int i=0; i<row; i++)
for(int j=0; j<col; j++)
{
A[i][j] = M[i][j];
if(i>0)
A[i][j] = min(A[i][j], A[i-1][j]);
if(j>0)
A[i][j] = min(A[i][j], A[i][j-1]);
if(i>0 && j>0)
retV = max(retV, M[i][j] - A[i-1][j-1]);
}
return retV;
}
If we convert the matrix into a vector then the maximum can be found the value in O(n^2). Here is the code
double MaxElement(std::vector<std::vector<double>> M)
{
int n1=M.size();
int n2=M.at(0).size();
std::vector<double> vec;
for (int i=0; i<n1 ;i++)
{
for(int j=0; j<n2; j++)
{
vec.push_back(M[i][j]);
}
}
int vecSize=vec.size();
double max=vec[n2+1]-vec[0];
int j=0;
for (int i=0; i<vecSize ; i++)
{
j=i+n2+1;
while(j<vecSize)
{
if (vec[j]-vec[i]>max)
{
max=vec[j]-vec[i];
}
if ((j+1)%n2>0)
{
j++;
}
else
{
j+=n2+1;
}
}
}
return max;
}
The following is in C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace MatrixMaxElement
{
class Program
{
static void Main(string[] args)
{
int[,] matrix = new int[3, 3];
FillArray(matrix);
Display(matrix);
Console.WriteLine(string.Format("\n\nMax Value is {0}",FindMax(matrix)));
Console.Read();
}
private static void FillArray(int[,] matrix)
{
for (int i = 0; i <= matrix.GetUpperBound(0); i++)
{
for (int j = 0; j <= matrix.GetUpperBound(1); j++)
{
matrix[i,j] = i + j;
}
}
}
private static void Display(int[,] matrix)
{
for (int i = 0; i <= matrix.GetUpperBound(0); i++)
{
Console.WriteLine("\n");
for (int j = 0; j <= matrix.GetUpperBound(1); j++)
{
Console.Write(matrix[i, j]);
Console.Write("\t");
}
}
}
private static int FindMax(int[,] matrix)
{
int max = 0;
for (int i = 0; i <= matrix.GetUpperBound(0); i++)
{
for (int j = 0; j <= matrix.GetUpperBound(1); j++)
{
if (i == 2 || j == 2) continue;
int a = i;
int b = j;
int c = a + 1;
int d = b + 1;
var difference = matrix[c,d] - matrix[a,b];
if (difference > max)
max = difference;
}
}
return max;
}
}
}
int findmax(int a,int b,int R,int C){
int max=INT_MIN,j;
for(int i=a;i<R;i++){
max=maxm(max,mat[i][b]);
mat[i][b]=max;
}
max=INT_MIN;
for(int i=b;i<C;i++){
max=maxm(max,mat[a][i]);
mat[a][i]=max;
}
for(int i=a+1;i<R;i++)
for(int j=b+1;j<C;j++){
mat[i][j]=maxm(maxm(mat[i-1][j],mat[i][j-1]),mat[i][j]);
}
return mat[R-1][C-1];
}
use DP no need to even allocate extra space manipulate that matrix
ans =max-mat[a][b];
// if any prolem with this code plz let me know
int findmax(int a,int b,int R,int C){
int max=INT_MIN,j;
for(int i=a;i<R;i++){
max=maxm(max,mat[i][b]);
mat[i][b]=max;
}
max=INT_MIN;
for(int i=b;i<C;i++){
max=maxm(max,mat[a][i]);
mat[a][i]=max;
}
for(int i=a+1;i<R;i++)
for(int j=b+1;j<C;j++){
mat[i][j]=maxm(maxm(mat[i-1][j],mat[i][j-1]),mat[i][j]);
}
return mat[R-1][C-1];
}
a=a+1;
b=b+1;// as mentioned no extra space manipulate that matrix
int findmax(int a,int b,int R,int C){
int max=INT_MIN,j;
for(int i=a;i<R;i++){
max=maxm(max,mat[i][b]);
mat[i][b]=max;
}
max=INT_MIN;
for(int i=b;i<C;i++){
max=maxm(max,mat[a][i]);
mat[a][i]=max;
}
for(int i=a+1;i<R;i++)
for(int j=b+1;j<C;j++){
mat[i][j]=maxm(maxm(mat[i-1][j],mat[i][j-1]),mat[i][j]);
}
return mat[R-1][C-1];
}
//Considering 'n' a global variable representing size of matrix
//Considering matrix to be in the form of double dimension array of size (nXn )
public int maxDiffInMatrix(int arr[][]){
int max=arr[1][1];
int min=arr[0][0];
int a=0,b=0,c=1,d=1;
//Finding maximum arr[c][d].....complexity n^2
for(int i=1;i<n;i++){
for(int j=1;j<n;j++){
if(arr[i][j]>max){
max=arr[i][j];
c=i;
d=j;
}
}
}
//Finding minimum arr[a][b]........complexity n^2
for(int m=0;m<c;m++){
for(int n=0;n<d;n++){
if(arr[m][n]<min){
min=arr[m][n];
a=m;
b=n;
}
}
}
//Returning desired value.....final complexity: (n^2)+(n^2)= O(n^2)
return (arr[c][d]-arr[a][b]);
}
public class MaxMinArray {
public static void calc(int[][] arr, int n, int c, int d) {
if(n<2 || c<1 || d<1)
return;
int[][] maxjperi = new int[n][n];
int[][] minjperi = new int[n][n];
for(int i = 0; i<n; i++) {
maxjperi[i][0] = 0;
for(int j=1; j<n; j++) {
maxjperi[i][j] = arr[i][j] >= arr[i][maxjperi[i][j-1]] ? j : maxjperi[i][j-1];
minjperi[i][j] = arr[i][j] <= arr[i][minjperi[i][j-1]] ? j : minjperi[i][j-1];
}
}
int iwithmax = 0;
int iwithmin = 0;
for(int i = 1; i < c; i++) {
iwithmax = arr[i][maxjperi[i][d-1]] >= arr[iwithmax][maxjperi[iwithmax][d-1]] ? i : iwithmax;
iwithmin = arr[i][minjperi[i][d-1]] <= arr[iwithmin][minjperi[iwithmin][d-1]] ? i : iwithmin;
}
if(arr[c][d] - arr[iwithmax][maxjperi[iwithmax][d-1]] > arr[c][d] - +arr[iwithmin][minjperi[iwithmin][d-1]]) {
System.out.println("index are "+iwithmax+" and "+maxjperi[iwithmax][d-1]);
} else {
System.out.println("index are "+iwithmin+" and "+minjperi[iwithmin][d-1]);
}
}
}
#!/usr/bin/python
def matrix_min(mat):
a = len(mat)
max_m = [[0 for i in range(0,a)]for j in range(0,a)]
# construct a matrix which save the maximum value of the
# submatrix mat[i][j] to mat[a-1][a-1]
for i in reversed(range(0,a)):
for j in reversed(range(0,a)):
if i == a-1 and j == a-1:
max_m[i][j] = mat[i][j]
elif i == a-1 and j < a-1:
max_m[i][j] = max(mat[i][j], max_m[i][j+1])
elif j == a-1 and i < a-1:
max_m[i][j] = max(mat[i][j],max_m[i+1][j])
else:
max_m[i][j] = max(mat[i][j],max_m[i][j+1],max_m[i+1][j])
max_value = 0
for i in range(0,a-1):
for j in range(0,a-1):
# compare the current value in mat with the maximum
# value in the summatrix max_x[i+1][j+1] to max_x[a-1][a-1]
max_value = max(max_value, max_m[i+1][j+1]-mat[i][j])
print max_value
mat = [[3,7,9,2],[6,11,5,8],[1,20,4,7],[3,21,5,18]]
matrix_min(mat)
#!/usr/bin/python
def matrix_min(mat):
a = len(mat)
max_m = [[0 for i in range(0,a)]for j in range(0,a)]
# construct a matrix which save the maximum value of the
# submatrix mat[i][j] to mat[a-1][a-1]
for i in reversed(range(0,a)):
for j in reversed(range(0,a)):
if i == a-1 and j == a-1:
max_m[i][j] = mat[i][j]
elif i == a-1 and j < a-1:
max_m[i][j] = max(mat[i][j], max_m[i][j+1])
elif j == a-1 and i < a-1:
max_m[i][j] = max(mat[i][j],max_m[i+1][j])
else:
max_m[i][j] = max(mat[i][j],max_m[i][j+1],max_m[i+1][j])
max_value = 0
for i in range(0,a-1):
for j in range(0,a-1):
# compare the current value in mat with the maximum
# value in the summatrix max_x[i+1][j+1] to max_x[a-1][a-1]
max_value = max(max_value, max_m[i+1][j+1]-mat[i][j])
print max_value
mat = [[3,7,9,2],[6,11,5,8],[1,20,4,7],[3,21,5,18]]
matrix_min(mat)
Program want diff b/w max and min value off matrix with given constraint (c>a and d>b). select randomly min and max in matrix such that c>a and d >b. In a loop find min and max in matrix with conditions and output difference,
- kg October 07, 2013let min=a[0][0],max[n-1][n-1] and a=0,b=0,c=n-1,d=n-1
for(i=0;i<n;i++)
{ for (j=0;j<n;j++)
{ if(min > a[i][j] && i<c && j <d)
{min=a[i][j];a=i;b=j;}
else if(max<a[i][j] && i>a && j>b)
{max=a[i][j];c=i;d=j;}
}
}