DataStructures_and_Algorithms
Notes from CSC236, 263, 373 and also the LeetCode journey!
Table of Contents:
- Abstract Data Type and Data Structure
- Runtime Notation
- Divide and Conquer
- Tree
- Priority Queue
- Hashing
- Sorting Algorithms
- Stack and Queue
- Monotonic Stack
- Graphs
- Dijkstra's Algorithm
- Minimum Spanning Tree
- Disjoint Set
- Greedy Algorithm
- Dynamic Programming
- Shorest Weight Path (Dijkstra Algorithm)
- Bitmask and Bit Manipulation
- Fenwick Tree (Binary Indexed Tree)
- Trie
- Linked List
- Array
- Backtracking
- Math
- Prefix Sum
- Topological Sort
- Top Questions from Microsoft
- Two Pointers
- Neetcode.io
- Abstract Data Type: is the set of objects together with operations.
- i.e. Stack, Queue, Priority Queue
- Data Structure: is the implementation of an ADT.
- i.e. We can use List or LinkedList to implement Queue
- Big O: upper bound, worst case, argue that algorithm executes no more than c * g(n) steps on every input of size n.
- Big Omega: lower bound, best case, find one input on which algorithm executes at least c * g(n) steps.
- Notes
- Examples:
- Merge Sort
- Find Smallest Not Belong To List
- Binary Search
- Bisect Left
- Bisect Right
- Find Peak Element
- Divide Chocolate
- Shortest Distance to Target Color
- Longest Increasing Subsequence
- Different Ways to Add Parentheses
- Split Array Largest Sum
- Range Module
- Minimize the Maximum Difference of Pairs
- Search in Rotated Sorted Array II
- Find First and Last Position of Element in Sorted Array
- Find in Mountain Array
- Minimum Number of Days to Make m Bouquets
- Magnetic Force Between Two Balls
- Find Kth Smallest Pair Distance
- Minimized Maximum of Products Distributed to Any Store
- General Notes
- Examples:
- Is Balanced Binary Tree
- Binary Tree Level Order Traversal
- BST to Balanced BST
- Find a Corresponding Node of a Binary Tree in a Clone of that Tree
- Find All the Lonely Nodes
- Kill Process
- Binary Tree Vertical Order Traversal
- All Nodes Distance k In Binary Tree
- Find Leaves of Binary Tree
- House Robber III
- Binary Tree Longest Consecutive Sequence II
- Average of Leaves in Binary Tree
- Vertical Order Traversal of a Binary Tree
- N-ary Tree Level Order Traversal
- Path Sum II
- Find Largest Value in Each Tree Row
- Kth Symbol in Grammar
- Count Nodes Equal to Average of Subtree
- Construct String from Binary Tree
- Binary Tree Inorder Traversal
- Leaf Similar Trees
- Amount of Time for Binary Tree to be Infected
- Maximum Difference Between Node and Ancestor
- Find Bottom Left Tree Value
- Even Odd Tree
- Count Nodes with the Highest Score
- Sum of Left Leaves
- Sum Root to Leaf Numbers
- Add One Row to Tree
- Smallest String Starting from Leaf
- Subtree of Another Tree
- Evaluate Boolean Binary Tree
- Delete Leaves with a Given Value
- Distribute Coins in Binary Tree
- Find the Maximum Sum of Node Values
- Delete Nodes And Return Forest
- Binary Tree Postorder Traversal
- N-ary Tree Postorder Traversal
- Kth Largest Sum in a Binary Tree
- Cousins in Binary Tree II
- Flip Equilvalent Binary Trees
- Binary Search Tree Notes Examples:
- AVL
Examples:
- Notes
- Examples:
- Heap Implementation
- Heap Sort
- O(n) Build Heap
- Min Heap with Decrease Key
- Kth Smallest Element in a Sorted Matrix
- Maximum Performance of a Team
- Reorganize String
- The k Weakest Rows in a Matrix
- Number of Followers in Full Bloom
- Seat Reservation Manager
- Find Polygon With the Largest Perimeter
- Furthest Building You Can Reach
- Meeting Rooms III
- Maximize Happiness of Selected Children
- Kth Smallest Prime Fraction
- Minimum Cost to Hire K Workers
- IPO
- Ugly Number II
- The Number of the Smallest Unoccupied Chair
- Divide Intervals Into Minimum Number of Groups
- Smallest Range Covering Elements From K Lists
- Maximal Score After Applying K Operations
- Maximum Swap
- Notes
- Examples:
- Group Anagrams
- Four Sum II
- Diagonal Traverse
- Max Number of k-sum Pairs
- Ransom Note
- Design Underground System
- Find Duplicate File in System
- Design HashMap
- Majority Element II
- Sort Vowels in a String
- Count Nice Pairs in an Array
- Find Words That Can Be Formed by Characters
- Destination City
- Redistribute Characters to Make All Strings Equal
- Largest Substring Between Two Equal Characters
- Minimum Number of Steps to Make Two Strings Anagram
- Determine if Two Strings Are Close
- Find Players With Zero or One Losses
- Insert Delete GetRandom O(1)
- Unique Number of Occurrences
- Set Mismatch
- Sort Characters By Frequency
- Find the Town Judge
- Count Elements With Maximum Frequnecy
- Intersection of Two Arrays
- Custom Sort String
- Binary Subarrays with Sum
- Isomorphic Strings
- Largest Positive Integer That Exists With Its Negative
- Number of Ways Where Square of Number Is Equal to Product of Two Numbers
- Make Sum Divisible by P
- Longest Palindrome
- Find Common Characters
- Continuous Subarray Sum
- Subarray Sums Divisible by K
- Number of Atoms
- Create Binary Tree From Descriptions
- Make Two Arrays Equal by Reversing Subarrays
- Kth Distinct String in an Array
- Notes
- Examples:
- Merge Sort
- Quick Sort
- Reordered Power of 2
- Sort the Matrix Diagonally
- Eliminate Maximum Number of Monsters
- Minimize Maximum Pair Sum in Array
- Reduction Operations to Make the Array Elements Equal
- Divide Array into Arrays with Max Difference
- Relative Ranks
- Maximize Happiness of Selected Children
- Largest Number
- Smallest Range II
- Maximum Sum Obtained of Any Permutation
- The Number of Weak Characters in the Game
- Maximum Total Importance of Roads
- Special Array With X Elements Greater Than or Equal X
- Minimum Number of Moves to Seat Everyone
- Minimum Increment to Make Array Unique
- Most Profit Assigning Work
- Sort the People
- Sort Array by Increasing Frequency
- Sort the Jumbled Numbers
- Minimum Time Difference
- Rank Transform of an Array
- Divide Players Into Teams of Equal Skill
- Most Beautiful Item for Each Query
- Count the Number of Fair Pairs
- Notes
- Examples:
- Backspace String Compare
- Implement Stack Using Queues
- Remove All Adjacent Duplicates in String II
- 132 Pattern
- Flatten Nested List Iterator
- Longest Valid Parentheses
- Find Permutation
- Constrained Subsequence Sum
- Build an Array with Stack Operations
- Sum of Subarray Minimums
- Implement Queue using Stacks
- Minimum Remove to Make Valid Parentheses
- Maximum Nesting Depth of the Parentheses
- Make the String Great
- Valid Parenthesis String
- Number of Students Unable to Eat Lunch
- Reveal Cards in Increasing Order
- Reverse Substrings Between Pair of Parentheses
- Robot Collisions
- Design a Stack with Increment Operation
- Minimum String Length After Removing Substrings
- Notes
- Examples:
- Notes
- Examples:
- Is Bilateral (BFS)
- Jump Game IV (BFS)
- Schedule Course (DFS detects cycle)
- Populating Next Right Pointers in Each Node II (BFS)
- Deepest Leaves Sum
- Shortest Path in Binary Matrix
- Walls and Gates
- Pacific Atlantic Water Flow
- Open the Lock
- Number of Operations to Make Network Connections
- Remove Invalid Parentheses
- Shortest Path to Get All Keys
- The Maze II
- 01 Matrix
- Frog Jump
- Shortest Path Visiting All Nodes
- Bus Stops
- Out of Boundary Paths
- Find All People With Secret
- Count Sub Islands
- Island Perimeter
- Find All Groups of Farmland
- Minimum Number of Vertices to Reach All Nodes
- All Ancestors of a Node in a Directed Acyclic Graph
- Step-By-Step Directions From a Binary Tree Node to Another
- Second Minimum Time to Reach Destination
- Most Stones Removed with Same Row or Column
- Notes
- Examples:
- Notes
- Examples:
- Notes
- Examples:
- Notes
- Examples:
- Notes
- Examples:
- Scheduling Intervals
- Interval Partitioning
- Schedule Course III (Greedy Algorithm with max heap)
- Maximum Units on a Truck
- Reduce Array Size to the Half
- Split Array into consecutive Subsequences
- Minimum Number of Refueling Stops
- Bag of Tokens
- Text Justification
- Maximum Length of Pair Chain
- Group the People Given the Group Size They Belong To
- Candy
- Determine if a Cell is Reachable at a Given Time
- Maximum Element After Decreasing and Rearranging
- Maximum Number of Coins You Can Get
- Number of Ways to Divide a Long Corridor
- Minimum Time Visiting All Points
- Buy Two Cholocates
- Minimum Time to Make Rope Colorful
- Assign Cookies
- Convert an Array Into a 2D Array With Conditions
- Minimum Number of Operations to Make Array Empty
- Least Number of Unique Integers after K Removals
- Minimum Number of Arrows to Burst Balloons
- Construct Smallest Number From DI String
- Append Characters to String to Make Subsequence
- Minimum Difference Between Largest and Smallest Value in Three Moves
- Maximum Score From Removing Substrings
- Minimum Number of Pushes to Type Word II
- Minimum Number of Changes to Make Binary String Beautiful
- Prime Subtraction Operation
- Notes
- Examples:
- Rod Cutting
- Subset Sum
- Longest Palindromic Substring
- Edit Distance
- Course Schedule IV FloydWarshall
- Count Sorted Vowel Strings
- Longest Increasing Path in a Matrix
- Unique Paths II
- Coin Change
- Palindromic Substrings
- Ones and Zeroes
- Pascal's Triangle II
- Unique Paths
- Combination Sum IV
- Count Vowels Permutation
- Binary Trees with Factor
- Regular Expression Matching
- Best Time to Buy and Sell Stock with Cooldown
- Best Time to Buy and Sell Stock with Transaction Fee
- Maximal Square
- Predict the Winner
- Palindrome Partitioning II
- Partition Equal Subset Sum
- Minimum Cost for Tickets
- Best Time to Buy and Sell Stock III
- Dungeon Game
- Best Time to Buy and Sell Stock IV
- Fibonacci Number
- Longest Increasing Subsequency
- Longest Common Subsequence
- Minimum INsertion Steps to Make a String Palindrome
- Longest Palindromic Subsequence
- Decode Ways
- Word Break
- Number of Music Playlists
- Coin Change II
- Check if There is a Valid Partition For The Array
- Minimum Number of Taps to Open to Water a Garden
- Counting Bits
- Extra Characters in a String
- Count All Valid Pickup and Delivery Options
- Longest String Chain
- Champagne Tower
- Integer Break
- Build Array Where You can Find the Maximum Exactly K Comparisons
- Max dot Product of Two Subsequences
- Painting the Walls
- Number of Ways to Stay in the Same Place After Some Steps
- Knight Dialer
- Number of Dice Rolls with Target Sum
- String Compression II
- Minimum Difficulty of a Job Schedule
- Maximum Profit in Job Scheduling
- Arithmetic Slices II Subsequence
- Minimum Falling Path Sum
- Number of Submatrices That Sum to Target
- Perfect Squares
- Cherry Pickup II
- Freedom Trail
- Student Attendance Record II
- Strange Printer
- Minimum Total Distance Traveled
- Notes
- Examples:
- Notes
- Examples:
- Single Number (XOR)
- Maximum Product of Word Lengths (Bitmaks)
- Number of 1 Bits
- Maximum Length of a Concatenated String with Unique Characters
- Find Winner on a TicTacToe Game
- Cinema Seat Allocation
- Single Number II (XOR)
- Single Number III (XOR)
- Find the Duplicate Number
- Find the Difference
- Remove Duplicate Letters
- Sort Integers by the Number of 1 Bits
- Find the Original Array of Prefix XOR
- Unique Length-3 Palindromic Subsequences
- Bitwise AND of Numbers Range
- Minimum Number of Operations to Make Array XOR Equal to K
- Score After Flipping Matrix
- Sum of All Subset XOR Totals
- Count Triplets That Can Form Two Arrays of Equal XOR
- Find if Array Can Be Sorted
- Largest Combination With Bitwise AND Greater Than Zero
- Maximum XOR for Each Query
- Shortest Subarray With OR at Least K II
- Notes
- Examples:
- Notes
- Example:
- First Node of a Cycle in Linked List
- Palindrome Linked List
- Partition List
- Split Linked List in Parts
- Reverse Linked List II
- Middle of the Linked List
- Merge in Between Linked Lists
- Delete Node in a Linked List
- Double a Number Represented as a Linked List
- Merge Nodes in Between Zeros
- Find the Minimum and Maximum Number of Nodes Between Critical Points
- Design Circular Deque
- All O`one Data Structure
- Examples:
- Maximum Product Subarray
- Three Sum Equal To 0
- Sort Array by Parity
- Shortest Unsorted Continuous Subarray
- Sort Colors
- Merge Intervals
- Check If a String Contains All Binary Codes of Size k
- Tranpose Matrix
- My Calendar I
- Meeting Scheduler
- Find the Duplicate Number (Floyd's algorithm)
- Product of Two Run-length Encoded Arrays
- Longest Substring With At Most Two Distinct Characters
- Longest Substring With At Most k Distinct Characters
- Max Consecutive Ones III
- Factor Combinations
- Decode String
- Substring with Concatenation of All Words
- N Queens
- Sudoku Solver
- Roman to Integer
- Dot Product of Two Sparse Vectors
- First Unique Character in a String
- Maximum Subarray
- Unique Morse Code Words
- Find Original Array From Doubled Array
- Minimum Penalty for a Shop
- Minimum Replacements to Sort the Array
- Minimum Operations to Reduce X to Zero
- Is Subsequence
- Decoded String at Index
- Monotonic Array
- 132 Pattern
- Reverse Words in a String III
- Remove Colored Pieces if Both Neighbors are the Same Color
- Number of Good Pairs
- Minimum Number of Operations to Make Array Continuous
- Maximum Score of a Good Subarray
- Last Moment Before All Ants Fall Out of a Plank
- Find the Winner of an Array Game
- Count Number of Homogenous Substrings
- Find Unique Binary String
- Frequency of the Most Frequent Element
- Minimum Amount of Time to Collect Garbage
- Diagonal Traverse II
- Arithmetic Subarrays
- Sum of Absolute Differences in a Sorted Array
- Check If Two String Arrays are Equivalent
- Largest 3-Same-Digit Number in String
- Count of Matches in Tournament
- Calculate Money in Leetcode Bank
- Largest Odd Number in String
- Element Appearing More Than 25% In Sorted Array
- Maximum Product of Two Elements in an Array
- Special Positions in a Binary Matrix
- Difference Between Ones and Zeros in Row and Column
- Maximum Product Difference Between Two Pairs
- Image Smoother
- Widest Vertical Area Between Two Points Containing No Points
- Maximum Score After Splitting a String
- Path Crossing
- Minimum Changes To Make Alternating Binary String
- Number of Laser Beams in a Bank
- Deteremine if String Halves Are Alike
- Sequential Digits
- Majority Element
- Find First Palindromic String in the Array
- Maximum Odd Binary Number
- Find the Pivot Integer
- First Missing Positive
- Length of Last Word
- Time Needed to Buy Tickets
- Longest Ideal Subsequence
- Minimum Falling Path Sum II
- Reverse Prefix of Word
- Compare Version Numbers
- Minimum Numbers of Function Calls to Make Target Array
- Score of a String
- Relative Sort Array
- Pass the Pillow
- Water Bottles
- Find the Winner of the Circular Game
- Average Waiting Time
- Lucky Numbers in a Matrix
- Find Valid Matrix Given Row and Column Sums
- Count Number of Teams
- Maximum Distance in Arrays
- Lemonade Change
- Find the Student that Will Replace the Chalk
- Sum of Digits of String After Convert
- Walking Robot Simulation
- Shortest Palindrome
- Lexicographical Numbers
- Kth Smallest in Lexicographical Order
- My Calendar II
- Check if Array Pairs are Divisible by K
- Sentence Similarity III
- Minimum Number of Swaps to Make the String Balanced
- Minimum Add to Make Parentheses Valid
- Longest Square Streak in an Array
- Delete Characters to Make Fancy String
- Circular Sentence
- Rotate String
- String Compression III
- Examples:
- Combination Sum III
- Letter Combinations of a Phone Number
- Permutations II
- Robot Room Cleaner
- Palindrome Partitioning
- Pseudo-Palindromic Paths in a Binary Tree
- Combinations
- Word Search
- Maximum Path Quality of a Graph
- Path with Maximum Gold
- Split a String Into the Max Number of Unique Substrings
- The Number of Beautiful Subsets
- Maximum Score Words Formed by Letters
- Word Break II
- Count Number of Maximum Bitwise or Subsets
- Examples
- Examples
- Notes
- Examples:
- Kahn's Algorithm BFS Implementation
- Rearrange Array Element by Sign
- Squares of a Sorted Array
- Minimum Length of String After Deleting Similar Ends
- Minimum Common Value
- Subarray Product Less Than k
- Count Subarrays Where Max Element Appears at Least k Times
- Subarrays with k Different Integers
- Count Subarrays With Fixed Bounds
- Boats to Save People
- Shortest Subarray to be Removed to Make Array Sorted
- Get Equal Substrings Within Budget
- Maximum Number of Robots Within Budget
- Count Number of Nice Subarrays
- Minimum Swaps to Group All 1's Together II
- Separate Black and White Balls
- Easy Level Examples
- Medium Level Examples
- String to Integer (atoi)
- Reverse Words in a String
- (Premium): Reverse Words in a String II
- Longest Palindromic Substring
- Set Matrix Zeroes
- Multiply Strings
- Spiral Matrix
- Word Search
- (Premium) Meeting Rooms II
- (Premium) Inorder Successor in BST
- (Premium) Design Tic-Tac-Toe
- (Premium) Design Hit Counter
- String Compression
- Minimum Moves to Equal Array Elements
- Design Circular Queue
- Top k Frequent Words
- Maximize Distance to Closest Person
- Angle Between Hands of a Clock
- Number of Steps to Reduce a Number in Binary Representation to One
- Longest Happy String
- Maximal Network Rank
- Minimum Deletions to Make Character Frequencies Unique
- Recover Binary Search Tree
- Binary Tree Ziqzag Level Order Traversal
- Shortest Bridge
- Minimum Deleteions to Make String Balanced
- Equal Sum Arrays with Minimum Number of Operations
- Hard Level Examples
- Contains Duplicate
- Two Sum
- Valid Anagram
- Encode and Decode Strings
- Group Anagrams
- Longest Consecutive Sequence
- Product of Array Except Self
- Top k Frequent Elements
- Valid Sudoku
- Binary Search
- Median of Two Sorted Arrays
- Find minimum in Rotated Sorted Array
- Koko Eating Bananas
- Search a 2D matrix
- Time Based Key Value Store
- Linked List Cycle
- Merge Two Sorted Lists
- Reverse Linked List
- Merge k Sorted Lists
- Reverse Nodes in k Group
- Add Two Numbers
- Copy List with Random Pointer
- Find the Duplicate Number
- LRU Cache
- Remove nth Node from End of List
- Reorder List
- Best Time to Buy and Sell Stock
- Minimum Window Substring
- Sliding Window Maximum
- Longest Repeating Character Replacement
- Longest Substring Without Repeating Characters
- Permutation in String
- Valid Parentheses
- Largest Rectangle in Histogram
- Car Fleet
- Daily Temperatures
- Evaluate Reverse Polish Notation
- Generate Parentheses
- Min Stack
- Balanced Binary Tree
- Diameter of Binary Tree
- Invert Binary Tree
- Lowest Common Ancestor of a Binary Search Tree
- Maximum Depth of Binary Tree
- Same Tree
- Subtree of Another Tree
- Binary Tree Maximum Path Sum
- Serialize and Deserialize Binary Tree
- Binary Tree level Order Traversal
- Binary Tree right Side View
- Construct Binary Tree from Preorder and Inorder Traversal
- Count Good Nodes in Binary Tree
- Kth Smallest Element in a BST
- Validate Binary Search Tree
- Valid Palindrome
- Trapping Rain Water
- Container with Most Water
- Three Sums
- Two Sum II Input Array is Sorted
- Kth Largest Element in a Stream
- Last Stone Weight
- K Cloest Points to Origin
- Kth Largest Element in an Array
- Task Scheduler
- Design Twitter
- Find Median From Data Stream
- Subsets
- Combination Sum
- Permutations
- Subsets II
- Combination Sum II
- Word Search
- Palindrome Partitioning
- Letter Combinations of a Phone Number
- N Queens
- Number of Islands
- Clone Graph
- Max Area of Island
- Pacific Atlantic Water Flow
- Surrounded Regions
- Rotting Oranges
- Walls and Gates
- Course Schedule
- Course Schedule II
- Redundant Connection
- Word Ladder
- Restore the Array from Adjacent Pairs
- Find Center of Star Graph
- Reconstruct Itinerary
- Min Cost to Connect All Points
- Network Dealy Time
- Swim in Rising Water
- Alien Dictionary
- Cheapest Flights Within K Stops
- Climbing Stairs
- Min Cost Climbing Stairs
- House Robber
- House Robber II
- Longest Palindromic Substring
- Palindromic Substrings
- Decode Ways
- Coin Change
- Maximum Product Subarray
- Word Break
- Longest Increasing Subsequence
- Partition Equal Subset Sum
- Unique Paths
- Longest Common Subsequence
- Best Time to Buy and Sell Stock with Cooldown
- Coin Change II
- Target Sum
- Interleaving String
- Longest Increasing Path in a Matrix
- Distinct Subsequences
- Edit Distance
- Brust Balloons
- Regular Expression Matching
- Maximum Subarray
- Jump Game
- Jump Game II
- Gas Station
- Hand of Straights
- Merge Triplets to Form Target Triplet
- Partition Labels
- Valid Parenthesis String