View MaximalRectangle.java
import java.util.Stack;
public class MaximalRectangle {
static int findMaxArea(int l, int[] heights) {
Stack<Integer> stack = new Stack<Integer>();
int max_area = 0;
for (int i = 0; i < l; i++) {
while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
int top_height = heights[stack.pop()];
int w = stack.isEmpty() ? i : i - stack.peek() - 1;
View MaximalSquare.java
public class MaximalSquare {
static int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
static int findMaxSquare(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
int[][] memo = new int[n][m];
int max = 0;
View NestedListIterator.java
import java.util.*;
public class NestedListIterator implements Iterator<Integer> {
interface NestedInteger {
boolean isInteger();
Integer getInteger();
List<NestedInteger> getList();
}
Stack<Iterator<NestedInteger>> stack;
View Vector2DIterator.java
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
public class Vector2DIterator implements Iterator<Integer> {
Iterator<List<Integer>> parent = null;
Iterator<Integer> child = null;
void updateChild() {
while (!child.hasNext() && parent.hasNext()) {
View RestoreLotteryNumber.java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class RestoreLotteryNumber {
static void restoreLotteryNumbers(String s, List<String> result, Set<String> seen,
String number, int count, int index) {
if (count > 7) { return; }
if (count == 7 && number.length() == (s.length() + 6)) {
View RestoreIpAddresses.java
import java.util.ArrayList;
import java.util.List;
public class RestoreIpAddresses {
static void restoreIpAddresses(String s, List<String> result, String ip, int count, int index) {
if (count > 4) { return; }
if (count == 4 && ip.length() == (s.length() + 3)) {
result.add(ip);
}
View FindTheCelebrity.java
import java.util.*;
public class FindTheCelebrity {
static int N = 7;
static Map<Integer, List<Integer>> relation = new HashMap();
static {
relation.put(0, Arrays.asList(1));
relation.put(1, new ArrayList()); // celebrity
relation.put(2, Arrays.asList(1));
relation.put(3, Arrays.asList(1, 2));
View EggDropping.java
public class EggDropping {
static int findFloor(int n, int k) {
// n: number of eggs
// k: number of floors
int[][] memo = new int[n + 1][k + 1];
// initialize
// 0 trial for 0th floor
// 1 trial for 1st floor
for (int i = 1; i <= n; i++) {
memo[i][0] = 0;
View SquareRoot.java
public class SquareRoot {
static int naive(int x) {
if (x == 0 || x == 1) { return x; }
for (int i = 2; i < x; i++) {
long temp = i * i;
if (temp > x) {
return i - 1;
}
}
return -1;
View PowerImpl.java
public class PowerImpl {
static int power(int x, int y) {
// base case
if (y == 0) {
return 1;
}
int temp = power(x, y / 2);
if (y % 2 == 0) {
return temp * temp;
} else {