# 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

![](https://leetcode.com/problems/linked-list-cycle-ii/Figures/142/Slide1.PNG) ![](https://leetcode.com/problems/linked-list-cycle-ii/Figures/142/diagram.png)

## Boyer-Moore Algorithm

### questions

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

### explanation

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

```java
// 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

```java
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].

```java
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>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/topics/advanced-algorithm.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.