Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algorithms - Coggle Diagram

- - - - have the smallest value at the root node. The smallest value has the highest priority to be removed.
    - - have the largest value at the root node. The largest value has the highest priority to be removed.
  - - - Unlike binary search trees, heaps may contain duplicate values.
  - - - However, pushing and popping from a heap is more complicated, but can still be accomplished efficiently with a time complexity of O(log n)
  - - - If we build our heap of size n by pushing each element one-by-one, this would also run in O(n log n) time. But there is actually a more efficient algorithm know as heapify, which allows us to perform this operation in O(n) time.
- - - - A similar approach can be taken with BSTs. We know all nodes to the left are smaller than our current node and all nodes to the right are greater than our current node. Thus, recursively search the right subtree if our target is greater than the current node and the left subtree if our target is smaller.
        If we reach the node with the target value, we will return true. Otherwise, we return false.
        
        Algorithm
        
        If we reach a null node, we return false because the target does not exist in the current tree.
        
        If the target is greater than the current node, we search the right subtree.
        
        If the target is less than the current node, we search the left subtree.
        
        If the target is equal to the current node, we return true.
        
        In part 2 and 3, we recursively call the function with the left or right child of the current node. The return value of the recursive call is the return value of the current function call as well.
        Part 1 and 4 are the base cases of the recursion. If we reach a null node, we return false because the target does not exist in the current subtree. If the target is equal to the current node, we return true.
  - - - In a balanced tree, we can eliminate half the nodes each time, which results in O(log n), for reasons we discussed in the merge sort and binary search lessons.
        
        In the worst case we have a skewed tree, where the height of the tree is equal to the number of nodes. In this case, the time complexity will be O(n)
  - - - If we have a BST [4], and wish to insert 6, this could be done in two different ways
        
        1. [4, null] where the root is 4 and right child is 6
        
        2. [6,4,null] where the root is 6 and left child is 4
        
        Both of these ara valid BSTs. In first example, we added the 6 as a leaf node, which is an easier process than the second example.
        
        Let's add 5 to this scenario tree [4,null,6], which results in [4,null,6,5,null]
        
        In resume the code will follow this
        
        If the current node is null, we return a new node with the value val.
        
        If the value is greater than the current node, we recursively call the function with the right child of the current node.
        
        If the value is less than the current node, we recursively call the function with the left child of the current node.
        
        We return the current node after the recursive call
        
        Notice that:
        
        We return a new node if the current node is null. This is how we add a new node to the tree. Even in the recursive case, we return the current node after the recursive call.
        
        The return values from the recursive calls are assigned to either the left or right child of the current node. This is how we maintain the tree structure.
        
        The time complexity of this operation is O(log n) if the tree is balanced. This is because we will continue until we reach a leaf node and thus the number of nodes we visit is proportional to the height of the tree.
  - - - Imagine the following tree: [4,6,5,null,7,null,3,2,null]
        
        Case 1 - The target has one or no children
        
        If we wish to delete node 2, which has no children, the left child pointer of 3 now points to null
        
        If we wish to delete node 3, which has one child, the left child pointer of the root node will point to 2 instead of 3.
        
        Case 2 - The target node has two children
        
        If we wanted to delete a node with two children, say, 6, we replace the node with its in-order successor.
        
        The in-order successor is the left-most in the right subtree of the target node. Another way of looking at this it is node among all the nodes that are greater than the target node.
        
        The time complexity of inserting and removing from a BST is proportional to the height of the tree. This is because we are essentially running a binary search on the tree until we reach the target position to insert into, or the target node to remove.
        
        O(log n) if the tree is balanced. However, if the tree is unbalanced, the time complexity can be O(n) in worst case.
        
        The space complexity of these operations is O(log n) in the bestt case and O(n) in the worst case. This is because we are using recursion to traverse the tree, and the number of recursive calls is proportionalto the height of the tree.
- - - - O(n) - need to search all list
    - - O(n)
    - - O(1) - arruming you already have a reference to the node at the desired position
    - - O(1) - arruming you already have a reference to the node at the desired position
  - - - Enqueue
        
        Inserts an element to the end of the queue. If implemented with singly linked list it runs in O(1) time
      - Dequeue
        
        Removes an element from the front of the queue and returns that element. It runs in O(1) time
- - - - size cannot change once is declared
    - - Reading
        
        O(1) - Accessing one indexed element at array
      - Insertion
        
        O(n) - If is AT THE END of array, O(1)
      - Deletion
        
        O(n) - if deleting AT THE END, O(1)
  - - - Access
        
        O(1)
      - Insertion
        
        O(1) - if insertion in the middle since shifting will be required
      - Deletion
        
        O(1) - if deletion in the middle since shifting will be required
    - - Resize operation takes O(n) is not performed every time we add a new element, so, take average time of O(1)
  - - - Push
        
        O(1)
      - Pop
        
        O(1) - check if the stack is empty first
      - Peek / top
        
        O(1) - retrieves without removing
