public class Exercise10 {
// private final Integer[] HEIGHT = {1,8,6,2,5,4,8,3,7};
// private final Integer[] HEIGHT = {1,2,4,7,9};
// private final Integer[] HEIGHT = {6, 2, 0, 20, 1};
// private final Integer[] HEIGHT = {1, 1, 10, 9, 1, 1};
// private final Integer[] HEIGHT = {14, 8, 5, 3, 3, 2, 1};
private final Integer[] HEIGHT = {100, 1, 102};
private int getArea(int i, int j) {
return Math.abs(i - j) * Math.min(HEIGHT[i], HEIGHT[j]);
}
private void solveBruteForce() {
int indexI = 0, indexJ = 0;
int maxArea = 0;
for (int i=0; i<HEIGHT.length - 1; i++) {
for (int j=1; j<HEIGHT.length; j++) {
int area = getArea(i, j);
if (area > maxArea) {
maxArea = area;
indexI = i;
indexJ = j;
}
}
}
System.out.println("[Brut] maxArea = " + maxArea + ", i = " + indexI + ", j = " + indexJ);
// O(n^2)
}
private void solveEasy() {
// sort lines by y desc, x desc;
// find first common element going from i=0 and from j=0 towards the rest of the arrays;
// for that element find its best pair;
List<Integer> unsortedArray = Arrays.asList(HEIGHT);
List<Integer> sortedArray = Arrays.asList(HEIGHT.clone());
sortedArray.sort((i1, i2) -> i2 - i1 != 0 ? i2 - i1 : unsortedArray.indexOf(i2) - unsortedArray.indexOf(i1));
int indexElement = 0;
Set<String> keys = new HashSet<>();
for (int i=0; i<HEIGHT.length; i++) {
String key1 = i + "," + unsortedArray.get(i);
String key2 = unsortedArray.indexOf(sortedArray.get(i)) + "," + sortedArray.get(i);
if (keys.contains(key1) || key1.equals(key2)) {
indexElement = i;
break;
}
if (keys.contains(key2)) {
indexElement = unsortedArray.indexOf(sortedArray.get(i));
break;
}
keys.add(key1);
keys.add(key2);
}
int maxArea = 0;
int secondIndex = 0;
for (int i=0; i<HEIGHT.length; i++) {
int area = getArea(indexElement, i);
if (area > maxArea) {
maxArea = area;
secondIndex = i;
}
}
System.out.println("[Easy] maxArea = " + maxArea + ", i = " + indexElement + ", j = " + secondIndex);
// O(n log n) due to sorting
}
public static void main(String args[]) {
new Exercise10().solveBruteForce();
new Exercise10().solveEasy();
}
}
public class Exercise11 {
private final Integer[][] MATRIX = {{1,1,1},{1,0,1},{1,1,1}}; // 1 <= m, n <= 200
// private final Integer[][] MATRIX = {{1,0,1,1},{1,1,1,1},{1,1,1,0}};
// private final Integer[][] MATRIX = {{1,1,2,4},{3,1,9,3},{7,0,8,1}};
private void showMatrix(long mask, String label) {
System.out.println(label);
for (int i=0; i< MATRIX.length; i++) {
System.out.print("[ ");
for (int j=0; j<MATRIX[i].length; j++) {
int elem = getBitAt(mask, i, j) > 0 ? MATRIX[i][j] : 0;
System.out.print(elem + " ");
}
System.out.println("]");
}
System.out.println();
}
private long clearBitAt(long mask, int i, int j) {
int pos = i * MATRIX[0].length + j;
int clearMask = ~ (1 << pos);
return clearMask & mask;
}
private long getBitAt(long mask, int i, int j) {
int pos = i * MATRIX[0].length + j;
return mask & (1 << pos);
}
private long setZerosFor(long mask, int posI, int posJ) {
for (int i=0; i<MATRIX.length; i++) {
mask = clearBitAt(mask, i, posJ);
}
for (int j=0; j<MATRIX[0].length; j++) {
mask = clearBitAt(mask, posI, j);
}
return mask;
}
private void solve() {
// matrix has a initial mask (number), where each bit is 0 if element = 0, else 1
long mask = (long) Math.pow(2, MATRIX.length * MATRIX[0].length) - 1;
showMatrix(mask, "Initial:");
for (int i=0; i<MATRIX.length; i++) {
for (int j=0; j<MATRIX[0].length; j++) {
if (MATRIX[i][j] == 0) {
mask = setZerosFor(mask, i , j);
}
}
}
showMatrix(mask, "After Zeros set:");
// O(1) space complexity
}
public static void main(String args[]) {
new Exercise11().solve();
}
}