---

Leetcode Python Solutions.

📜 Summary

This repository contains solutions to Leetcode problems. It will be updated regularly(Daily/Weekly). The primary reason for this repository is because I believe the best way to solve these problems is by dividing them into topics, each topic into difficulties, and solving at least one problem within each difficulty(quality > quantity). Such repositories are hard to find on the internet; this is the first one most likely. Therefore, I will gradually build this place to make it easier for beginners to learn algorithms by solving problems on leetcode by topics.

Don’t forget to slap that ⭐ button an odd number of times ;-)

Currently maintained by Mahmoud Harmouch.

---

Prerequisites

Basic understanding of the core language. If you are new to python, I highly recommend checking out the free learning material I compiled in the awesome-python repository.

python -c "import this" | grep Simple

Simple is better than complex.

---

👉 Table Of Content (TOC).

• Two Pointers
  • Easy
    • Move Zeros
    • Two Sum
    • Squares of a Sorted Array
  • Medium
    • Two Sum II
• Hash Table
  • Easy
    • Two Sum
  • Medium
    • Integer to Roman
• Binary Tree
  • Easy
    • Binary Tree Preorder Traversal
    • Binary Tree Inorder Traversal
    • Binary Tree Postorder Traversal
    • Average of Levels in Binary Tree
  • Medium
    • Binary Tree Level Order Traversal
    • Binary Tree Zigzag Level Order Traversal
    • Populating Next Right Pointers in Each Node
• Binary Search
  • Easy
    • Find Smallest Letter Greater Than Target
    • Binary Search
    • First Bad Version
    • Search Insert Position
    • Sqrt(x)
  • Medium
    • Find Minimum in Rotated Sorted Array
    • Find Peak Element
    • My Calendar I
  • Hard
    • Find Minimum in Rotated Sorted Array II
    • Median of Two Sorted Arrays
• String
  • Easy
    • Longest Common Prefix
    • Reorder Data in Log Files
    • Isomorphic Strings
    • Is Subsequence
  • Medium
    • Group Anagrams
• Linked List
  • Easy
    • Reverse Linked List
    • Merge Two Sorted Lists
  • Medium
    • Add Two Numbers
    • Reorder List
• Array
  • Easy
    • Running Sum of 1d Array
    • Find Pivot Index
  • Medium
    • Search a 2D Matrix II
    • Kth Smallest Element in a Sorted Matrix
• Math
  • Easy
    • Mirror Reflection

Two Pointers

🔝 Go To TOC.

Easy

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
283.	Move Zeroes	Use two consecutive pointers, the left one at the start of the list, the right one at start + 1.	file	O(n). The right pointer does not visit the same element twice.	O(1). All operations are made in-place.
1.	Two Sum	Sort the array and store it into a tmp variable. Use two pointers, the left one at the start of the list, the right one at the end of the list.	file	O(n logn). because of Timsort	O(n). n is the length of the tmp List.
977.	Squares of a Sorted Array	The array is already sorted. Use two pointers, the left one at the start of the list, the right one at the end of the list. Compare the abs of the left and right elements. If abs_left is larger than abs_right, then: results[right - left] = abs_left * abs_left left += 1 else: results[right - left] = abs_right * abs_right right -= 1	file	O(n). A linear scan, n is the length of the results List	O(n). n is the length of the results List.

Medium

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
167.	Two Sum II - Input Array Is Sorted	The array is already sorted. Use two pointers, the left one at the start of the list, the right one at the end of it.	file	O(n). The right and left pointers do not visit the same element twice.	O(1). All operations are made in-place.

Hash Table

🔝 Go To TOC.

Easy

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
1.	Two Sum	Create a hashmap which accepts integer datatype as key and value. Check if difference (element visited - target) is present in the hashmap. If present, return indexes as result. Otherwise, add the current element as key and its value as the current iteration	file	O(n). One for loop, hashmap lookup ~ O(1)	O(n). Hash Table.

