DSA learning and practice

                       

Please use the discussions tab for any queries. <br> <br> Use the index given below to search for problems and solutions. Problems are arranged in non-descending order of difficulty. <br> <br>

💢 Index

<details open> <summary><b>Theory</b></summary> <br>

• Introduction<br>
• Big-O Notation <br>

</details> <details open> <summary><b>Data Structures</b></summary> <br>

• Arrays<br>
• Linked Lists<br>
• Stacks<br>
• Queues<br>
• Heaps (Prority queues)<br>
• Trees<br>
• Tries (Prefix trees)<br>
• Graphs <br>

</details> <details open> <summary><b>Algorithms</b></summary> <br>

• Dynamic programming
• Binary Search
• Sliding Window
• Depth First Search
• Breadth First Search
• Strings
• Two pointers
• Bit manipulation
• Backtracking <br>

</details> <details open> <summary><b>Extra</b></summary> <br>

• CodeChef DSA learning series
• Miscellaneous/Uncategorized Problems
• Love Babbar 450 questions DSA sheet <br>

</details> <br> <br>

💢 Introduction

<details> <summary><b>What is data structure(DS)?</b></summary> <br>

• A way of organizing data, so it can be used effectively

</details> <details> <summary><b>Why do we use them?</b></summary> <br>

• To create fast and powerful algorithms
• To make code easier for understanding <br>

</details> <details> <summary><b>What is abstract data type(ADT)?</b></summary> <br>

• An abstraction of a DS which provides only an interface. An interface is not specific to any programming language, instead, it's completely free of all of them.
• ADTs are implemented using data structures <br>

Some examples are :

| # | ADT | Implementation(DS) | |:-----:| --------------- | ----------- | | 1 | Lists | Dynamic Array <br> Linked List | | 2 | Queue | Array based queue <br> Stack based queue <br> Linked List based queue | | 3 | Maps | Hash table <br> Tree | <br>

</details> <br/> <div align="right"> <b><a href="#-index">⬆️ Back to Top</a></b> </div> <br/>

💢 The Big-O Notation

<details> <summary><b>What is Big-O and why do we use it?</b></summary> <br>

Big-O notation helps us identify the time and space complexity of an algorithm. There are many other notations as well, like, Big-Theta, or, Big-Omega, but we use Big-O because it deals with the worst case scenario of an algorithm, i.e., when the size of input tends to infinity.<br>

Size of input is denoted by 'n'. <br>

</details> <details> <summary><b>Ascending order of complexity</b></summary> <br>

| # | Notation | Name | Example (time) | |:-----:|---------------| ----------- | ----------- | | 1 | O (1) | Constant | Accessing an array | | 2 | O (log n) | Logarithmic | Binary search | | 3 | O (n) | Linear | Traversing an array | | 4 | O (n log n) | Linearithmic | Merge sort | | 5 | O (n^2) | Quadratic | 2 Nested loops | | 6 | O (n^3) | Cubic | 3 Nested loops | | ... | | | | | 7 | O (nm) | O of n m | Iterating over a matrix of (n X m) | | ... | | | | | 8 | O (b^n) | Exponential | All subsets of a set -> O (2^n) | | 9 | O (n!) | Factorial | All permutations of a string |

</details> <br/> <div align="right"> <b><a href="#-index">⬆️ Back to Top</a></b> </div> <br/>

💢 Arrays

<details> <summary><b>Property</b></summary> <br>

• Each and every element is indexable(can be referenced with a number) from range 0 to n-1. 'n' is the size of array. <br>

</details> <details> <summary><b>Used</b></summary> <br>

• for sorting
• to access sequential data
• as buffer by I/O routines
• as lookup / inverse lookup tables
• to return multiple values from a function
• as cache in dynamic programming <br>

</details> <details> <summary><b>Types of arrays</b></summary> <br>

• Static : fixed length<br>
• Dynamic : variable length; implemented using static array; when size capacity is reached, a new static array of double size is created and elements are copied. <br>

</details> <details open> <summary><b>PROBLEMS on arrays</b></summary> <br>

Key : 🟢 Easy, 🟡 Medium, 🔴 Hard

<br>

 

| ID | Title | Solution | Time | Space | Difficulty | Tags | Note | |:-----:|-------|:----------:|:------:|:------------:|:------------:|-------|------| | 1929 | Concatenation of array | C,<br>C++ |||🟢||| | 1920 | Build array from permutation | C,<br>C++ |||🟢||| | 0989 | Add to array-form of integer | C++ |||🟢||| | 1480 | Running sum of 1D array | C,<br>C++ |||🟢||| | 1672 | Richest customer wealth | C++ |||🟢||matrix| | 0566 | Reshape the matrix | C++ |||🟢||| | 0867 | Transpose matrix | C++ |||🟢||| | 1470 | Shuffle the array | C++ |||🟢||| | 0532 | K-diff pairs in an array | C++ |||🟢||| | 1200 | Minimum absolute difference | C++ |||🟢||| | 1217 | Minimum cost to move chips to the same position | C++ |||🟢||| | 1431 | Kids with greatest number of candies | C++|||🟢||| | 1512 | Number of good pairs | C++ |||🟢||bruteforce,<br> hash table| | 1365 | How many numbers are smaller than current number | C++ |||🟢| |frequency array| | 1413 | Minimum value to get positive step by step sum | C++ |||🟢||| | 0448 | Find all numbers disappeared in an array | C++ |||🟢||| | 0941 | Valid mountain array | C++ |||🟢||| | 0706 | Design hashmap | C++ |||🟢||| | 1528 | Shuffle string | C++ |||🟢||| | 0219 | Contains duplicate II | C++ |||🟢||| | 1491 | Average salary excluding the minimum and maximum salary | C++ |||🟢||| | 0136 | Single number | C++ |||🟢||| | 1332 | Remove palindromic subsequences | C++ |||🟢||| | 1720 | Decode XORed array | C++ |||🟢||XOR property| | 0169 | Majority element | C++ |||🟢||Moore's Voting algo| | 1313 | Decompress run-length encoded list | C++ |O(n^2)||🟢||| | 1389 | Create taget array in the given order | C++ |O(n)||🟢||| | 1773 | Count items maching a rule | C++ |||🟢||| | 1588 | Sum of all odd length arrays | C++ |||🟢||| | 1656 | Design an ordered stream | C++ |||🟢||| | 1662 | Check if two atring arrays are equivalent | C++ |||🟢||| | 1684 | Count the number of consistent strings | [C++](./C++/LeetCode