Welcome to the Data Structures and Algorithms (DSA) repository! This repository is dedicated to providing a collection of DSA problems and their solutions in a clear and well-documented format.
For me great algorithms are the poetry of computation. Just like verse, they can be terse, allusive, dense and even mysterious. But once unlocked, they cast a brilliant new light on some aspect of computing.
- Francis Sullivan
Big O is a mathematical notation commonly used to describe the impact on time or space as input size n increases. We are mostly interested in discussing the worst case of an algorithm, but it is also beneficial to compare algorithms in their average and best case scenarios. Seven Big O notations commonly used in algorithm complexity analysis are discussed in the following sections.
[Figure 1] Schematic diagram of Big O for common run times from fastest to slowest.
O(1) O(Log n) O(n)
▲ ▲ ▲
│ │ │
│ │ │ .
│ │ │ .
│ │ │ .
│ │ │ .
│ │ │ .
t│ t│ ... t│ .
│ │ ......... │ .
│ │ ...... │ .
│ │ ..... │ .
│ │ ... │ .
│......................... │ .. │ .
│ │. │.
└────────────────────────► └────────────────────────► └────────────────────────►
n n n
O(n*Log n) O(Log 2^n) O(2^n)
▲ . ▲ . ▲ .
│ .. │ . │ .
│ . │ . │ .
│ . │ . │ .
│ . │ . │ .
│ . │ . │ .
│ .. │ . │ .
t│ .. t│ . t│ .
│ .. │ . │ .
│ .. │ . │ .
│ .... │ . │ .
│ . . . │ .. │ .
│ ..... │ ... │ .
│... │... │..
└────────────────────────► └────────────────────────► └────────────────────────►
n n n
O(n!)
▲ .
│ .
│ .
│ .
│ .
│ .
│ .
t│ .
│ .
│ .
│ .
│ .
│.
└────────────────────────►
n
- This figure is taken from Complexity Analysis by @Spring1843
To understand the big O notation, let us focus on time complexity and specifically examine the O(n) diagram. This diagram depicts a decline in algorithm performance as the input size increases. In contrast, the O(1) diagram represents an algorithm that consistently performs in constant time, with input size having no impact on its efficiency. Consequently, the latter algorithm generally outperforms the former.
However, it is essential to note that this is not always the case. A O(1) algorithm with a single time-consuming operation might be slower than a O(n) algorithm with multiple operations if the single operation in the first algorithm requires more time to complete than the collective operations in the second algorithm.
The Big O notation of an algorithm can be simplified using the following two rules:
- Remove the constants.
O(n) + 2*O(n*Log n) + 3*O(K) + 5is simplified toO(n) + O(n*Log n) + O(K). - Remove non-dominant or slower terms.
O(n) + O(n*Log n) + O(K)is simplified toO(n*Log n)becauseO(n*Log n)is the dominant term.
| Data Structure / Algorithm | Time Complexity (Average / Worst Case) | Space Complexity |
|---|---|---|
| Data Structures | ||
| ---------------------------------- | ---------------------------------------- | -------------------- |
| Array | Access: O(1), Search: O(n), Insert: O(n) | O(n) |
| Linked List (Singly/Doubly) | Access: O(n), Search: O(n), Insert: O(1) | O(n) |
| Stack | Access: O(n), Search: O(n), Insert: O(1) | O(n) |
| Queue (Array-based) | Access: O(1), Search: O(n), Insert: O(1) | O(n) |
| Queue (Linked List-based) | Access: O(1), Search: O(n), Insert: O(1) | O(n) |
| Hash Table | Insert/Delete/Search: O(1) (amortized) | O(n) |
| Binary Search Tree (BST) | Average: O(log n), Worst: O(n) | O(n) |
| AVL Tree (Balanced BST) | Insert/Delete/Search: O(log n) | O(n) |
| Heap (Binary, Max/Min) | Insert/Delete: O(log n), Max/Min: O(1) | O(n) |
| Trie | Insert/Search/Delete: O(L) (L is length) | O(ALPHABET_SIZE * L) |
| Graph (Adjacency Matrix) | Access: O(1), Search: O(V^2), Space: O(V^2) | O(V^2) |
| Graph (Adjacency List) | Access: O(V + E), Search: O(V + E) | O(V + E) |
| ---------------------------------- | ---------------------------------------- | -------------------- |
| Algorithms | ||
| ---------------------------------- | ---------------------------------------- | -------------------- |
| Linear Search | O(n) | O(1) |
| Binary Search | O(log n) | O(1) |
| Merge Sort | O(n log n) | O(n) |
| Quick Sort | Average: O(n log n), Worst: O(n^2) | O(log n) |
| Depth-First Search (DFS) | O(V + E) | O(V) |
| Breadth-First Search (BFS) | O(V + E) | O(V) |
| Dijkstra's Algorithm | O(V^2) (with matrix), O((V + E) log V) (with min heap) | O(V) |
| Floyd-Warshall Algorithm | O(V^3) (with matrix) | O(V^2) |
| Binary Tree Traversal (in-order, pre-order, post-order) | O(n) | O(h) (h is the height) |
| Traveling Salesman Problem (TSP) | O(n!) (Brute Force) | O(n) |
| ---------------------------------- | ---------------------------------------- | -------------------- |
You can easily run the tests for this project using Jest, a JavaScript testing framework.
Before running the tests, make sure you have installed the required packages. To install the required packages, run below command:
npm installTo run all the tests in the project, execute the following command in your terminal:
npm testThe below table includes all the questions, which I have solved.
| S.No | Questions |
|---|---|
| 1 | First and last occurrence of element) |
| 2 | Peak index in a mountain array) |
| 3 | Pivot in rotated sorted array) |
| 4 | Search in rotated sorted array) |
| S.No | Pattern | Level | Questions |
|---|---|---|---|
| 1 | Two Pointers | Easy | Merge Two Sorted Lists |
| 2 | Two Pointers | Easy | two Sum |
| 3 | Two Pointers | Easy | Squares of a Sorted Array |
| 3 | Two Pointers | Easy | Squares of a Sorted Array |
| 4 | Two Pointers | Easy | Backspace String Compare |
| 5 | Two Pointers | Easy | Moves Zeroes |
| 6 | Two Pointers | Easy | Is Subsequence |
| 7 | Two Pointers | Medium | Find the duplicate numbers |
- Alogrithms - Part 1 By Coursera
- Alogrithms - Part 1 By Coursera
- Master the Coding Interview: Data Structures + Algorithms
- Strivers A2Z DSA Course/Sheet
- Study Guide by Subjects
- 14 Patterns to Ace Any Coding Interview Question
- Comprehensive Data Structure and Algorithm Study Guide
- Object Oriented Programming
- Visualizing DSA through Animation
This repository is dedicated to Data Structures and Algorithms (DSA) problems and their solutions. It provides a collection of well-documented DSA problems with clear explanations and code samples.
The solutions are primarily provided in TypeScript, a statically typed superset of JavaScript. However, you can often adapt the concepts and logic to other programming languages.
You can use the table of contents (TOC) at the beginning of this README to jump to specific sections. Each problem is listed with a link for easy access.
Absolutely! We welcome contributions from the community. If you have new problems to add, improvements to existing solutions, or suggestions for better explanations, please feel free to open a pull request.
Yes, we have listed some additional resources in the "Other Resources" section. These include online courses and sheets that can help you deepen your understanding of DSA.
We recommend starting with the "Questions" section, where you'll find a variety of problems to solve. Begin with the ones that match your skill level and gradually work your way up.
Basic knowledge of programming and data structures is helpful, but even if you're new to DSA, you can use this repository as a learning resource. The problems are organized from easy to more challenging.
If you encounter issues with the code or have questions about specific problems, feel free to open an issue in this repository. The community and maintainers will be happy to assist you.
Yes, this repository is open-source and available under the License mentioned in this README. Please review the license terms before using or contributing to the repository.
This project is licensed under the MIT License - see the LICENSE file for details.