Medium

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
12.	Integer to Roman	Store the numbers from largest to smallest into a hashmap, aka dict. Keep dividing the given number by the numbers stored in the hashmap The quotient of division denotes how many times the current roman number appears in the end result Update the number by the reminder of the previous division.	file	O(k). k: length of the hash table.	O(n). n: length of the hash table + list.

Binary Tree

🔝 Go To TOC.

Easy

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
144.	Recursive Preorder Traversal	Add the current node onto the list. Traverse the left sub-tree, and keep adding the visited node. If root is None, stop traverse, and move to the right sub-tree.	file	O(n), n number of nodes.	O(log n) ~ height/depth of the tree.
144.	Iterative Preorder Traversal	Use a stack(LIFO). Add the root node into a list. Visit right, then left nodes, and push onto the stack. Pop an element from the stack, add it into the list. Repeat the previous two steps until the stack is empty.	file	O(n), n number of nodes.	O(log n) ~ height/depth of the tree.
144.	Morris Traversal	Preorder traversal without recursion and or stack. Push current.right rather than the current node. The None cases will handle themselves by the inner while loop.	file	O(n), n number of nodes.	O(1).
94.	Iterative Inorder Traversal	Push all the left children of root into the stack until there's no more nodes. Then pop from the stack which is called current. Add current to result list. Kepp calling push_all_left() on current's right child until stack is empty.	file	O(n), n number of nodes.	O(n), n number of nodes.
94.	Recursive Inorder Traversal	Keep visiting all the left nodes. Once finished, add the current node while visiting the right node.	file	O(n), n number of nodes.	O(log n) ~ height/depth of the tree.
145	Iterative Postorder Traversal	Push all the left children of root into the stack until there's no more nodes. Then pop from the stack which is called current. Keep calling push_all_left() on current's right child until stack is empty. Add current to result list.	file	O(n), n number of nodes.	O(n), n number of nodes.
145.	Recursive Postorder Traversal	Keep visiting all the left nodes, then all the left of current. Once finished, add the current node while visiting the right node.	file	O(n), n number of nodes.	O(log n) ~ height/depth of the tree.
637.	Iterative Average of Levels in Binary Tree	Same as level order traversal, append the average value of each level nodes onto the list.	file	O(n), n number of nodes.	O(n), n number of nodes.

Medium

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
102.	Level Order Traversal	Traverse tree level by level. Use a Queue/Deque to keep track of all the nodes of the next level before moving to the next level.	file	O(n).	O(n)
102.	Recursive Level Order Traversal	Traverse tree level by level. Use a Deque to keep track of all the nodes of the next level before moving to the next level.	file	O(n).	O(logn)
103.	Iterative Zigzag Level Order Traversal	After doing level order traversal using recursion, we simply reverse the direction at alternate levels	file	O(n).	O(n)
103.	Recursive Zigzag Level Order Traversal	After doing level order traversal using recursion, we simply reverse the direction at alternate levels	file	O(n).	O(logn)
116.	Populating Next Right Pointers in Each Node	Using BFS to populate next pointers of each node with nodes that occur to its immediate right on the same level. Since for each node, we require the right node on the same level, we will perform a right-to-left BFS instead of the standard left-to-right BFS.	file	O(n).	O(1) by using pointers

Binary Search

🔝 Go To TOC.

