class Solution {
public int[] searchRange(int[] nums, int target) {
int start = firstGreaterOrEqual(nums, target);
if (start == nums.length || nums[start] != target) {
return new int[] {-1, -1};
}
return new int[]{start, firstGreaterOrEqual(nums, target+1)-1};
}
private int firstGreaterOrEqual(int[] nums, int target) {
int low = 0, high = nums.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] < target) {
low = mid + 1;
} else {
// A[mid] > target OR A[mid] == target
//We want to capture A[mid] == target as well
//So we should not do mid-1 here, and only do mid
//Works for A[mid] > target case as well.
high = mid;
}
}
return low;
}
}class Solution {
public int findKthLargest(int[] nums, int k) {
return Quick.select(nums, nums.length - k);
}
public static class Quick {
public static int select(int[] nums, int K) {
knuthShuffle(nums);
int low = 0, high = nums.length - 1;
while (low < high) {
int j = partition(nums, low, high);
if (j < K) {
low = j + 1;
} else if (j > K) {
high = j - 1;
} else {
break;
}
}
return nums[K];
}
private static void knuthShuffle(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int j = new Random().nextInt(i+1); //[0, i], not [0, N], otherwise no t unifrom
swap(nums, i, j);
}
}
//low + 1 <= i < j <= high
private static int partition(int[] nums, int low, int high) {
int pivot = nums[low];
int i = low, j = high + 1;
while (true) {
while (nums[++i] < pivot) {
if ( i == high) {
break;
}
}
while (nums[--j] > pivot) {
if (j == low) {
break;
}
}
if (i >= j) {
break;
}
swap(nums, i, j);
}
//j is the first element not greater than pivot
swap(nums, j, low);
return j;
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}class Solution {
public void sortColors(int[] nums) {
Quick3Way.sort(nums);
}
//[low, lt): less than pivot
//(gt, high]: greater than pivot
// i examins [lt, gt]
private static class Quick3Way {
public static void sort(int[] nums) {
sort(nums, 0, nums.length - 1);
}
public static void sort(int[] nums, int low, int high) {
if (high <= low) {
return;
}
int pivot = nums[low];
int lt = low, gt = high;
int i = low;
while (i <= gt) {
if (nums[i] < pivot) {
swap(nums, i++, lt++);
} else if (nums[i] > pivot) {
swap(nums, i, gt--);
} else {
i++; //do nothing
}
}
sort(nums, low, lt-1);
sort(nums, gt+1, high);
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}class BSTIterator {
Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
// Stack for the recursion simulation
this.stack = new Stack<TreeNode>();
// Remember that the algorithm starts with a call to the helper function
// with the root node as the input
this._leftmostInorder(root);
}
private void _leftmostInorder(TreeNode root) {
// For a given node, add all the elements in the leftmost branch of the tree
// under it to the stack.
while (root != null) {
this.stack.push(root);
root = root.left;
}
}
/**
* @return the next smallest number
*/
public int next() {
// Node at the top of the stack is the next smallest element
TreeNode topmostNode = this.stack.pop();
// Need to maintain the invariant. If the node has a right child, call the
// helper function for the right child
if (topmostNode.right != null) {
this._leftmostInorder(topmostNode.right);
}
return topmostNode.val;
}
/**
* @return whether we have a next smallest number
*/
public boolean hasNext() {
return this.stack.size() > 0;
}
}class BSTIterator {
ArrayList<Integer> nodeSorted;
int index;
public BSTIterator(TreeNode root) {
this.nodeSorted = new ArrayList<Integer>();
this.index = -1;
this.inorder(root);
}
private void inorder(TreeNode root) {
if (root == null) {
return;
}
inorder(root.left);
nodeSorted.add(root.val);
inorder(root.right);
}
/** @return the next smallest number */
public int next() {
index++;
return nodeSorted.get(index);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return index+1 < nodeSorted.size();
}
}class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> solutions = new ArrayList<>();
backtrack(nums, solutions, new ArrayList<>(), 0);
return solutions;
}
private void backtrack(int[] nums, List<List<Integer>> solutions, List<Integer> solution, int start) {
solutions.add(new ArrayList<>(solution));
for (int i = start; i < nums.length; i++) {
solution.add(nums[i]);
backtrack(nums, solutions, solution, i+1);
solution.remove(solution.size() - 1);
}
}
}class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, result, new ArrayList<>(), 0);
return result;
}
private void backtrack(int[] nums, List<List<Integer>> result, List<Integer> subset, int start) {
result.add(new ArrayList<>(subset));
for (int i = start; i < nums.length; i++) {
if ( i > start && nums[i] == nums[i-1]) {
continue;
}
subset.add(nums[i]);
backtrack(nums, result, subset, i+1);
subset.remove(subset.size() - 1);
}
}
}class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, nums, new ArrayList<>(), new boolean[nums.length]);
return result;
}
public void backtrack(List<List<Integer>> result, int[] nums, List<Integer> prefix, boolean[] visited) {
if (prefix.size() == nums.length) {
result.add(new ArrayList<>(prefix));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i]) {
continue;
}
prefix.add(nums[i]); visited[i] = true;
backtrack(result, nums, prefix, visited);
prefix.remove(prefix.size() - 1); visited[i] = false;
}
}
}class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
backtrack(result, nums, new ArrayList<>(), new boolean[nums.length]);
return result;
}
private void backtrack(List<List<Integer>> result, int[] nums, List<Integer> prefix, boolean[] visited) {
if (prefix.size() == nums.length) {
result.add(new ArrayList<>(prefix));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i]) {
continue;
}
if (i > 0 && nums[i] == nums[i-1] && visited[i-1]) {
continue;
}
prefix.add(nums[i]); visited[i] = true;
backtrack(result, nums, prefix, visited);
prefix.remove(prefix.size() - 1); visited[i] = false;
}
}
}class Solution {
//string s => solution of s
HashMap<String, List<String>> memo = new HashMap<>();
public List<String> wordBreak(String s, List<String> wordDict) {
return dfs(s, wordDict);
}
public List<String> dfs(String s, List<String> wordDict) {
if (memo.containsKey(s)) {
return memo.get(s);
}
List<String> result = new ArrayList<>();
if (s.length() == 0) {
result.add("");
return result;
}
for (String word: wordDict) {
if (s.startsWith(word)) {
List<String> sublist = dfs(s.substring(word.length()), wordDict);
for (String sub: sublist) {
result.add(word + (sub.isEmpty() ? "" : " ") + sub);
}
}
}
memo.put(s, result);
return result;
}
}public class Solution {
//A copy of dictionary, INPUT
private Set<String> wordSet;
//Adjacency Map of SymbolGraph, INPUT by dict, OUTPUT to bfs, dfs
private Map<String, List<String>> graph = new HashMap<>();
//Path Length from begin word to ALL word in dict, INPUT by bfs, output to dfs
private Map<String, Integer> distance = new HashMap<>();
public List<List<String>> findLadders(String start, String end, List<String> wordList) {
//Step 1: Init all necessary auxiliary information
wordSet = new HashSet<String>(wordList);
wordSet.add(start);
buildGraph();
//Step 2: BFS to Build node adjacency list AND distance lookup
bfs(start, end);
//Step 3: Backtrack on all possible path
List<List<String>> result = new ArrayList<List<String>>();
List<String> pathPrefix = new ArrayList<String>();
dfs(start, end, pathPrefix, result);
return result;
}
private void buildGraph() {
for (String word : wordSet) {
graph.put(word, getNeighbors(word));
}
}
// BFS: Trace every node's distance from the start node (level by level).
private void bfs(String start, String end) {
Queue<String> queue = new LinkedList<String>();
int level = 0;
queue.offer(start);
distance.put(start, 0); //Serve as the marked[] to see if nodes are already visited
while (!queue.isEmpty()) {
int size = queue.size(); //NOTE: Used to explore node level by level
//NOTE: MUST explore all nodes of the level where end word is in.
for (int i = 0; i < size; i++) {
//Get a word
String currentWord = queue.poll();
//Update relevant information: distance & neighbor
int currentDistance = distance.get(currentWord);
//Enqueue unvisited neighbor
for (String neighbor: graph.get(currentWord)) {
if (!distance.containsKey(neighbor)) {
distance.put(neighbor, level+1);
queue.offer(neighbor);
}
}
}
level++;
}
}
// Find all next level nodes.
private List<String> getNeighbors(String node) {
List<String> result = new ArrayList<String>();
char chs[] = node.toCharArray();
//Compute all different variations of the word, and see if it's in the dictionary
for (int i = 0; i < chs.length; i++) {
for (char ch ='a'; ch <= 'z'; ch++) {
if (chs[i] == ch) {
continue;
}
char origCh = chs[i];
chs[i] = ch;
String word = String.valueOf(chs);
if (wordSet.contains(word)) {
result.add(word);
}
chs[i] = origCh;
}
}
return result;
}
// DFS: output all paths with the shortest distance using backtracking
private void dfs(String currentWord, String endWord, List<String> pathPrefix, List<List<String>> result) {
//Step 1: Take a step with currentWord
pathPrefix.add(currentWord);
//Step 2: Explore on all possible next steps
if (endWord.equals(currentWord)) {
//Step 2.1: If already reached end, no need to explore next step
result.add(new ArrayList<String>(pathPrefix));
//NOTE: Do not return early here, you need to be able to backtrack since some other path might lead to endWord
} else {
//Step 2.2: Otherwise, the next step should be the neighbor AND one step larger from current node to end
for (String nextWord : graph.get(currentWord)) {
if (distance.get(nextWord) == distance.get(currentWord) + 1) {
dfs(nextWord, endWord, pathPrefix, result);
}
}
}
//Step 3: Take the step back
pathPrefix.remove(pathPrefix.size() - 1);
}
}class Solution {
class UnionFind {
int[] parent;
int count;
public UnionFind(int N) {
count = 0;
parent = new int[N];
for (int i = 0; i < N; i++) {
parent[i] = -1;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB) {
parent[rootA] = rootB;
count--;
}
}
void addToUF(int i) {
parent[i] = i;
count++;
}
public boolean contains(int i) {
return parent[i] != -1;
}
int getCount() {
return count;
}
}
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> result = new ArrayList<>();
UnionFind uf = new UnionFind(m * n);
int[][] DIRS = new int[][] {
{-1,0}, {1,0}, {0,1}, {0,-1}};
for (int[] pos: positions) {
int r = pos[0], c = pos[1];
int current = r * n + c;
if (uf.contains(current)) {
result.add(uf.getCount());
continue;
}
List<Integer> validNeighbors = new ArrayList<>();
for(int[] dir: DIRS) {
int x = r + dir[0], y = c + dir[1];
if (x >= 0 && x < m && y >= 0 && y < n ) {
int neighbor = x * n + y;
if (uf.contains(neighbor)) {
validNeighbors.add(neighbor);
}
}
}
uf.addToUF(current);
for (int neighbor: validNeighbors) {
uf.union(neighbor, current);
}
result.add(uf.getCount());
}
return result;
}
}class Solution {
class TrieNode {
TrieNode[] child = new TrieNode[26];
String word;
}
TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String w: words) {
TrieNode p = root;
for (char c: w.toCharArray()) {
if (p.child[c-'a'] == null) {
p.child[c-'a'] = new TrieNode();
}
p = p.child[c-'a'];
}
p.word = w;
}
return root;
}
char VISITED = '#';
public List<String> findWords(char[][] board, String[] words) {
List<String> result = new ArrayList<>();
TrieNode root = buildTrie(words);
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs(board, i, j, root, result);
}
}
return result;
}
private void dfs(char[][] board, int i, int j, TrieNode p, List<String> result) {
char c = board[i][j];
if (c == VISITED || p.child[c-'a'] == null) {
return;
}
p = p.child[c-'a'];
if (p.word != null) {
result.add(p.word);
p.word = null; //Mark this word as invalid to avoid duplication
}
board[i][j] = VISITED;
//Visit four valid neighbor cells
if (i > 0) {
dfs(board, i-1, j, p, result);
}
if (j > 0) {
dfs(board, i, j-1, p, result);
}
if (i < board.length - 1) {
dfs(board, i+1, j, p, result);
}
if (j < board[0].length - 1) {
dfs(board, i, j+1, p, result);
}
board[i][j] = c;
}
}class Solution {
class TrieNode {
TrieNode[] child = new TrieNode[26];
//Set of words that have current prefix
Set<String> wordSet = new HashSet<String>();
}
TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String word: words) {
TrieNode node = root;
for (char c: word.toCharArray()) {
if (node.child[c-'a'] == null) {
node.child[c-'a'] = new TrieNode();
}
node = node.child[c-'a'];
node.wordSet.add(word);
}
}
return root;
}
Set<String> getWordsWithPrefix(TrieNode root, String prefix) {
TrieNode node = root;
for (char c: prefix.toCharArray()) {
if (node.child[c-'a'] == null) {
return new HashSet<>();
}
node = node.child[c-'a'];
}
return node.wordSet;
}
public List<List<String>> wordSquares(String[] words) {
TrieNode root = buildTrie(words);
List<List<String>> result = new ArrayList<>();
for (String word: words) {
List<String> candidate = new ArrayList<>();
candidate.add(word);
backtrack(candidate, result, 1, words[0].length(), root);
}
return result;
}
private void backtrack(List<String> candidate, List<List<String>> result, int wordCount, int squareSize, TrieNode root) {
if (wordCount == squareSize) {
result.add(new ArrayList<>(candidate));
return;
}
StringBuilder prefix = new StringBuilder();
for (String word: candidate) {
prefix.append(word.charAt(wordCount));
}
for (String word: getWordsWithPrefix(root, prefix.toString())) {
candidate.add(word);
backtrack(candidate, result, wordCount+1, squareSize, root);
candidate.remove(candidate.size()-1);
}
}
}class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
int LEFT = 0, RIGHT = 1, HEIGHT = 2;
//Ordered by critical points: left -> building, right -> building
Map<Integer, List<int[]>> cps = new TreeMap<>();
for (int[] building: buildings) {
int left = building[LEFT], right = building[RIGHT];
if (!cps.containsKey(left)) {
cps.put(left, new ArrayList<>());
}
if (!cps.containsKey(right)) {
cps.put(right, new ArrayList<>());
}
cps.get(left).add(building);
cps.get(right).add(building);
}
List<List<Integer>> result = new ArrayList<>();
int prevHeight= -1;
//Heap of building by height
PriorityQueue<int[]> heap = new PriorityQueue<>(
(b1, b2) -> Integer.compare(b2[HEIGHT], b1[HEIGHT]));
//Sweep line
for (int cp: cps.keySet()) {
List<int[]> activeBuilding = cps.get(cp);
for (int[] building: activeBuilding) {
if (cp == building[LEFT]) {
heap.offer(building);
} else if (cp == building[RIGHT]) {
heap.remove(building);
}
}
if (heap.isEmpty()) {
result.add(Arrays.asList(cp, 0));
}else {
int height = heap.peek()[HEIGHT];
if (height != prevHeight) {
result.add(Arrays.asList(cp, height));
prevHeight = height;
}
}
}
return result;
}
}public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || k <= 0) {
return new int[0];
}
int[] results = new int[nums.length - k + 1];
int ri = 0;
// store index
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
//remove numbers out of range k
while (!q.isEmpty() && q.peek() < i - k + 1) {
q.poll();
//inspect(i, q, "index out of range, POLL", nums);
}
//remove smaller numbers in k range as they are useless
while(!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
q.pollLast();
//inspect(i, q, "last less than current, POLL_LAST", nums);
}
//q contains index where as r contins content
q.offer(i);
//inspect(i, q, "add new i,OFFER", nums);
if (i >= k - 1) {
//inspect(i, q, "window size reached, PEEK", nums);
results[ri] = nums[q.peek()];
ri++;
}
}
return results;
}
}class Solution {
public int largestRectangleArea(int[] heights) {
//What's the first element smaller than me on my left
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
stack.push(-1); //Mark end of stack
for (int i = 0; i< heights.length; i++) {
//Only the first element smaller than me can pop me out of stack, so we update area only on pop
while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
maxArea = Math.max(maxArea, heights[stack.pop()] * (i - stack.peek() - 1) );
}
stack.push(i);
}
while (stack.peek() != -1) {
maxArea = Math.max(maxArea, heights[stack.pop()] * (heights.length - stack.peek() - 1));
}
return maxArea;
}
}/*
expr -> term ((PLUS|MINUS) term)*
term -> factor ((MUL|DIV) factor)*
factor -> INTEGER | (PLUS|MINUS) factor | LPAREN expr RPAREN
*/
class Solution {
enum Type {
PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, EOF, INTEGER
}
class Token {
Type type;
int value;
public Token(Type type) {
this.type = type;
this.value = -1;
}
public Token(Type type, int value) {
this.type = type;
this.value = value;
}
}
class Lexer {
char NONE = '#';
int pos;
char currentChar;
String text;
public Lexer(String text) {
this.text = text;
this.pos = 0;
currentChar = text.length() == 0 ? NONE: text.charAt(pos);
}
private void advance() {
currentChar = (pos >= text.length() - 1 ? NONE : text.charAt(++pos));
}
private int integer() {
int value = 0;
while (currentChar != NONE && Character.isDigit(currentChar)) {
value = value * 10 + currentChar - '0';
advance();
}
return value;
}
public Token getNextToken() {
while (currentChar != NONE) {
if (Character.isSpace(currentChar)) {
advance();
continue;
} else if (Character.isDigit(currentChar)) {
return new Token(Type.INTEGER, integer());
} else if (currentChar == '+') {
advance();
return new Token(Type.PLUS);
} else if (currentChar == '-') {
advance();
return new Token(Type.MINUS);
} else if (currentChar == '*') {
advance();
return new Token(Type.MUL);
} else if (currentChar == '/') {
advance();
return new Token(Type.DIV);
} else if (currentChar == '(') {
advance();
return new Token(Type.LPAREN);
} else if (currentChar == ')') {
advance();
return new Token(Type.RPAREN);
}
}
return new Token(Type.EOF);
}
}
class Parser {
Lexer lex;
Token currentToken;
public Parser(Lexer lex) {
this.lex = lex;
currentToken = lex.getNextToken();
}
private void eat(Type type) {
if (currentToken.type != type) {
System.out.println("Parser Error: invalid type");
}
currentToken = lex.getNextToken();
}
// expr -> term ((PLUS|MINUS) term)*
int expr() {
int result = term();
while (currentToken.type == Type.PLUS || currentToken.type == Type.MINUS) {
Token token = currentToken;
if (token.type == Type.PLUS) {
eat(Type.PLUS);
result += term();
} else if (token.type == Type.MINUS) {
eat(Type.MINUS);
result -= term();
}
}
return result;
}
// term -> factor ((MUL|DIV) factor)*
int term() {
int result = factor();
while (currentToken.type == Type.MUL || currentToken.type == Type.DIV) {
Token token = currentToken;
if (token.type == Type.MUL) {
eat(Type.MUL);
result *= factor();
} else if (token.type == Type.DIV) {
eat(Type.DIV);
result /= factor();
}
}
return result;
}
// factor -> INTEGER | (PLUS|MINUS) factor | LPAREN expr RPAREN
int factor() {
Token token = currentToken;
if (token.type == Type.INTEGER) {
eat(Type.INTEGER);
return token.value;
} else if (token.type == Type.LPAREN) {
eat(Type.LPAREN);
int result = expr();
eat(Type.RPAREN);
return result;
} else if (token.type == Type.MINUS) {
eat(Type.MINUS);
return -1*factor();
} else if (token.type == Type.PLUS) {
eat(Type.PLUS);
return factor();
}
return -1;
}
}
public int calculate(String s) {
Lexer lex = new Lexer(s);
Parser parser = new Parser(lex);
return parser.expr();
}
}