- - - - The i pointer at the element we are currently inserting into the sorted portion of the array
      - The j pointer starts off one index to the left of i
      - The goal is to find the position that arr[i] should be inserted into the sorted position of the array
        
        Continue swapping it wih arr[j] until we find the correct position
        
        After each swap we shift j to the left by 1
        
        Stop once the element is greater than or equal to the element to its left
    - - Insertion sort is stable, meaning that it is guaranteed that the relative order will remain the same
    - - TIME
        
        O(n) - this is the best case scenario where the input array is already sorted and the inner loop will never execute
        
        O(n^2) - In the worst case scenario, because the inner loop will execute n times for each element in array
        
        O(n^2) - If the array is in random order, the time complexity is still this in the avg case
      - SPACE
        
        An in-place sorting algorithm. This means that the space complexity is O(1) since no additional data structures are used
  - - - Recursively call mergeSort() on the right half of thw array. Do this by passing pointers m + 1 and e to the function, which in this case represent the start and end of the right half of the array
        
        Merge the two sorted halves by calling the merge() function
        
        For merge() we have three pointers K, J and I
        
        k - keeps track of where the next element in arr needs to be placed
        
        i - points to the element in the leftSubArr that is currently being compared to the j element in the rightSubArr
        
        One of i or j will increment depending on which element in smaller
        
        k will increment regardless because arr will have an element placed inside of it regardless of which one of i or j increments
    - - Merge Sort proves to be a stable algorithm. This is because when we compare the ith element in the left subarray to the jth element in the right subarray for equality, we pick the one in the left subarray, maintaining the relative order. Recall the following pseudocode from the merge() subroutine.
    - - TIME
        
        O(nlogn) - Merge will take n steps because at any level of the tree, we have n elements to compare and sort, where n is the length of the original array. To get the final time complexity we multiply the number of levels in the recursion tree by the cost of each level (logn)
        
        This means we have log n levels in out recursionn tree and the cost of each level is dependent of the merge() function
  - - - Picking a pivot value
        
        Pick the first index
        
        Pick the last index
        
        Pick the median (pick the first, last and the middle value and find their median and peform the split at the median)
        
        Pick a random pivot
        
        Ideally we can pick a pivot that would divide the array into two roughly equal halves. This would result in the most efficient sorting scenario
        
        Once we pick a pivot will partition the array such that all element less than or equal to the pivot are on the left and the rest are on the right
        
        We will then recursively run quicksort on the left and right halves until we hit the base case which is an array of size 1
        
        Unlike merge sort, there is no need to merge the two halves because the partitioning step itself is enough to sort the array.
        
        In some sense, quick sort is the opposite of merge sort. Merge sort has a simple recursive step, but the complexity is in handling the merging of the two halves. Quick sort has a complex recursive step, but the complexity is in the partitioning step.
        
        There is also a variation of Quicksort called randomized Quicksort, where the pivot is picked randomly, or the array is shuffled if you like, and this reduces the chance of hitting the worst case.
        
        This results in O(nlogn) in the worst case instead of the typical implementation where it is O(n^2)
    - - Quicksort is not a stable algorithm because it exchanges non-adjacent elements.
    - - TIME
        
        The partition step takes O(n) time and we do this for every level of recursion tree. The number of levels in the recursion tree is O(logn), but only in the best case
        
        The best case is that we pick a pivot such that we can always perform the partition in the middle. If the array is perfectly partitioned in the middle every single time and the pivot is the median, it is possible to keep getting O(nlogn) as the ultimate result
        
        Continuosly picking a pivot where the pivot element is the smallest or the largest element will result in the worst case performance of O(n^2). This is because our partitioning will not be effective and we will end up with a partition of size n-1 and 0 respectively, making the height of our recursion tree n
- - - - The idea is we pick a direction, say left, and keep following pointers as far down left as we can go until we reach null. Once we reach null, we backtrack to the parent node and then go right. We keep doing this until we have visited every node in the tree. This is the essence of depth-first search.
  - - - Inorder
        
        An inorder traversal will recursively visit all the nodes in the left subtree, then visit the parent node and finally visit all the nodes in the right subtree. In this case, "visit" could mean anything from printing the node to performing some operation on it.
        
        The order in which these nodes will be visited is [2,3,4,5,6,7], which is sorted. It is important to note that an inorder traversal will only print the nodes in a sorted order if the tree is a binary search tree.
        
        The reason the nodes will print in a sorted order is because of the BST property. Since we know all values to the left of a node are smaller, this means we won't hit our base case until we reach the left-most node which is also the smallest node. After visiting this, we will traverse up, visit the parent and then visit the right-subtree. The visual below shows this process.
      - 2. Preorder
        
        Alternatively, preorder traversal will visit the parent node first, then visit the left subtree and finally visit the right subtree.
        
        The nodes are visited in the following order [4,3,2,6,5,7]
      - 3. Postorder
        
        A postorder traversal will visit the left subtree, then the right subtree and finally the parent node last.
        
        The order in which these nodes will be visited is: [2,3,5,7,6,4]
  - - - It´s O(n), because we will visit all nodes.
    - - It´s O(h), where h is the height of the tree, which would be O(log n) for balanced binary tree or O(n) for a skewed tree.