Easy

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
744.	Find Smallest Letter Greater Than Target	Return letters[0] if letter at index 0 is larger than target. Return letters[0] if letter at index -1 is lower or equal to target. Perform a binary seach on the list for target. The condition of the while loop is left <= right. Check if mid element > target element, update right = mid_point - 1. else: left = mid_point + 1. Return letters[left]	file	O(log n). n: length of the list.	O(1). pointers.
704.	Iterative Binary Search	Initialise two pointers: left = 0, right = length of the array - 1. While left <= right: Compare nums[mid] to target. If the target = nums[mid]: return mid. If target < nums[mid], continue the search on the left, right = mid - 1. Else continue the search on the right, left = mid + 1. If not found, return -1.	file	O(log n). n: length of the list.	O(1). pointers.
704.	Recursive Binary Search	Pass the array, two pointers, and the target to a function for reursive calls: binary_search(nums, left, right, target) Base case: if left > right: return - 1 If the target = nums[mid]: return mid. If target < nums[mid], continue the search on the left, right = mid - 1: binary_search(nums,left , mid-1, target) Else continue the search on the right, return binary_search(nums,mid + 1 , right, target)	file	O(log n). n: length of the list.	O(log n). log n: The length of the binary tree.
278.	Iterative First Bad Version	Initialise two pointers: left = 1, right = n. While left <= right: check if isBadVersion(mid). If not isBadVersion(mid): continue the search on the right, left = mid + 1. Else continue the search on the left, right = mid - 1. return left	file	O(log n). n: length of the list.	O(1). pointers.
278.	Recursive First Bad Version	Pass two pointers to a function for reursive calls: binary_search(left = 1, right = n) Base case: if left > right: return - 1 if left == right: return left If the target = nums[mid]: return mid. if not isBadVersion(mid), continue the search on the right, return binary_search(mid + 1, right). Else continue the search on the left, return binary_search(left, mid).	file	O(log n). n: length of the list.	O(log n). log n: The length of the binary tree.
35.	Iterative Search Insert Position	Initialise two pointers, and a return value variable: left = 0, right = length of the array - 1, ret_val = 0. Compare nums[mid] to target. If the target = nums[mid]: return mid. If target < nums[mid], continue the search on the left, right = mid - 1. Else continue the search on the right, left = mid + 1, and set ret_val = left. return ret_val.	file	O(log n). n: length of the list.	O(1). pointers.
35.	Recursive Search Insert Position	pass the array, two pointers, target, and a ret_val to a function for reursive calls: binary_search(nums, left, right, target, ret_val) Base case: if left > right: return ret_val If the target = nums[mid]: return mid. If target < nums[mid], continue the search on the left, right = mid - 1: binary_search(nums,left , mid-1, target) Else set ret_val = mid + 1, and continue the search on the right, return binary_search(nums,mid + 1 , right, target)	file	O(log n). n: length of the list.	O(log n). log n: The length of the binary tree.
69.	Sqrt(x)	Use two pointers left, right= 0, number. The condition of the while loop is left <= right. Check if mid * mid <= number < (mid + 1) * (mid + 1), return mid. Check if number < mid * mid , set right to mid. else, set left to mid.	file	O(log n). n: given number.	O(1). pointers.

Medium

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
153.	Find Minimum in Rotated Sorted Array	Check if the array is sorted but not rotated, return the first element. Perform a binary seach on the list. The condition of the while loop is left < right. Check if mid element > right element, update left = mid_point + 1. else: right = mid_point. Return min(nums[left], nums[right]).	file	O(log n). n: length of the list.	O(1). pointers.
162.	Find Peak Element	Perform a binary seach on the list. The condition of the while loop is left < right. Check if mid element < mid element + 1, update left = mid_point + 1. else: right = mid_point. Return left.	file	O(log n). n: length of the list.	O(1). pointers.
729.	My Calendar I	Check if it is possible to insert an interval when possible by performing a binary seach on the calendar. The condition of the while loop is left < right. Check if target <= nums[mid][0], update right = mid. else: left = mid + 1. Return left. Check if index > 0 and self.calendar[index-1][1] > start, return False Check if index < len(self.calendar) and end > self.calendar[index][0], return False Insert into calender: self.calendar.insert(index, [start, end]) return True	file	O(log n). n: length of the list.	O(1). pointers.

Hard

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
154.	Find Minimum in Rotated Sorted Array II	Same as Find Minimum in Rotated Sorted Array. The only difference is that we can have duplicates. Therefore we need to update left += 1, and right += 1, instead of mid. Example, [5,5,0,5,5,5,5] Return nums[left]	file	O(log n). n: length of the list.	O(1). pointers.
4.	Median of Two Sorted Arrays	Initialize two pointers : left=0 and right=m (size of smaller array). Iterate untill condition left<=right evaluates to be true. Make a partition at the middle of the range and pick up the elements before the partition from first array. Now take the remaining elements from the second array (say p1). Find the values of border elements of the range of elements taken from both the arrays(leftmost and rightmost values). Check if nums1_leftmost > nums2_rightmost: then decrease right pointer to p1-1 Check if nums2_leftmost > nums1_rightmost: then increase left = p1 + 1 Check if nums2_leftmost > nums1_rightmost: then increase left = p1 + 1 Else: Check if total number of elements in both the arrays is odd: then median = (max(nums1_leftmost, nums2_leftmost) + min(nums1_rightmost, nums2_rightmost)) / 2 Else: median = max(nums1_leftmost, nums2_leftmost)	file	O(log(min(m,n))). m, n: length of both arrays.	O(1). Operations are made in place.

