This is a collection of algorithms and data-structure implemenetations in Go and Python made by myself!
I work with a TDD methodology. Each folder has its [name].go file and its [name]_test.go file. In order to run the go code just go to the desired path and run the following command:
go test [-v] // The -v flag is optional- Linked List
- Deque
- Stack
- Min Stack: Retrieves the min value in O(1) time.
- Contains Duplicate (Leetcode 217): Brute force O(N^2), Merge Sort method O(N logN) and Map solution O(N).
- Valid Anagram (Leetcode 242): An efficient Hashmap solution O(N) and another implementation for detecting sub-anagrams of t contained in s!
- Two Sum (Leetcode 1): Brute force O(N^2) and efficient O(N) using a hashmap.
- Group Anagrams (Leetcode 49): Brute force O(N^3) and efficient O(M*N) using a hashmap.
- Top K Frequent Elements (Leetcode 347): Not efficient solution in O(n log n) time and an efficient Bucket Sort solution in O(n).
- Product of Array expect Self (Leetcode 238): Efficient solution in O(N), there is a simpler formula but does the trick.
- Valid Sudoku (Leetcode 36): Efficient solution in O(N*M) faster than 100% ⭐.
- Encode and Decode Strings (Leetcode 271): Two O(N) solutions (with and without the standard library).
- Longest Consecutive Sequence (Leetcode 128): O(N) solution: first we build up the hashset, then we count steaks above and below (value+1 and value-1).
- Valid Palindrome (Leetcode 125): O(N) efficient solution, working with Go strings, runes or bytes is always a pleasure for its standard lib! Faster than 100% ⭐.
- Two Sum II (Leetcode 167): O(N^2) brute force solution and O(N) efficient solution, because the array is sorted we don't need the hashmap approach.
- 3Sum (Leetcode 15): O(N^3) brute force solution and O(N^2) Better approach in which we avoid duplicates by sorting the array and not using as first value (i) twice the same value. Then we reduce the rest of the two nums to a two sum problem.
- Container With Most Water (Leetcode 11): O(N) time. It's not a hard problem it just requires problem specification.
- Trapping Rain Water (Leetcode 42): O(NlogN) Approach based on finding local max "valleys", minimum of 3 numbers where the extremas are bigger than the inner numbers.
- Best Time to Buy and Sell Stock (Leetcode 121): Brute force O(N^2) and Sliding Window with 2 pointers in O(N) time.
- Longests Substring without repeating characters (Leetcode 3): O(N) time. It was tricky because our reference pointer is the tail, and typically we are so used to have the reference pointer the leading one. Faster than 100% ⭐.
- Longest Repeating Character Replacement (Leetcode 424): In O(N) time. This one was hard, did not know how to approach in a clear way.
- Permutation in String (Leetcode 567): O(N^2) approach with sliding window, could be much faster if Go could deepcopy a map in a easy way.
- Minimum Window Substring (Leetcode 76): O(N) approach with sliding window that always mantains all elements of permutations except for one. Grow to find the desired value, Shrink to expand later on.
- Sliding Window Maximum (Leetcode 239): O(N) approach with a deque.
- Valid Parentheses (Leetcode 20): O(N) approach with readable code using the stack and a hashmap.
- Min Stack (Leetcode 155): In constant time O(1) by using an additional stack that keeps track of the minimum value at each node.
- Evaluate Reverse Polish Notation (Leetcode 150): O(N) time using the logic of Polish notation.
- Generate Parentheses (Leetcode 22): Tricky one, O(N) solution with Backtracking algorithm and a Stack to help keep track of the state. Recursion in Go is more strict than any other languages, we do not want memory leaks! Faster than 100% ⭐.
- Daily Temperatures (Leetcode 739): Dynamic Stack solution keeping the local max in reverse order loop.
- Car Fleet (Leetcode 853): O(N logN) because it requires to sort the positions array and a hash map for the speeds.
- Search a 2d Array (Leetcode 74): O(n log n) approach with binary search for a given row.
- Koko Eating Bananas (Leetcode 875):
- skiena-1.30: Nearest Neighbour vs Closest Pair heuristic in the TSP problem.
- leetcode-739 (Problem in Leetcode): Brute force implementation O(N^2)
- leetcode-61 (Problem in Leetcode): Linked List implementation from scratch and Rotation algorithm in O(N^2) and an improved version in O(N) time faster than 100% ⭐.
- leetcode-324 (Problem in Leetcode): Wiggle Sort. Clear approach, but not optimal.
- leetcode-1833 (Problem in Leetcode): Merge sort O(N log N).