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

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.

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

ℹ️ 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

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:

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);
        }
    }
}

Result printout

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

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.

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);
    }
}

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.

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:

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:

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

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

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

Below template inspired by known article ⭐LINK

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:

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.

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 Shortest path from source to all vertices in given graph + code Really nice explanation of Dijkstra`s algorithm Really good article about algorithm + java implementation

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.

Dynamic connectivity problem

Union find

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

• Find query

  • check if two objects are in the same component

• Union command

  • Replace components containing two objects with their union

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

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

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

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)

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

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

Percolation

Useful math

$1 + 2 + 3 + ... + n = {n(n+1) \over 2 }$

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

$\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)

  • first non repeating character

• Single number among others being twice

  • This is non optimal solution. The better is here.

• Is a number a power of two

  • There is a better solution here. With explanation is the comment.

• Robot return to origin. 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.

• Sum of the tree path matches an expected value.

• Return element from array and return new length.

• Lowest common ancestor of BST

• Jewels and stones. How many chars from one string are contained in another string.

• Most frequent word in string except banned words

• K closest points to origin

• Best time to buy and sell stock II

• Climbing stairs