Amazon Interview Question SDE-2s
Country: United States
Is the question supposed to be picking n-1 elements from each row instead of m-1 elements? If it is m-1, there will be a case ( 3 x 100 matrix) that it's not possible to pick at least one element from each column.
The below logic is to choose n-1 elements from each row.
There are two cases for this problem.
case 1> If the maximum element of each row is not the same column position, then excluding the maximum element from each row and sum all other elements gives the result.
1 100 120
10 3 9
5 70 100
In the above example, the maximum element from each row is 120, 10, 100. They are not in the same column position. In this case, simply exclude maximum element from each row gives the result which is (1 + 100) + ( 3 + 9 ) + ( 5 + 70) .
case 2> The opposite of the 1st case is that the maximum element of each row is the same column position. In this case, choose one of the element from that column such a way that the resultant sum is minimum.
1 100 120
10 3 90
5 70 100
In this case, the maximum element of each row is in the 3rd column. The objective is to choose one value from the 3rd column. Choosing the least value from that column does not give minimal value. The reason is that picking the value in column 3 of some row needs to remove the second largest element in that row. The overall increase is in total sum is "element at column 3 minus next largest element in that row".
Let's find how much increase happens in all three cases.
Picking 1st element in column 3 --> overall increase is 120 - 100 = 20
Picking 2nd element in column 3 --> overall increase is 90 - 10 = 80
Picking 3rd element in column 3 --> overall increase is 100 - 70 = 30
Hence pick the 1st element of column 3.
like in case 1 calculate the sum of all elements by excluding the maximum element in each row ( i.e (1+100) + ( 10 + 3) + ( 5 + 70 ) = 189 ).
Now directly add the overall increase by picking the element in column 3. That is 189 + 20 = 209.
Which eventually same as ( ( 1 + 120) + (10 + 3) + (5+ 70) = 209 )
All of these can be easily done in a single traverse in a matrix.
Please comment if there are any logic issues. :)
O(m x n)
public int solve(int matrix[][]) {
int minSum = 0;
boolean isAllColumnsCovered = false;
int firstMaxColumnID = 0;
int minDiff = Integer.MAX_VALUE;
int N = matrix.length;
if (N < 1) { return 0; }
int M = matrix[0].length;
if (M < 1) { return 0; }
// 1st traversal
for (int i = 0; i < N; i++) {
int max = 0;
int max2 = 0;
int rowSum = 0;
int maxColumnID = 0;
for (int j = 0; j < M; j++)
{
if (matrix[i][j] > max)
{
if (i == 0)
{
firstMaxColumnID = j;
}
else
{
maxColumnID = j;
}
if (j == 0)
{
max = matrix[i][j];
}
else
{
max2 = max;
max = matrix[i][j];
}
}
else if (matrix[i][j] > max2)
{
max2 = matrix[i][j];
}
rowSum += matrix[i][j];
}
rowSum -= max;
minSum += rowSum;
if (!isAllColumnsCovered) {
if (i > 0 && firstMaxColumnID != maxColumnID) {
isAllColumnsCovered = true;
} else {
// Keep the min diff
if (minDiff > (max - max2)) {
minDiff = max - max2;
}
}
}
}
return minSum + (isAllColumnsCovered ? 0 : minDiff);
}
To get minimal sum for a row one needs to throw away the biggest element. So let's find for every i-th row first biggest element FB_i and (for secret reason) second biggest element SB_i.
Next we need to check if all FB_i are from the same column. If that is true then we need to substitute at least one of them. To increase the sum for the smallest amount possible find such i that FB_i - SB_i is minimal.
We also need to show that if we do this change we still use all columns. And we still do, because before the change we had selected n-1 columns m times each and one column 0 times and after the change we select n-2 columns m times each, one column m-1 times and one column one time.
public int getMinimumSum(int[][] matrix) {
if (matrix == null) {
throw new IllegalArgumentException("matrix is null");
}
int N = matrix.length;
if (N < 2) {
throw new IllegalArgumentException("Number of rows must be equal or greater than 2");
}
int M = matrix[0].length;
if (M < 1) {
throw new IllegalArgumentException("Number of columns must be equal or greater than 1");
}
int result = 0;
int minDelta = Integer.MAX_VALUE;
boolean[] visitedColumns = new boolean[M];
for (int j=0; j < visitedColumns.length; j++) {
visitedColumns[j] = false;
}
for (int i=0; i < N; i++) {
int currentMaxIndex = 0;
int previousMaxIndex = 0;
for (int j=1; j < M; j++) {
if (matrix[i][j] > matrix[i][currentMaxIndex]) {
result += matrix[i][currentMaxIndex];
visitedColumns[currentMaxIndex] = true;
previousMaxIndex = currentMaxIndex;
currentMaxIndex = j;
} else {
if (previousMaxIndex == currentMaxIndex || matrix[i][j] > matrix[i][previousMaxIndex]) {
previousMaxIndex = j;
}
result += matrix[i][j];
visitedColumns[j] = true;
}
}
int delta = matrix[i][currentMaxIndex] - matrix[i][previousMaxIndex];
if (delta < minDelta) {
minDelta = delta;
}
}
for (boolean visitedColumn : visitedColumns) {
if (!visitedColumn) {
return result + minDelta;
}
}
return result;
}
import java.util.HashMap;
public class findmin {
public static void main ( String [] args) {
int [][] source = { {0,1,2},
{2,3,2},
{4,5,6}};
int x = solve(source);
System.out.println(x);
}
public static int solve( int[][] source ) {
//Iterate thru first row, crate a structure containing row number,
//column number left off, its value, and the second largest number.
// at the end fo first row add the sum to 0;
//for subsequent rows, check if the ignored column exists in the structure.
//if it does, then update the row number and other values if column value is greater.
//TODO - if the value is same.
//if it doesnt, then ignore the structure, mark a boolean to update sum as false.
//if update sum is true then get the second largest number from the structure,
//remove it from the sum , add the column value.
//return sum.
columnignored c1 = new columnignored();
boolean wascolumnignored = true;
int sum = 0;
for (int i=0;i< source.length ; i++) {
int minSumForRow = 0;
int maxnumber = Integer.MIN_VALUE;
int maxcolumn = 0;
int secondmax = Integer.MIN_VALUE;
for( int j=0;j< source[i].length; j++) {
minSumForRow+=source[i][j];
if ( maxnumber< source[i][j]) {
secondmax = maxnumber;
maxnumber = source[i][j];
maxcolumn = j;
} else {
secondmax = Math.max(secondmax, source[i][j]);
}
}
minSumForRow=minSumForRow-maxnumber;
sum= sum +minSumForRow;
if( i==0) {
c1.createcolumn(0, maxcolumn, maxnumber, secondmax);
} else {
if( c1.columnExists(maxcolumn)) {
c1.updaterow(i, maxnumber, secondmax);
} else {
wascolumnignored = false;
}
}
}
if (wascolumnignored) {
sum=sum+c1.value-c1.secondmax;
}
return sum;
}
}
package test;
public class columnignored{
int row;
int column;
int value;
int secondmax;
public columnignored(int row, int column, int value, int secondmax) {
super();
this.row = row;
this.column = column;
this.value = value;
this.secondmax= secondmax;
}
public columnignored() {
// TODO Auto-generated constructor stub
}
public boolean columnExists(int column) {
if( this.column==column ) {
return true;
}
return false;
}
public void createcolumn(int row, int column, int value, int secondmax) {
this.row = row;
this.column = column;
this.value = value;
this.secondmax= secondmax;
}
public void updaterow (int row, int value, int secondmax ) {
if( this.value>value ) {
this.value = value;
this.row = row;
} else if ( this.value == value) {
if( this.secondmax>secondmax) {
this.value = value;
this.row = row;
this.secondmax = secondmax;
}
}
}
}
package test;
public class columnignored{
int row;
int column;
int value;
int secondmax;
public columnignored(int row, int column, int value, int secondmax) {
super();
this.row = row;
this.column = column;
this.value = value;
this.secondmax= secondmax;
}
public columnignored() {
// TODO Auto-generated constructor stub
}
public boolean columnExists(int column) {
if( this.column==column ) {
return true;
}
return false;
}
public void createcolumn(int row, int column, int value, int secondmax) {
this.row = row;
this.column = column;
this.value = value;
this.secondmax= secondmax;
}
public void updaterow (int row, int value, int secondmax ) {
if( this.value>value ) {
this.value = value;
this.row = row;
} else if ( this.value == value) {
if( this.secondmax>secondmax) {
this.value = value;
this.row = row;
this.secondmax = secondmax;
}
}
}
}
import java.util.HashMap;
public class findmin {
public static void main ( String [] args) {
int [][] source = { {0,1,2},
{2,3,2},
{4,5,6}};
int x = solve(source);
System.out.println(x);
}
public static int solve( int[][] source ) {
//Iterate thru first row, crate a structure containing row number,
//column number left off, its value, and the second largest number.
// at the end fo first row add the sum to 0;
//for subsequent rows, check if the ignored column exists in the structure.
//if it does, then update the row number and other values if column value is greater.
//TODO - if the value is same.
//if it doesnt, then ignore the structure, mark a boolean to update sum as false.
//if update sum is true then get the second largest number from the structure,
//remove it from the sum , add the column value.
//return sum.
columnignored c1 = new columnignored();
boolean wascolumnignored = true;
int sum = 0;
for (int i=0;i< source.length ; i++) {
int minSumForRow = 0;
int maxnumber = Integer.MIN_VALUE;
int maxcolumn = 0;
int secondmax = Integer.MIN_VALUE;
for( int j=0;j< source[i].length; j++) {
minSumForRow+=source[i][j];
if ( maxnumber< source[i][j]) {
secondmax = maxnumber;
maxnumber = source[i][j];
maxcolumn = j;
} else {
secondmax = Math.max(secondmax, source[i][j]);
}
}
minSumForRow=minSumForRow-maxnumber;
sum= sum +minSumForRow;
if( i==0) {
c1.createcolumn(0, maxcolumn, maxnumber, secondmax);
} else {
if( c1.columnExists(maxcolumn)) {
c1.updaterow(i, maxnumber, secondmax);
} else {
wascolumnignored = false;
}
}
}
if (wascolumnignored) {
sum=sum+c1.value-c1.secondmax;
}
return sum;
}
}
O(m x n) solution
- Anoneemus July 23, 2019public int solve(int matrix[][]) { int minSum = 0; boolean isAllColumnsCovered = false; int firstMaxColumnID = 0; int minDiff = Integer.MAX_VALUE; int N = matrix.length; if (N < 1) { return 0; } int M = matrix[0].length; if (M < 1) { return 0; } // 1st traversal for (int i = 0; i < N; i++) { int max = 0; int max2 = 0; int rowSum = 0; int maxColumnID = 0; for (int j = 0; j < M; j++) { if (matrix[i][j] > max) { if (i == 0) { firstMaxColumnID = j; } else { maxColumnID = j; } if (j == 0) { max = matrix[i][j]; } else { max2 = max; max = matrix[i][j]; } } else if (matrix[i][j] > max2) { max2 = matrix[i][j]; } rowSum += matrix[i][j]; } rowSum -= max; minSum += rowSum; if (!isAllColumnsCovered) { if (i > 0 && firstMaxColumnID != maxColumnID) { isAllColumnsCovered = true; } else { // Keep the min diff if (minDiff > (max - max2)) { minDiff = max - max2; } } } } return minSum + (isAllColumnsCovered ? 0 : minDiff); }