Definitions

Akhil Singh Chauhan
Creator

General algorithms/techniques

Recursion

• A recursive algorithm is one that calls itself to solve smaller instances of the same problem, ultimately reaching a base case that can be solved directly.
• It breaks down a problem into subproblems until a simple, solvable case is reached, then combines the solutions to build the solution for the original problem.
• Defining a problem in terms of itself, often leading to elegant and concise solutions.

  %%{init: {"themeVariables": {"fontSize":"18px"}, "flowchart": {"curve": "monotoneY"}} }%%
  flowchart TD
    Start((Start)):::start e1@==> CallFunc{"Is Base Case?"}:::decision
    CallFunc e2@==>|Yes| BaseCase(["Return Result (Base Case)"]):::endClass
    CallFunc e3@==>|No| Recurse["Call function<br>again with<br>simpler input"]:::recurse
    Recurse e4@==>|Recursive Call| CallFunc
    BaseCase e5@==> Output["Result unwinds<br>back through calls"]:::output

    classDef animate stroke-dasharray: 9,5,stroke-dashoffset: 900,animation: dash 10s linear infinite;

    class e1,e2,e3,e4,e5 animate;

    classDef start fill:#8ead52,stroke:#16634d,stroke-width:2px;
    classDef decision fill:#ffb9009c,stroke:#b07a29,stroke-width:2px;
    classDef recurse fill:#19f6f98f,stroke:#7fa0f77a,stroke-width:2px,font-style:italic;
    classDef returnNode fill:#bdf7b7,stroke:#24581c,stroke-width:2px;
    classDef output fill:#b44adc8c,stroke:#8150ae,stroke-width:2px,font-style:italic;

    class Start start;
    class CallFunc decision;
    class ReturnNode returnNode;
    class Recurse recurse;
    class Output output;

Dynamic Programming

• Breaking down a problem into overlapping subproblems and storing solutions to avoid recomputation.

%%{init: { 'securityLevel': 'loose', 'theme': 'default', 'flowchart': {'curve': 'monotoneY'}}}%%
  flowchart TD
      A[Original Problem] e1@==> B{Is Subproblem Solved?}
      B e2@==>|No| C[Break Down into Subproblems]
      C e3@==> D[Solve Subproblem]
      D e4@==> E[Store Solution in Memory]
      E e5@==> F[Use Stored Solution]
      B e6@==>|Yes| F
      F e7@==> G[Solve Original Problem Efficiently]

      classDef animate stroke-dasharray: 5,3,stroke-dashoffset: 900,animation: dash 10s linear infinite;

      class e1,e2,e3,e4,e5,e6,e7 animate;

      %% Animation Hints
      click A "javascript:void(0)" "Start with the main problem"
      click B "javascript:void(0)" "Check if subproblem was solved"
      click C "javascript:void(0)" "Divide into overlapping subproblems"
      click D "javascript:void(0)" "Solve the required subproblem"
      click E "javascript:void(0)" "Store the solution to avoid recomputation"
      click F "javascript:void(0)" "Reuse stored result"
      click G "javascript:void(0)" "Problem solved efficiently!"

Divide & Conquer

• A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

Greedy Algorithms

• Making locally optimal choices at each step with the hope of finding a global optimum.

Backtracking

• Incrementally building solutions, exploring all possible paths, and abandoning invalid ones.

Arrays & Strings

Subsequence

• A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Substring

• A substring is a contiguous non-empty sequence of characters within a string.

Palindrome

• A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Monotonic

• Elements are entirely non-decreasing or non-increasing

Circular Array

• Array where the end connects to the beginning

Partition

• Dividing array into parts based on specific criteria

Kadane's Algorithm

• Technique to find maximum subarray sum subarray

Two Pointers

• Using two index pointers to solve array problems

Sliding Window

• Technique of maintaining a window that slides through an array

Prefix Sum

• Array where each element is sum of all previous elements

Suffix Sum

• Array where each element is sum of all elements after it

Rotation

• Shifting array elements by a certain offset

In-place

• Algorithm that transforms input without creating another data structure

Anagram

• An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

Lexicographic Order

• Dictionary Ordering of Strings

Array Operations Time Complexity

Heap & Priority Queue

Min Heap / Max Heap

• Tree-based data structure where parent is smaller/larger than children

Heap Sort

• Sorting algorithm using a heap

Priority Queue

• Abstract data type providing efficient access to the minimum/maximum element

Heapify

• Process of creating a heap from an array

K-Way Merge

• Merging k sorted arrays/lists (often using heaps)

Build Heap

• The process of running heapify() on the entire heap to create a valid heap

Two Heaps

• A technique used to find the median of a data stream using a max and a min heap

