# 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)


---

# 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://amartyushov.gitbook.io/tech/computer-science/general-notes-1.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.