> For the complete documentation index, see [llms.txt](https://amartyushov.gitbook.io/tech/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://amartyushov.gitbook.io/tech/computer-science/general-notes-1.md).

# Algorithms

**Disclaimer:** current page is not for educational purposes, it has a intention of notes for myself about algorithms.

## Big O

Asymptotic runtime. 

### Time complexity

![](/files/-M5uLFgWiTeEVuk99-kM)

`BigTheta` is a merge of BigO and BigOmega => 

the algorithm is BigTheta(N) if it is O(N) && BigOmega(N).

In industry BigO is close to BigTheta => **the tightest description of the time.**

**The way to describe bigO for particular input:**

* Best case (not useful)
* Worst case
* expected case (useful to consider as worst, but sometimes.

![](/files/-M5uTodBiOYbRGvc3HwY)

![](/files/-M5uUIwLC4mjLoI4LzW9)

:information\_source:When you see a problem where number of elements is halved each time, it will be most likely $$O(logN)$$ runtime.

:information\_source: When recursive function makes multiple calls =often=> $$O(branches^{depth})$$ 

### Space complexity

To create a array n => O(n) space

To create two-dimentional array n\*n => $$O(n^2)$$ space

![](/files/-M5uRUuXT4Yn0Y_qcHlE)

What affects: **data structure size** and **call stack size**.

## Iteration over strings (Перебор строк)

**Lexicographical** order: (abc < acb)\
Strict definition:

```
s < t  
s[i] = t[i], i=0,1..k-1, s[k]<t[k]
```

For three chars 'a', 'b', 'c' the code to produce all combinations in lexicographical order is:

```java
for (char i = 'a'; i <= 'c'; i++) {
    for (char j = 'a'; j <= 'c'; j++) {
        for (char k = 'a'; k <= 'c'; k++) {
            System.out.println(i+""+j+k);
        }
    }
}
```

<details>

<summary>Result printout</summary>

aaa aab aac aba abb abc aca acb acc baa bab bac bba bbb bbc bca bcb bcc caa cab cac cba cbb cbc cca ccb ccc

</details>

In more general case, when it is required to iterate over all strings with length **n** which consist of first **m** chars of alphabet.\
The task can be reformulated differently: Output all sequences with a length on **n** which consist of numbers from 0 to **m**.

```java
private static Integer[] array;
private static Integer m = 3; // max integer in the sequence
private static Integer n = 3; // length of the sequence

public static void main(String[] args) {
    array = new Integer[m];
    rec(0);
}

private static void rec(int idx) {
    if (idx == n) {
        Arrays.stream(array).forEach(System.out::print);
        System.out.println();
        return;
    }
    for (int i = 1; i <= m; i++) {
        array[idx]=i;
        rec(idx+1);
    }
}
```

```java
111
112
113
121
...
333
```

## Permutation

All sequences of integers from 1 to n, where each integer is used only once. Such sequence is called - **permutation**.

```java
public class IntegerPermutation {
    static int size = 3;
    static Integer[] array = new Integer[size];
    static Boolean[] used = new Boolean[size+1];

    public static void main(String[] args) {
        initUsed();
        rec(0);
    }

    private static void rec(int idx) {
        if (idx == size) {
            Arrays.stream(array).forEach(System.out::print);
            System.out.println();
        }
        for (int i = 1; i<=size; i++) {
            if (used[i] == true) {
                continue;
            }
            used[i] = true;
            array[idx] = i;
            rec(idx+1);
            used[i] = false;
        }
    }

    private static void initUsed() {
        for (int i=0; i<size+1; i++){
            used[i]=false;
        }
    }
}
```

Array `used` is needed to restrict having permutation with same integers. Output is:

```java
123
132
213
231
312
321
```

### Correct brace sequence

Lets consider a correct brace sequence from Math point of view. E.g. `((()))`, `()()()`, `(())()`. One of implementations:

```java
boolean isCorrect(String s) {
    int balance = 0;
    for (int i=0; i<s.length(); i++) {
        if (s.charAt(i) == '(') {
            balance++;
        } else {
            balance--;
        }
        if (balance<0){
            return false;
        }
    }
    return (balance == 0);
}
```

Also there is a well-known implementation of this algorithm with a stack.

### Implementation of correct brace sequence using recursion

```java
public class IsBraceSequencedCorrectRecursion {
	
	private static int n = 2;
	static char[] s = new char[2*n];
	
	public static void main(String[] args) {
		rec(0,0);
	}
	
	private static void rec(int idx, int bal) {
		if (idx == 2*n) {
			if (bal == 0) {
				out();
			}
			return;
		}
		
		s[idx] = '(';
		rec(idx + 1, bal + 1);
		
		if (bal == 0) {
			return;
		}
		
		s[idx] = ')';
		rec(idx + 1, bal - 1);
	}
	
	
	private static void out() {
		new String(s).chars().mapToObj(i->(char)i).forEach(System.out::print);
		System.out.println("");
	}
}
```

## Binary search

time efficiency O(log(n)). (base of logarithm is 2, not 10.)

3 parts of successful binary search:

* ***pre-processing***. Sort if collection is not sorted.
* ***Binary search***. Using loop or recursion divide search space in half each comparison.
* ***post-processing***. Determine viable candidates in remaining space.

### Template 1

```java
// Template #1 
int binarySearch(int[] nums, int target){
  if(nums == null || nums.length == 0)
    return -1;

  int left = 0, right = nums.length - 1;
  while(left <= right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    
    if (nums[mid] == target) {
      return mid; 
    } else if (nums[mid] < target) { 
      left = mid + 1; 
    } else { 
      right = mid - 1; 
    }
  }

  // End Condition: left > right
  return -1;
}
```

**Distinguishing Syntax:**

* Initial Condition: `left = 0, right = length-1`
* Termination: `left > right`
* Searching Left: `right = mid-1`
* Searching Right: `left = mid+1`

#### Another template&#x20;

Below template inspired by known article :star:[LINK](https://leetcode.com/discuss/general-discussion/786126/python-powerful-ultimate-binary-search-template-solved-many-problems)

Suppose we have a **search space**. It could be an array, a range, etc. Usually it's sorted in ascending order. For most tasks, we can transform the requirement into the following generalized form:

**Minimize k , s.t. condition(k) is True**

The following code is the most generalised binary search template:

```python
def binary_search(array) -> int:
    def condition(value) -> bool:
        pass

    left, right = min(search_space), max(search_space) # could be [0, n], [1, n] etc. Depends on problem
    while left < right:
        mid = left + (right - left) // 2
        if condition(mid):
            right = mid
        else:
            left = mid + 1
    return left
```

## Breadth first search

Used to explore nodes and edges of the graph.

**Time complexity O(Verticies + Edges)**.

**Finding shortest path on unweighted graphs**.

![](/files/-MA2sgGH3d6bJ3DgeUjB)

## Depth first search (DFS)

Goes deep.

## Dijkstra's Algorithm

***The basic goal of the algorithm is to determine the shortest path between a starting node, and the rest of the graph.***\
This is a greedy algorithm.

[First explanation](https://www.youtube.com/watch?v=gdmfOwyQlcI)\
[Shortest path from source to all vertices in given graph + code](https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/)\
[Really nice explanation of Dijkstra\`s algorithm](https://www.youtube.com/watch?v=pVfj6mxhdMw)\
[Really good article about algorithm + java implementation](https://www.baeldung.com/java-dijkstra)

### Logic

* *Settled* nodes are the ones with a known minimum distance from the source.
* The *unsettled* nodes set gathers nodes that we can reach from the source, but we don't know the minimum distance from the starting node.

#### Here's a list of steps to follow in order to solve the SPP with Dijkstra:

* Set distance to *startNode* to zero.
* Set all other distances to an infinite value.
* We add the *startNode* to the unsettled nodes set.
* While the unsettled nodes set is not empty we:
  * Choose an evaluation node from the unsettled nodes set, the evaluation node should be the one with the lowest distance from the source.
  * Calculate new distances to direct neighbours by keeping the lowest distance at each evaluation.
  * Add neighbours that are not yet settled to the unsettled nodes set.

These steps can be aggregated into two stages, Initialisation and Evaluation.&#x20;

## Dynamic connectivity problem

![](/files/-MJlG6n-uspVFAn8Kaob)

### Union find

This is an algorithm which answers a question whether two nodes are connected to each other (see dynamic connectivity problem).

![](/files/-MJlHGr-6xsLgtrzxtfx)

* Find query
  * check if two objects are in the same component
* Union command
  * Replace components containing two objects with their union

![](/files/-MJlHy25D9nG0oni1oSM)

```java
public class UnionFind {
    // init UF data structure with N objects (O to N-1)
    UnionFind(int N);
    
    // add connection between p and q
    void union(int p, int q);
    
    // are p and q in the same component?
    boolean connected(int p, int q);
}
```

### Quick-find algorithm (eager approach)

| algorithm              | init | union        | find |
| ---------------------- | ---- | ------------ | ---- |
| quick-find             | N    | N (too slow) | 1    |
| quick-union            | N    | N            | N    |
| quick-union (weighted) | N    | logN         | logN |

Data structure:

* Integer array `id[]` of size N
* Interpretation: `p` and `q` are connected iff (if and only if) they have the same id

![](/files/-MK0e5SuCeX1OhIXz3g-)

**Find**. Check if `p` and `q` have the same id.\
**Union**. To merge components containing `p` and `q` change all entries whose id equals id\[p] to id\[q].

![](/files/-MK0epoND48NvOrFtbGi)

```java
public class QuickFindUF {
    
    private int[] id;
    
    // set id of each object to itself. 
    // initially all objects are in diff components
    // N array accesses
    public QuickFindUF(int N) {
        id = new int[N];
        for (int i=0; i<N; i++) {
            id[i]=i;        
        }    
    }
    
    // check whether p and q are in the same component
    // 2 array accesses
    public boolean connected(int p, int q) {
        return id[p] == id[q];
    }
    
    // change all entries with id[p] to id[q]
    // at most 2N+2 array accesses
    public void union(int p, int q) {
        int pid = id[p];
        int qid = id[q];
        for (int i=0; i<id.length; i++) {
            if (id[i] == pid) {
                id[i] = qid;
            }        
        }
    }
}
```

### Quick-union (lazy approach)

Data structure:

* Integer array `id[]` of size N
* Interpretation: id\[i] is parent of i

![](/files/-MK0ktJKHg_ZRkERirh-)

**Find**. Check if `p` and `q` have the same root.

**Union**. To merge components containing `p` and `q` - set the id of p's root to the id of q's root. (e.g. union(3,4) - 3 goes under 4. The order is important)

![](/files/-MK1OqKgVStzvamFW1ac)

```java
public class QuickUnionUF {

    private int[] id;

    // set id of each object to itself. 
    // initially all objects are in diff components
    // N array accesses
    public QuickUnionUF(int N) {
        id = new int[N];
        for (int i=0; i<N; i++) {
            id[i]=i;        
        }    
    } 
    
    private int root(int i) {
        while (i != id[i]) {
            i = id[i];
        }
        return i;
    }
    
    public boolean connected(int p, int q) {
        return root(p) == root(q);
    }
    
    public void union(int p, int q) {
        int i = root(p);
        int j = root(q);
        id[i] = j;
    }    
}
```

### Quick-union (weighted)

* Modify quick-union to avoid tall trees
* Keep track of size of each tree
* Balance by linking root of **smaller** tree to root of **larger** tree

```java
public class QuickUnionWeightedUF {

    private int[] id;
    // num of items  in the tree rooted at i
    private int[] sz;
    
    // set id of each object to itself. 
    // initially all objects are in diff components
    // N array accesses
    public QuickUnionUF(int N) {
        id = new int[N];
        for (int i=0; i<N; i++) {
            id[i]=i;        
        }    
    } 
    
    private int root(int i) {
        while (i != id[i]) {
            i = id[i];
        }
        return i;
    }
    
    public boolean connected(int p, int q) {
        return root(p) == root(q);
    }
    
    public void union(int p, int q) {
        int i = root(p);
        int j = root(q);
        if (i == j) return;
        if (sz[i] < sz[j]) {
            id[i] = j; 
            sz[j] += sz[i];
        } else {
            id[j] = i;
            sz[i] += sz[j];
        }   
    }    
}
```

Depth of any node `x` is at most `lgN` (base 2 logarithm).

### Quick-union with path compression

![](/files/-MKaV8yTzrZ5fNCxZ492)

## Percolation

![](/files/-MKaXGBtqMZEQByv0Sh9)

![](/files/-MKaXnseyPnG5JJa2QOE)

## Useful math

$$1 + 2 + 3 + ... + n = {n(n+1) \over 2 }$$ &#x20;

$$2^0 + 2^1 + 2^2 + ... + 2^n = 2^{n+1}-1$$

&#x20;$$\log\_{10} x = {\log\_2 x \over \log\_2 10}$$ => for BigO notation it is not important what is a base  for logarithm

## Explained tasks

* [First unique character in a string (LeetCode)](https://www.youtube.com/watch?v=St47WCbQa9M)
  * [first non repeating character](https://www.youtube.com/watch?v=5co5Gvp_-S0)
* [Single number among others being twice](https://www.youtube.com/watch?v=CvnnCZQY2A0)
  * This is non optimal solution. The better is [here](https://github.com/amartyushov/Experiments/blob/master/leetcode/src/main/java/io/mart/problems/p136.java).
* [Is a number a power of two](https://www.youtube.com/watch?v=uVAvuyah9Ek)
  * There is a better solution [here](https://github.com/amartyushov/Experiments/blob/deef7ed4df04f9e9015969942c01b5cc80e431fb/leetcode/src/main/java/io/mart/problems/p231.java#L7). With explanation is the [comment](https://www.youtube.com/watch?v=uVAvuyah9Ek\&lc=UgwozkgqhVISHHHZ-WF4AaABAg.8uZvpVs3mA-97r2qDmYu3A).
* [Robot return to origin](https://www.youtube.com/watch?v=f7Zd8hEbCz0). Check that moves right, left, down, up have equal number and you return to the same initial point.
* [Return a missing number in the monotonically increasing array.](https://www.youtube.com/watch?v=YMYVYSWL93w)
* [Sum of the tree path matches an expected value](https://www.youtube.com/watch?v=Hg82DzMemMI).
* [Return element from array and return new length.](https://www.youtube.com/watch?v=sRKByfozeEg)
* [Lowest common ancestor of BST](https://www.youtube.com/watch?v=kulWKd3BUcI)
* Jewels and stones. [How many chars from one string are contained in another string.](https://www.youtube.com/watch?v=9Reqqk60Nv4)
* [Most frequent word in string except banned words](https://www.youtube.com/watch?v=q2v5nik5vwU)
* [K closest points to origin](https://www.youtube.com/watch?v=1rEUgAG7f_c)
* [Best time to buy and sell stock II](https://www.youtube.com/watch?v=blUwDD6JYaE)&#x20;
* [Climbing stairs](https://www.youtube.com/watch?v=uHAToNgAPaM)