Heap Operations Time Complexity

Backtracking

Subsets

• Set A is a subset to Set B if all of its elements are found in Set B

Combinations

• Number of ways of selection and arrangement of items where order does not matter

Permutations

• Number of ways of selection and arrangement of items where order matters

Pruning

• Used to eliminate branches early on that can never lead to valid solutions

Constraint

• A condition that must be satisfied to reach a valid solution

Base Case

• Determines when a valid solution has been found

Candidate Solution

• Start from the final problem and recursively break it into smaller subproblems

Unique Combination

• Two combinations are unique if the frequency of chosen numbers is not the same

Dynamic Programming

Memoization

• Cache technique to avoid redundant calculations

Tabulation

• Bottom-up approach using arrays to store subproblem results

State

• Snapshot of progress you've made in solving the larger problem

Overlapping Subproblems

• When the same subproblems are solved multiple times

1-Dimensional

• The result for the current state only depends on one previous state or a linear history, e.g. Fib

2-Dimensional

• The problem depends on two varying factors, often two strings, two sequences, or two indices

Top Down

• Start from the final problem and recursively break it into smaller subproblems

Bottom Up

• Build the solution from the base case all the way up to the final solution

Longest Common Subsequence (LCS)

• Finding the longest subsequence common to two sequences

Longest Increasing Subsequence (LIS)

• Finding the longest subsequence where elements are in ascending order

0 / 1 Knapsack

• Pick items such that profits associated with them are maximized.
• Each item can be picked at most once

Unbounded Knapsack

• Pick items such that profits associated with them are maximized.
• Each item can be picked unlimited times

Tree

Binary Tree

• Tree where each node has atmost two children

Binary Search Tree (BST)

• Binary tree where left child value < parent value < right child value

Complete Binary Tree

• Every level filled except possibly last, which is filled left to right

Perfect Binary Tree

• All internal nodes have exactly two children and all leaf nodes are at same level

Balanced Tree

• Height difference between left and right subtrees is limited and (often \(\leq\) 1)

Self Balancing Tree

• Automatically maintains balance after insertions/deletions (e.g., AVL, Red-Black)

Traversal

• Methods to visit all nodes (preorder, inorder, postorder, level-order)

Lowest Common Ancestor (LCA)

• Deepest node that is an ancestor of two given nodes

Serialization/ Deserialization

• Converting a tree to/from a string representation

• Serialization: Converting a tree to a string.

• Deserialization: Converting a string back into a tree

• Example: "1, 2, 4, null, null, 5, null, null, 3, null, null", where null indicates a null node.

Diameter

• The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Length of Path

• The length of a path between two nodes is represented by the number of edges between them.

Depth

• A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Level Order

• Processing tree nodes level by level

Segment Tree

• Data structure for range queries

BFS (Breadth First Search) aka Level Order Traversal

• Traversing the tree nodes level by level, often using a queue.

DFS (Depth First Search)

• Traversing the tree in a depth-first manner

• Visits nodes by exploring depth-first. Comes in three orders:

• Preorder: node → left → right (NLR)

• Inorder: left → node → right (LNR)
• Postorder: left → right → node (LRN)

Graphs

Directed / Undirected

• Edges with/without direction

Weighted / Unweighted

• Edges with/without values - known as weights

Connected Component

• Subset of vertices where any two vertices are connected by a path

Strongly Connected Component (SCC)

• In a directed graph, subset where every vertex is reachable from every other

Bipartite Graph

• Can be divided into two sets with no edges within each set

DAG (Directed Acyclic Graph)

• Directed graph with no cycles

Topological Sort

• Linear ordering of vertices where for every edge (u,v), u comes before v. Works with DAGs

Adjacency List

• Graph representation derived from an array of edges

BFS/DFS

• Breadth-First Search and Depth-First Search traversal strategies

MST (Minimum Spanning Tree)

• Tree connecting all vertices with minimum total edge weight

Bellman-Ford / Dijkstra / Floyd-Warshall

• Shortest path algorithms

Union-Find

• Data structure for disjoint sets operations

Cycle Detection

• Algorithms to find cycles in graphs

A* Algorithm

• Best-first search algorithm for path finding

Miscellaneous

Amortized Analysis

• Analyzing average performance over a sequence of operations

Randomized Algorithm

• Algorithm that uses random numbers to decide next step

Skip List

• Probabilistic data structure for efficient search

Execution Time

• The raw time taken in seconds to execute an algorithm

Stable Sorting Algorithm

• A sorting algorithm that maintains the relative order of elements after sorting

Unstable Sorting Algorithm

• A sorting algorithm that does not maintain the relative order of elements after sorting