Advanced algorithm

• Circle detection: Floyd's Tortoise and Hare

• Find majority: Boyer-Moore Algorithm

Floyd's Tortoise and Hare

quesions

https://leetcode.com/problems/linked-list-cycle-ii/description/ https://leetcode.com/problems/find-the-duplicate-number/description/

explanation

Boyer-Moore Algorithm

questions

https://leetcode.com/problems/majority-element-ii/description/

explanation

https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html

// https://leetcode.com/problems/majority-element-ii/description/

public class Solution {
public List<Integer> majorityElement(int[] nums) {
 //there should be at most 2 different elements in nums more than n/3
 //so we can find at most 2 elements based on Boyer-Moore Majority Vote algo
 List<Integer> res = new ArrayList<Integer>();
 if(nums.length==0) return res;
 int count1=0,count2=0,m1=0,m2=0;
 for(int n : nums){
     if(m1==n) count1++;
     else if(m2==n) count2++;
     else if(count1==0) {
         m1=n;
         count1=1;
     }
     else if(count2==0) {
         m2=n;
         count2=1;
     }
     else{
         count1--;
         count2--;
     }
 }
 count1=0;
 count2=0;
 //count the number for the 2 elements
 for(int n:nums){
     if(n==m1) count1++;
     else if(n==m2) count2++;
 }
 //if those appear more than n/3
 if(count1>nums.length/3) res.add(m1);
 if(count2>nums.length/3) res.add(m2);
 return res;

   }
}

KMP

1) build pattern table; 2) match them https://www.youtube.com/watch?v=GTJr8OvyEVQ&t=632s https://leetcode.com/problems/implement-strstr/description/ https://leetcode.com/problems/repeated-substring-pattern/description/ https://leetcode.com/problems/shortest-palindrome/description/

Kadane's algorithm (maximum subarray sum)

https://leetcode.com/problems/maximum-subarray https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/description/

A* search - n-puzzle problems

class Solution {
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int slidingPuzzle(int[][] board) {
        // edge cases

        // find 0 position
        int r0 = 0, c0 = 0, row = board.length, col = board[0].length;
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (board[r][c] == 0) {r0 = r; c0 = c; break;}
            }
        }
        State begin = new State(board, 0, r0, c0); // initial state
        PriorityQueue<State> pq = new PriorityQueue<>();
        Set<State> inQueue = new HashSet<>();
        pq.offer(begin);
        inQueue.add(begin);

        // BFS
        while (!pq.isEmpty()) {
            State curr = pq.poll();
            if (curr.reachTarget()) return curr.step;
            for (int[] d : dirs) {
                int r = curr.r0 + d[0];
                int c = curr.c0 + d[1];
                State next = curr.move(r, c);
                if (next == null || inQueue.contains(next)) continue;
                pq.offer(next);
                inQueue.add(next);
            }
        }

        return -1;
    }
}

class State implements Comparable<State> {
    int[][] board;
    int step, r0, c0, row, col;

    public State(int[][] matrix, int k, int i, int j) {
        row = matrix.length; col = matrix[0].length;
        this.board = new int[row][col]; // deep copy passed matrix
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                board[r][c] = matrix[r][c];
            }
        }
        this.step = k;
        this.r0 = i;
        this.c0 = j;
    }

    public State move(int i, int j) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return null; // out of boundary
        State res = new State(this.board, step + 1, i, j);
        int tmp = res.board[i][j];
        res.board[i][j] = res.board[r0][c0];
        res.board[r0][c0] = tmp;
        return res;
    } 

    public boolean reachTarget() {
        return distanceToTarget() == 0;
    }

    public int distanceToTarget() {
        int sum = 0;
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                int val = board[r][c];
                if (val == 0) continue;
                int i = (val - 1) / 3; // this value suppossed to in this cell
                int j = (val - 1) % 3;
                sum += Math.abs(r - i) + Math.abs(c - j);
            }
        }
        return sum;
    }

    @Override
    public boolean equals(Object obj) {
        State that = (State) obj;
        return Arrays.deepEquals(this.board, that.board);
    }
    @Override
    public int hashCode() {
        return Arrays.deepHashCode(this.board);
    }
    @Override
    public int compareTo(State that) {
        return (distanceToTarget() + step) - (that.distanceToTarget() + that.step);
    }
}

Binary Indexed Tree

BIT explain: https://www.topcoder.com/thrive/articles/Binary%20Indexed%20Trees Key: one index is responsible for storing value representing a previous range, which is (index - getLSB(index), index]. E.g. index 12(1100) is responsible for (8, 12], i.e. (1000, 1100].

void update(int idx, int val) {
  while (idx <= MaxIdx) {
    tree[idx] += val;
    idx += (idx & -idx);
  }
}

int read(int idx) {
  int sum = 0;
  while (idx > 0) {
    sum += tree[idx];
    idx -= (idx & -idx);
  }
  return sum;
}

// "(idx & -idx)" is to get least significant non-zero bit, can also do idx & ~(idx-1), which is more intuitive.

https://leetcode.com/problems/range-sum-query-mutable/description/ https://leetcode.com/problems/range-sum-query-2d-mutable/description/

https://leetcode.com/problems/reverse-pairs/description/ https://leetcode.com/problems/count-of-smaller-numbers-after-self https://leetcode.com/problems/count-of-range-sum