Algorithms in Python and LeetCode

• daily-challenge folder contains my problem-solving every day by following the daily challenge problems given by LeetCode.
• algorithm folder attempts to improve my understanding of a specific algorithms by picking the algorithm from LeetCode.
• company folder is a collection of the problems I solved with the higher frequency by company.
• math folder contains mathematical equations, calculations and proof to get solutions or to calculate complexity.
• note folder contains markdown files in which I took note about Algorithm concepts, LeetCode problems related to the concepts, and useful code snippets.

LeetCode

LeetCode ID: yukikitayama (https://leetcode.com/yukikitayama/)

Progress

• Solve 700 LeetCode problems (2021-11-23)
• Solve 800 LeetCode problems (2022-01-14)
• Solve 900 LeetCode problems (2022-03-26)
• Solve 1,000 LeetCode problems (2022-05-01)
• Solve 1,100 LeetCode problems (2022-06-12)
• Solve 1,200 LeetCode problems (2022-11-08)
• Solve 1,300 LeetCode problems (2023-12-02)
• Solve 1,400 LeetCode problems (2024-03-14)
• Solve 1,500 LeetCode problems (2024-04-21)
• Solve 1,600 LeetCode problems (2024-05-29)
• Solve 1,700 LeetCode problems (2024-08-01)
• Solve 1,800 LeetCode problems (2024-11-15)
• Solve 1,900 LeetCode problems (2025-02-21)
• Solve 2,000 LeetCode problems

Algorithms that I am not confident of

• Dynamic programming
• Binary search
• Morris traversal
• Topological sorting
• Dijkstra's algorithm
• Union find
• Bit manipulation
• Boyer-Moore voting algorithm
  • 229. Majority Element II
• Trie
• Divide and conquer

Algorithms that I don't understand

• Fenwick tree (binary index tree (BIT))
  • https://leetcode.com/problem-list/binary-indexed-tree/
  • https://leetcode.com/discuss/post/1093346/introduction-to-fenwick-treebinary-index-tp6h/
  • https://leetcode.com/discuss/post/6097648/fenwick-tree-bit-complete-notes-beginner-grib/
  • https://medium.com/@florian_algo/typical-problems-of-fenwick-tree-binary-indexed-tree-1b87a673749
  • 2179. Count Good Triplets in an Array
    • Hard

Approach

• Should always start with the example given in the problem statement.

Thinking

• As intuitive as the problem seems to be, you might stumble over the implementation. It's natural.
• DP is a careful brute force. We try at every possible place, but save the answers to prevent us from doing multiple times.
  • Python3 || Detailed Explanation and Commented Code

Action

• Review A star in 1091. Shortest Path in Binary Matrix
• Understand Morris Preorder Traversal.
  • [114. Flatten Binary Tree to Linked List(https://leetcode.com/problems/flatten-binary-tree-to-linked-list/)
  • 94. Binary Tree Inorder Traversal
• Understand Inverse Ackermann Function used to analyze time complexity of disjoint set find() and union()
• Learn Quickselect by 215. Kth Largest Element in an Array and Quickselect wiki

Python

• python.md
  • Useful Python tricks to understand and solve LeetCode problems.

Math

• math.md
  • Useful maths to understand and solve LeetCode problems.

Programming

• programming.md
  • Programming concepts in general.

SQL

• sql.md
  • MySQL skills

Algorithm

Markdown files in which I take note to understand algorithm concepts, to track the useful LeetCode problems regarding the concepts and useful code snippets. These unordered lists are linked to markdown files in this repo.

• Dynamic programming
  • Kadane's Algorithm
• Bit manipulation
  • Two's Complement
  • Get rightmost 1-bit
  • Turn off rightmost 1-bit
  • Check whether a number is power of 2
  • XOR
  • 1-bit Bitmask
  • Carry
  • Create binary number from most significant bit
• Disjoint set
• Heap
  • Heap sort
• Linked list
  • Floyd's Tortoise and Hare (Floyd's cycle-finding algorithm)
• Graph
  • Depth First Search (DFS)
  • Breadth First Search (BFS)
  • Hierholzer's Algorithm
• Minimum spanning tree
  • Kruskal's Algorithm
  • Prim's Algorithm
• Single source shortest path
  • Dijkstra's Algorithm
  • Bellman-Ford Algorithm
  • Shortest Path Faster Algorithm (SPFA algorithm)
• Topological sorting
  • Kahn's Algorithm
• Recursion
• Backtracking
• Divide and conquer
  • Master Theorem
  • Merge Sort
  • Quick Sort
• Binary Tree
• Tree
  • Morris Preorder Traversal
• String manipulation
  • Rabin-Karp Algorithm
• State machine
  • Deterministic Finite Automation (DFA)
• Trie
• Greedy
• Probability and statistics
  • Reservoir Sampling

English

• Subarray
  • Contiguous subsequence
  • E.g. given nums = [1, 2, 3, 4], [1, 2, 3] is subarray, but [1, 2, 4] isn't. It's subsequence of nums, but 2 and 4 are not contiguous, so it's not subarray.
• Subsequence
  • A sequence that can be derived from a given array by deleting some or no elements without changing the order of the remaining elements. Doesn't necessarily need to be contiguous.
• Substring
  • A contiguous non-empty sequence of characters within a string.
• Palindrome
  • A sequence of characters or numbers which reads the same backward as forward same
  • e.g. 121 is a palindrome, 123 isn't. aba is a palindrome, but abc isn't.
• Pangram
  • A sentence where every letter of the english alphabet appears at least once
• Bipartition
  • Having or consisting of two parts

Communication

• Often times you don't need to code the brute force solution in interview if you can come up with a better solution.
• Just speak out the brute force approach.

Design

• Have as less attributes as possible, even if attributes are convenient.
  • Less attributes mean that the manipulation logic is simpler and less error-prone.
  • Less space, so efficiency to the runtime performance.

Follow-up

• Reducing the number of passes by loops is a very common follow-up.
  • e.g. Code contains 2 while loops. It's not O(N^2), but O(N), even if O(2N) = O(N) in analysis.

Amortized Analysis

• Gives the average performance of each operation in the worst case.
• The worst case operation can alter the state in such a way that the worst case cannot occur again for a long time ("amortizing cost").

Problems Requiring Amortized Analysis

• 173. Binary Search Tree Iterator

Proof by Contradiction

Example

• 134. Gas Station

Resource

• Stable Sort
  • YouTube videos to understand complex algorithm concepts
• Elements of Programming Interviews in Python: The Insiders' Guide
  • The book that the people who apply for software engineer use to prepare for technical interviews.

Blind Game

• A type of LeetCode problem where we don't have a direct access to the data.
• Instead, we are given API or custom class or function to get a partial information of the data.
• So unless interaction, we cannot find the answer.

Example

• 1274. Number of Ships in a Rectangle

Game

• Snake game
  • Play online

YouTube

LeetCode Number	Problem Name	Level	YouTube	Language
21	Merge Two Sorted Lists	Easy	https://youtu.be/5J_iUgDQqow	English
105	Construct Binary Tree from Preorder and Inorder Traversal	Medium	https://youtu.be/Q9xtzCxzpSg	English
729	My Calendar I	Medium	https://youtu.be/OoKST96zFdo	Japanese
695	Max Area of Island	Medium	https://youtu.be/9FtAC0yPigQ	English
102	Binary Tree Level Order Traversal	Medium	https://youtu.be/9fmXC3lyDCw	Japanese
359	Logger Rate Limiter	Easy	https://youtu.be/Npj5zJj8C2s	English
323	Number of Connected Components in an Undirected Graph	Medium	https://youtu.be/LXh35C1hVQA	Japanese
204	Count Primes	Easy	https://youtu.be/HwXK1DJIf1k
326	Power of Three	Easy	https://youtu.be/iHTOFDlkJqg
1480	Running Sum of 1D Array	Easy	https://youtu.be/HbSN-ElXHwc

Patterns

• Sorted input
  • Apply binary search for efficient element lookup.
  • Use the two-pointer technique for problems involving pairs or segments.
• Unsorted input
  • Use a hash map or set to find specific elements quickly.
  • Implement a monotonic stack or sliding window technique for managing elements while continuously finding maximum or minimum values.
  • Use backtracking for problems that ask for all possibilities or combinations (this is also a suitable fallback if dynamic programming isn’t going to work).
  • Apply dynamic programming for questions related to counting ways or optimizing values.
  • Use a Trie for prefix matching and string-building scenarios.
• Input is a Graph or Tree
  • Use DFS to explore all paths or when the question does not require finding the shortest path.
  • Use BFS when the question asks for the shortest path or fewest steps.
  • For binary trees, use DFS if the problem involves exploring specific depths or levels.
• Linked List input
  • Use techniques involving slow and fast pointers or "prev" and "dummy" pointers to facilitate certain operations if you are unsure how to achieve a specific outcome.