String

🔝 Go To TOC.

Easy

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
14.	Longest Common Prefix	Horizontal scanning. Assign the first element of the list as the common prefix. Iterate over the list. Test if all characters match the second string. If not, remove a letter from the end of the string(first element of the list.). If matches, continue untill you find the common prefix amoung all strings.	file	O(n), n is the length of the array.	O(1). constant length of the prefix.
14.	Reorder Data in Log Files	We define a tuple of 3 keys, (key_1, key_2, key_3), as follows: key_1: this key serves as a indicator for the type of logs. For the letter-logs, we could assign its key_1 with 0, and for the digit-logs, we assign its key_1 with 1. key_2: for this key, we use the content of the letter-logs as its value. key_3: similarly with the key_2, this key serves to further order the letter-logs.	file	O(m n logn). because of Timsort. m the for the comparison between two keys.	O(m n) to keep the keys for the log.
205.	Isomorphic Strings	Simultaneously, loop over the two strings s and t. Map each char in s to a char in t only if a new char of t not in values of dict/map. Example: s = "badc", t = "baba", dict = {'b' : 'b', 'a': 'a', ...} If the current char of s not in dict, and the current char of t in values of dict, return False. If the current char of s in dict, and the value of key of s char is not equal to the current char of t, return False. return True.	file	O(n), n: length of the input string.	O(1), because the number of ASCII chars is constant, man ascii
205.	Is Subsequence	Loop over all chars in t. If the current char of t is equal to the char of s at index pointer, increase pointer. If pointer is equal to the length of s, break. Return True if pointer is equal to the length of s, False otherwise.	file	O(n).	O(1).

Medium

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
49.	Group Anagrams	Maintain a map result : {str: list[str]} where each key K is a sorted string, and each value is the list of strings from the initial input that when sorted, are equal to K. Eample: strs_input = ["are", "bat", "ear", "code", "tab", "era"] result = {'aer'): ['are', 'ear', 'era'], ...} Itertate over the list of strings. Converts each string into a sorted tuple. Store the previous tuple as a key into the dict whos value the string itself. Once finished, return the values of the dict.	file	O(N K log⁡ K), N is the length of strs, and K is the maximum length of a string in strs.	O(N K), N strings, K is the maximum length of a string in strs.

Linked List

🔝 Go To TOC.

Easy

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
206.	Iterative Reverse Linked List	Maintain three variables, current node, head, previous node. Iterate the head through the list is done using the following instruction: head.next = head. But, we need to store the head before moving to the next node using the variable current = head. Move the current point to the previous node; this way, the list is being reversed. Assign the presvious node to current node. Keep iterating until head point to None. Return previous node as the new head for our reversed LinkedList.	file	O(n), n denotes the size of the linked list.	O(1), Operations are made in-place.
206.	Recursive Reverse Linked List	Return the pointer of next node to its previous node and then make the previous node as the next node of returned node and then return the current node. We first traverse till the last node and making the last node as the head node of reversed linked list and then applying the above procedure in the recursive manner.	file	O(n), n denotes the size of the linked list.	O(n), n denotes the size of the linked list.
206.	Stack Iterative Reverse Linked List	Traverse the list and push all of its nodes onto a stack. Traverse the list from the head node again and pop a value from the stack top and connect them in reverse order.	file	O(n), n denotes the size of the linked list.	O(n), n denotes the size of the linked list.
21.	Iterative Merge Two Sorted Lists	Create two dummy nodes, current = dummy = ListNode() Simultaneously, Traverse both lists. Compare the values of the current nodes from both lists. Assign the next node of current to the node that has the minimum value. Assign list to list.next. Assign current to list return dummy.next	file	O(n), n denotes the size of a linked list.	O(n), n denotes the size of a linked list.
21.	Recursive Merge Two Sorted Lists	Base case: if one of the lists is empty, return either lists. Compare the values of the current nodes from both lists. Assign the next node of current to the node that has the minimum value. Assign list.next to either mergeTwoLists(list.next, list) or mergeTwoLists(list, list.next). return either lists	file	O(n), n denotes the size of a linked list.	O(n), n denotes the size of a linked list.

