Insert Delete GetRandom O(1) Duplicates Allowed

https://github.com/fishercoder1534/fishercoderLeetcode/blob/master/MEDIUM/src/medium/RandomizedCollection.java

Advertisements

Range Sum Query 2D – Mutable

  • My natural naive knowledge is:
    • either have update() in O(1) time and sumRange() in O(n) time: have a loop to calculate the sum each time after an update
    • or have update() in O(n) time and sumRange() in O(1) time: have another array to store the sum of all previous elements, thus the sum for f(n) could be deduced from sum(n+1) – sum(n)
  • For sure, my naive approach got TLE.
  • Time to learn a more advanced data structure: Binary Indexed Tree!
    • Leaf nodes are the elements of the input array
    • each internal node represents some merging of the leaf nodes

 

  • An array representation of tree could be used to represent Segment Trees. For each node at index i, the left child is at index 2*i+1, right child at 2*i+2 and the parent is at floor((i-1)/2).
  • In mathematics and computer science, the floor and ceiling functions map a real number to the largest previous or the smallest following integer, respectively. More precisely, floor(x)  is the largest integer less than or equal to x and ceiling(x)  is the smallest integer greater than or equal to x.
  • There’s a graph here which is very helpful: http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
    • Every node has two numbers: one is the index of this node, the other is the value at this node
    • One important formula to get the parent index of a node at index i: parent(i) = i-i&(-i)
    • The above formula means to remove the right-most bit from i, and then AND with i, and then subtract that result from i, the following code snippet will be helpful, given i = 12, then parent(i) = 8
      
      
    • System.out.println(Integer.toBinaryString(12));
      System.out.println(Integer.toBinaryString(-12));
      System.out.println(Integer.toBinaryString(12&(-12)));
      System.out.println(12 – (12&(-12)));1100
      11111111111111111111111111110100
      100
      8
    • In the opposite direction, the formula would become parent(i) = i+i&(-i)

Looked at the two posts:

  1. https://discuss.leetcode.com/topic/30343/java-2d-binary-indexed-tree-solution-clean-and-short-17ms
  2. https://discuss.leetcode.com/topic/30935/share-my-java-2-d-binary-indexed-tree-solution

Key notes for me:

  • The biggest time cost is in constructing the binary indexed tree: O(m*n*lgm*lgn), (apparently, there’s a nested fro loop, thus m*n, and inside the nested for loop, it’s calling update(), which is O(lgm*lgn)), however, the tree only needs to be built once, and the benefit this tree brings is that after the tree is built, both update() and sumRange() will have O(lgm*lgn) time.
  • we need an additional array nums[][] to store matrix[][]
  • in the constructor, we build the tree, by calling update(i,j,newVal); function
  • inside update(i,j,newVal); function: we compute the delta between the newVal and the current value stored at nums[i][j], and then
    • store the newVal into this position
    • increment this node and all its parent nodes by delta
      • so, inside this update(i,j,newVal); function, the for loop starts from i+1 and j+1
  • how the sum is computed from the constructed tree:
    • row1,col1 is the overlap that got subtracted twice. That’s why it’s written like this.
int[][] nums;
int[][] tree;
int height;
int width;

public NumMatrix(int[][] matrix) {
if(matrix.length == 0 || matrix[0].length == 0) return;
height = matrix.length;
width = matrix[0].length;
this.nums = new int[height][width];
this.tree = new int[height+1][width+1];
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
update(i, j, matrix[i][j]);
}
}
}

public void update(int rowIndex, int colIndex, int newVal) {
if(height == 0 || width == 0) return;
int delta = newVal - nums[rowIndex][colIndex];
nums[rowIndex][colIndex] = newVal;
for(int i = rowIndex+1; i <= height; i += i&(-i)){
for(int j = colIndex+1; j <= width; j += j&(-j)){
tree[i][j] += delta;//just use its previous value plus delta is good
}
}
}

public int sumRegion(int row1, int col1, int row2, int col2) {
if(height == 0 || width == 0) return 0;
return sum(row2+1, col2+1) + sum(row1, col1) - sum(row1, col2+1) - sum(row2+1, col1);
}

private int sum(int row, int col) {
int sum = 0;
for(int i = row; i > 0; i -= i&(-i)){
for(int j = col; j > 0; j -= j&(-j)){
sum += tree[i][j];
}
}
return sum;
}

Design Snake Game

https://leetcode.com/problems/design-snake-game/

  • Looked at this post: https://discuss.leetcode.com/topic/48626/java-deque-and-hashset-design-with-detailed-comments
  • Keys:
    • Use Deque interface (stands for Double Ended Queue) which means you can remove and insert elements from both ends of the queue, this is exactly what we wanted in this problem. This is also why LinkedList in java is implemented as Doubly-linked list, to support operations in both directions.
    • The typical trick to convert a 2D matrix into a 1D array:
      • rowNumber*width + columnNumber
    • in switch branches, remember to add break; when needed
    • remember to have a field called foodIndex and check if it’s right for the given food[][] position and also remember to increment it by 1 each time a normal eat happens.

public class SnakeGame {

private Set<Integer> set;//Use a set to hold all occupied points for the snake body, this is for easy access for the case of eating its own body
private Deque<Integer> body;//use a queue to hold all occupied points for the snake body as well, this is for easy access to update the tail
int[][] food;
int score;
int foodIndex;
int width;
int height;

/** Initialize your data structure here.
@param width - screen width
@param height - screen height
@param food - A list of food positions
E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
public SnakeGame(int width, int height, int[][] food) {
this.set = new HashSet<Integer>();
set.add(0);//initially at [0][0]
this.body = new LinkedList<Integer>();
body.offerLast(0);
this.food = food;
this.width = width;
this.height = height;
}

/** Moves the snake.
@param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
@return The game's score after the move. Return -1 if game over.
Game over when snake crosses the screen boundary or bites its body. */
public int move(String direction) {
if(score == -1) return -1;

//compute head
int rowHead = body.peekFirst() / width;
int colHead = body.peekFirst() % width;
switch(direction){
case "U":
rowHead--;
break;
case "D":
rowHead++;
break;
case "L":
colHead--;
break;
default:
colHead++;
}
int newHead = rowHead*width+colHead;

set.remove(body.peekLast());//we'll remove the tail from set for now to see if it hits its tail
//if it hits the boundary
if(set.contains(newHead) || rowHead < 0 || colHead < 0 || rowHead >= height || colHead >= width){
return score = -1;
}

//add head for the following two normal cases:
set.add(newHead);
body.offerFirst(newHead);

//normal eat case: keep tail, add head
if(foodIndex < food.length && rowHead == food[foodIndex][0] && colHead == food[foodIndex][1]){
set.add(body.peekLast());//old tail does not change, so add it back to set since we removed it earlier
foodIndex++;
return ++score;
}

//normal move case without eating: move head and remove tail
body.pollLast();
return score;

}
}

/**
* Your SnakeGame object will be instantiated and called as such:
* SnakeGame obj = new SnakeGame(width, height, food);
* int param_1 = obj.move(direction);
*/