View SkylineProblem.java
import java.util.*;
public class SkylineProblem {
static class Item implements Comparable<Item> {
int left;
int right;
int height;
Item(int s, int e, int h) {
left = s;
View LargestRectangleInHistogram.java
import java.util.Stack;
public class LargestRectangleInHistogram {
static int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int n = heights.length;
Stack<Integer> stack = new Stack<Integer>();
int max_area = 0;
View NimGame.java
public class NimGame {
static String doesFirstWin(int[] piles) {
int n = piles.length;
int x = piles[0];
for (int i = 1; i < n; i++) {
x ^= piles[i];
}
if (x != 0) {
return "First";
} else {
View SumOfTwoIntegers.java
public class SumOfTwoIntegers {
static int getSum(int a, int b) {
while (b != 0) {
int carry = a & b;
a ^= b;
b = carry << 1;
}
return a;
}
View SwapWithoutExtraSpace.java
public class SwapWithoutExtraSpace {
static void swap(int[] nums, int i, int j) {
nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
}
static void printArray(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (i != 0) { System.out.print(" "); }
View LonelyInteger.java
public class LonelyInteger {
static int findLonelyInteger(int[] nums) {
int x = nums[0];
for (int i = 1; i < nums.length; i++) {
x ^= nums[i];
}
return x;
}
public static void main(String[] args) {
View LinearPartition.java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class LinearPartition {
static int INF = Integer.MAX_VALUE;
static int[][] partition(int[] values, int k) {
int n = values.length;
int[][] M = new int[n][k];
View CountOfSmallerNumbersAfterSelf.java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class CountOfSmallerNumbersAfterSelf {
static class TreeNode {
int val;
int count = 1;
TreeNode left;
TreeNode right;
View SubsetSum.java
/*
Problem: Given an array of integers and sum S,
find whether the subset exists to create sum S or not.
*/
import java.util.ArrayList;
import java.util.List;
public class SubsetSum {
// complexity: time O(n*m), space O(n*m), n: number of integers, m: sum
static boolean canMakeSubset(int[] ary, int sum) {
View LinearParition.java
/*
Problem: Given an array of integers and number of workers,
find a fair amount of partitions.
(sum of each partition may or may not be the same)
This is a k-partition problem, also known as a fair workload problem.
*/
public class LinearPartition {
static int INF = Integer.MAX_VALUE;
// complexity: O(n*k), space O(n*k)