- - - - Generally, BFS is implemented iteratively and that is the implementation we will be covering in this course. Since we want to visit all the nodes on one level before moving to the next, we will need a data structure that allows us to do this.
        
        A queue data structure, more specifically, a deque, allows us to remove elements both from the head and the tail in O(1) time. For BFS we will append elements to the tail and remove elements from the head as we go through each level of the tree from left to right.
  - - - Is O(n) where n is the number of nodes in the tree. This is because we visit every node exactly once.
    - - Is O(n) where n is the number of nodes in the tree. This is because we store an entire level of the tree in the queue at a time. In the worst case the last level may roughly half the size of the tree.
- - - - Given that the tree has n nodes, the time complexity will be O(n) because in the worst case we may need to visit all the nodes in the tree.
    - - The space complexity is O(h) where h is the height of the tree. his is because we are using recursion and the maximum depth of the recursion is the height of the tree. We are also storing the nodes along the path in the path list, which will have a maximum of O(h) elements at any given time.
- - - - Typically we are given an array, and a target element to search for
      - Similar to how we would search for a word in a dictionary: open it in the middle and determine if the word we are looking for is in the left or right half
      - Divides a given array by the middle index [(l + (r - l))/2] and compares the value at mid to the target value. if the target is greater than the mid value, we will search the right half of the array. if the target is less than the mid value, we will search the left half of the array.
    - - A range of numbers is given rather than an array, without a specific target
        
        Imagine you picked a number from 1-100 and asked your friend to guess the number you were thinking of. There are three outcomes. Either their guess is correct, too small or too large.
        
        After every guess, you would tell them if their guess was correct, too small or tool large. Your friend would then adjust their next guess accordingly.
    - - 1. Set two pointers, L and R, to the left-most and right-most indices of the array respectively
        
        2. Calculate the mid index by adding L + R pointers and dividing the result by 2. This is the middle of our seach space.
        
        3. Compare the value at middle index to the target value. Either we wil find the target at the mid index, or we will determine if the target is in the left or right half of the remaining search space. At each step, we will eliiminate half of the search space.
      - Search Range
        
        At its core, this is a binary search problem. As long as there is a way to determine if the number is too big, too small or correct, we can adjust the search space accordingly.
        
        In many problems, comparing the guess to the target is done by a predefined function or some math equation. For example, in this problem assume we are given a function isCorrect(n) that returns 1 if n is too big, -1 if n is too small and 0 if n is correct.
        
        This technique can be confusing and can come across as very subtle because you have to figure out how to modify the typical implementation of binary search. For questions like these, a predefined method API is given, in this case, isCorrect and you are required to treat the function as a black-box and use it within your own binary search method.
  - - - Thus we end up with the same formula where x is the number of times we can divide the array in half until we reach an array of size 1
      - 1 = n / 2^x
        
        After solving for x, we get x = log(n)
        
        O(log n)
- - - - If a node does not have any children, it`s classified as leaf node. if a node has even a single child, either left or right, it would be classified as a non-leaf node.
        
        Unlike linked lists, binary tree node pointers can only point in one direction. As such, cycles are not allowed in binary trees. Mathematically speaking, a binary tree is a connected, undirected graph with no cycles. This means that a leaf node is always guaranteed to exist.
  - - - Is the highest node in the tree and has no parent node. All of the nodes in the tree can be reached by the root node.
    - - Are nodes with no children. The nodes at the last level of the tree are guaranteed to be leaf nodes but they can also be found on other levels.
    - - The children of a node are its left child and right child.
    - - Is measured from the root node all to way to the lowest leaf node, just like the height of anything in real life. The height of a single node tree is just 1, if the node itself is counted, or 0 if not.
        
        Sometimes, the height is counted by the number of edges that are in between the nodes instead of the nodes themselves. Using this method, the height will be n-1 where the n is the number of nodes, in the path from the root to lowest leaf.
        
        The maximum height of the given binary tree is 3. Alternatively, if we were counting by edges, instead of nodes, it would be 2.
    - - Is measured from itself all the way up to the root As observed. the depth at the root node is 1, with it increasing as we go down. Measure depth at a given node by looking at how many nodes are above it, including the node itself.
    - - A node connected to all of the nodes below if is considered an ancestor to those nodes. For example, the root node is an ancestor to all of the nodes in tree.
    - - Is either child of the node or child of some other descendent of the node.