Medium

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
2.	Add Two Numbers	Initialize current node to dummy head of the returning list. Initialize carry to 0. Initialize dummy_head current_head. Loop through lists l1 and l2 until you reach both ends. Get the values from the linkedLists. Move heads to the next node. Check if carry > 0, if so append a new node with value carry to the returning list. Return dummy head's next node because we initialized the dummy_head with a value 0.	file	O(max⁡(m,n)) where m and n represents the length of l1 and l2 respectively.	O(max⁡(m,n)) The length of the new list is at most max⁡(m,n)+1.
143.	Reorder List	Find the middle of or list - be careful, it needs to work properly both for even and for odd number of nodes. we can use slow/fast iterators trick, where slow moves with speed 1 and fast moves with speed 2 Reverse the second part of linked list. The idea is to keep three pointers: prev, curr, nextt stand for previous, current and next and change connections in place. Finally, we need to merge two lists, given its heads. Interchange nodes: we put head2 as next element of head1 and then say that head1 is now head2 and head2 is previous head1.next.	file	O(n), n denotes the size of the linked list.	O(1).

Array

🔝 Go To TOC.

Easy

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
1480.	Running Sum of 1d Array	Iterate over the list. Add nums[i] to nums[i - 1] and assign the result to nums[i].	file	O(n), n is the length of the array.	O(1). Operations are made in place.
724.	Find Pivot Index	Set the left and the right sums to 0 and sum(nums) respectively. Subtract nums[i] from the right sum. Test if left_sum == right_sum, then return. else, add nums[i] to the left sum.	file	O(n), n is the length of the array.	O(1). Operations are made in place.

Medium

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
240.	Search a 2D Matrix II	Start iterating from bottom left corner with two pointers: bottom, left = nb_rows-1, 0. If target is larger then current element, then go right by incrementing the left pointer by one. If target is smaller then current element, then go up by decrementing the bottom pointer by one. If target is equal to the current element, then return True.	file	O(m+n), m, n are the number of columns and rows in the array.	O(1). Operations are made in place.
378.	Kth Smallest Element in a Sorted Matrix	Set two pointers: left = matrix[0][0] (top left), and right = matrix[n-1][n-1] bottom right. Search for the mid of left and right, The mid is NOT necessarily an element in the matrix. If countLessOrEqual(mid) >= k, we keep current ans = mid and try to find smaller value by searching in the left side. Otherwise, we search in the right side. Since ans is the smallest value which countLessOrEqual(ans) >= k, so it's the kth smallest element in the matrix.	file	O(m+n), m, n are the number of columns and rows in the array.	O(1). Operations are made in place.

Math

🔝 Go To TOC.

Easy

#	Problem Statement	Notes	Solution	Time Complexity	Space Complexity
858.	Mirror Reflection	Keep dividing p,q by 2 until at least one becomes odd. Check if p is odd: then return q % 2. Else: return 2. The idea is that for all odd p, the rays intersecting would alternate between 1 and 0. If p is odd, for q (1...n) -> mirror reflected will be (1,0,1...0,1). This can easily be generalized as q % 2, since mirror reflected will be 1 when q is odd, and 0 when q is even. if p is a power of 2, the mirror reflected will always be 2 except for when q == p, and then mirror reflected is 1.	file	O(1).	O(1).

Contributing

You can open a pull request if you want!

License

This project is licensed under the MIT License.