These are my submissions from Leetcode, started from knowing nothing about advanced data structures and algorithms (and still is).
Rather than to show off my code, this article is more like a progress revision for my algo journey. Therefore, it’ll be regularly updated.
Who knows, maybe after months of 40 hours a day practicing, I will take a look back and find out how sacrilegious my code once was. :D
Starting point: 14 days study plan to crack algo
First day: 704. Binary Search
Accepted Python code:
class Solution:
def search(self, nums: List[int], target: int) -> int:
high = len(nums)
low = 0
mid = (low + high) // 2
while low < high:
mid = (low + high) // 2
if nums[mid] != target and nums[mid] < target:
low = mid + 1
elif nums[mid] != target and nums[mid] > target:
high = mid
else:
return mid
return mid if nums[mid] == target else -1
Accepted C++ code:
class Solution {
public:
int search(vector<int>& nums, int target) {
int high = nums.size(), low = 0;
int mid = (high + low) / 2;
while (low < high) {
mid = (high + low) / 2;
if (nums[mid] < target)
low = mid + 1;
else if (nums[mid] > target)
high = mid;
else
return mid;
}
return -1;
}
};
First day: 278. First Bad version
Accepted Python solution:
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
high: int = n
low: int = 1
mid: int = low + (high - low) // 2
while low < high:
mid = low + (high - low) // 2
if isBadVersion(mid):
high = mid
else:
low = mid + 1
return low
Accepted C++ solution:
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int high = n, low = 1;
int mid = low + (high - low) / 2;
while (low < high) {
mid = low + (high - low) / 2;
if (isBadVersion(mid))
high = mid;
else
low = mid + 1;
}
return low;
}
};
First day: 35. Search Insert Position
Accepted C++ solution:
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int high = nums.size(), low = 0;
int mid;
while (low < high) {
mid = low + (high - low) / 2;
if (nums[mid] < target)
low = mid + 1;
else
high = mid;
}
return high;
}
};
Another accepted C++ solution, but took 9 ms more:
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
}
};
Accepted Python solution:
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
high: int = len(nums)
low: int = 0
while low < high:
mid = (low + high) // 2
if nums[mid] < target:
low = mid + 1
else:
high = mid
return high
This one ran slower, while taking less space:
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
return bisect_left(nums, target)
Even though they are practically the same algorithm… How could it be??
Day 2: 977. Squares of a Sorted Array
Accepted Python solution:
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
# Handling edge case
if not len(nums) > 3:
return sorted([i*i for i in nums])
# Set dead end on a side
MAX_INTERGER_VALUE: int = 10**4
nums.append(MAX_INTERGER_VALUE + 1)
# Get the position of the number
# that's nearest to 0
zeroPosition = bisect_right(nums, 0)
left: int = zeroPosition - 1
right: int = zeroPosition
answer = []
while left >= 0 or right < len(nums):
if abs(nums[left]) < abs(nums[right]):
answer.append(nums[left]**2)
left -= 1
else:
answer.append(nums[right]**2)
right += 1
if left == -1 and right + 1 == len(nums):
answer.append(nums[right]**2)
break
if right == len(nums) and left == 0:
answer.append(nums[left]**2)
break
return answer[:-1]
Another one, ran faster while taking 2KB more space:
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
return sorted([i*i for i in nums])
WHY???
Here’s my first C++ solution:
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
// Get index of first positive number
int firstPositiveNumber = 0;
while (firstPositiveNumber < nums.size() && nums.at(firstPositiveNumber) < 0) ++firstPositiveNumber;
int negative = firstPositiveNumber - 1, positive = firstPositiveNumber;
vector<int> answer;
while (negative >= 0 && positive < nums.size()) {
if (nums.at(negative) * -1 < nums.at(positive)) {
answer.push_back(nums.at(negative) * nums.at(negative));
--negative;
}
else {
answer.push_back(nums.at(positive) * nums.at(positive));
++positive;
}
}
while (negative >= 0) {
answer.push_back(nums.at(negative) * nums.at(negative));
--negative;
}
while (positive < nums.size()) {
answer.push_back(nums.at(positive) * nums.at(positive));
++positive;
}
return answer;
}
};
Another C++ one:
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
vector<int> answer(nums.size(), 0);
for (int i = nums.size() - 1; i >= 0; --i) {
if (abs(nums[left]) < abs(nums[right])) {
answer.at(i) = nums[right] * nums[right];
right -= 1;
}
else {
answer[i] = nums[left] * nums[left];
left += 1;
}
}
return answer;
}
};
And another one, far more superior:
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
transform(nums.begin(), nums.end(), nums.begin(), [](int f){return f*f;});
sort(nums.begin(), nums.end());
return nums;
}
};
At this rate, I’ve eventually given up haphazardly trust big O notation. ;-;
Day 2: 189. Rotate Array
Accepted Python solution:
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums[:] = nums[-k % len(nums):] + nums[:-k % len(nums)]
Accepted C++ solution:
class Solution {
public:
void rotate(vector<int>& nums, int k) {
// reverse method
k %= nums.size();
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
};
It was the moment writing this article that I realized - I was supposed to use 2 pointers method! Guess let’s just save that for later then. :D
Day 3: 283. Move Zeroes
Here are 2 different solutions, written in Python:
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
lastNonZeroIndex: int = 0
for i in nums:
if i:
nums[lastNonZeroIndex] = i
lastNonZeroIndex += 1
for i in range(lastNonZeroIndex, len(nums)):
nums[i] = 0
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
lastNonZeroIndex: int = 0
for i in range(len(nums)):
if nums[i]:
nums[lastNonZeroIndex], nums[i] = nums[i], nums[lastNonZeroIndex]
lastNonZeroIndex += 1
They are both O(n) in terms of time complexity, and O(1) in space complexity, so there’s not much comparison though.
C++ implementation for the second solution:
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int lastNonZeroIndex = 0;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i])
swap(nums[lastNonZeroIndex++], nums[i]);
}
}
};
Day 3: 167. Two Sum II - Input Array is Sorted
This bruteforce solution got Time Limit Exceeded:
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> ans;
for (int i = 0; i + 1 < numbers.size(); ++i) {
int left = i, right = numbers.size() - 1;
while (left < right &&\
numbers.at(left) + numbers.at(right) >= target) {
if (numbers.at(left) + numbers.at(right) == target) {
ans.insert(ans.end(), {left + 1, right + 1});
return ans;
}
--right;
}
}
return ans;
}
};
Accepted C++ solution:
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size() - 1;
vector<int> ans;
while (left < right) {
int currentSum = numbers.at(left) + numbers.at(right);
if (currentSum == target) {
ans.insert(ans.end(), {left + 1, right + 1});
break;
}
else if (currentSum > target) {
--right;
}
else {
++left;
}
}
return ans;
}
};
Python line-to-line convertion of that exact piece of code:
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
answer: List[int] = []
while left < right:
currentSum: int = numbers[left] + numbers[right]
if currentSum == target:
answer.extend([left + 1, right + 1])
break
elif currentSum > target:
right -= 1
else:
left += 1
return answer
Day 4: 344. Reverse String
Nothing much, just swap them in-place, and there’re built-in functions for that. Here’s C++ solution:
class Solution {
public:
void reverseString(vector<char>& s) {
reverse(s.begin(), s.end());
}
};
And Python implementation:
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
s.reverse()
Day 4: 557. Reverse Words in a String III
Still nothing much. Let’s just split it out and reverse it.
C++ accepted solution:
class Solution {
public:
string reverseWords(string s) {
int lastChar = 0;
string answer = s + " ";
for (int wordcount = 0; wordcount < answer.size(); ++wordcount) {
if (answer[wordcount] == ' ') {
int left = lastChar, right = wordcount;
lastChar = wordcount + 1;
reverse(answer.begin() + left, answer.begin() + right);
}
}
answer.pop_back();
return answer;
}
};
Accepted Python solution:
class Solution:
def reverseWords(self, s: str) -> str:
return " ".join([word[::-1] for word in s.split()])
Day 5: 876. Middle of the Linked List
Solution: Get 2 pointers to iterate at different speed, the faster one is twice as fast as the slower one. When the faster pointer reach the end, the slower pointer should be in the middle.
Accepted C++ implementation:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast != NULL && fast -> next != NULL) {
slow = slow -> next;
fast = fast -> next -> next;
}
return slow;
}
};
For Python, I tried to store all nodes in a list and then pick the middle out. Unexptectedly, 2 algorithms run at exactly same speed (28ms) and memory (14.1 MB):
# Should be slower, but wasn't.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
allList: List[ListNode] = []
currentNode = head
while True:
allList.append(currentNode)
if not currentNode.next: break
currentNode = currentNode.next
return allList[len(allList) // 2]
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow: ListNode = head
fast: ListNode = head
while fast != None and fast.next != None:
slow = slow.next
fast = fast.next.next
return slow
Day 5: 19. Remove Nth Node From End of List
Again, the solution is to have 2 pointers run with the distance n. When get to the node need to be deleted, simply link the previous node to the next node.
C++ implementation (faster than 100% and run at 0ms. lmao proud :D):
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (n == 0) return head;
ListNode *fast = head, *slow = head;
int fastIndex = 0, slowIndex = 0;
while (fast -> next != NULL) {
fast = fast -> next;
++fastIndex;
if (fastIndex - slowIndex > n) {
slow = slow -> next;
++slowIndex;
}
}
// For edge case
int linkedListSize = fastIndex + 1;
if (linkedListSize == n) return head -> next;
// Deleting by wiring previous to after deleting element
slow -> next = slow -> next -> next;
return head;
}
};
Python implementation:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
if n == 0: return head
fast: ListNode = head
slow: ListNode = head
fastIndex = slowIndex = 0
while fast.next != None:
fast = fast.next
fastIndex += 1
if fastIndex - slowIndex > n:
slow = slow.next
slowIndex += 1
linkedListSize: int = fastIndex + 1
if n == linkedListSize:
return head.next
# Deleting
slow.next = slow.next.next
return head
Day 6: 3. Longest Substring Without Repeating Character
The general idea is: Store the last position that does not contain a certain character, for every character in the string. When meet the next occurence of that character, we can immediately know length of the longest substring up to that point.
C++ implementation:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int maxcount = 0;
unordered_map<char, int> index;
for (int left = 0, right = 0; right < s.size(); ++right) {
if (index.find(s[right]) != index.end()) {
left = max(left, index[s[right]]);
}
maxcount = max(maxcount, right - left + 1);
index[s[right]] = right + 1;
}
return maxcount;
}
};
Python implementation:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
maxcount: int = 0
indexes: dict = {}
i = 0
for j in range(len(s)):
if s[j] in indexes:
i = max(i, indexes[s[j]])
maxcount = max(maxcount, j - i + 1)
indexes[s[j]] = j + 1
return maxcount
Day 6: 567. Permutation in String
Just count. Since a permutation can never be longer than s1, let’s just iterate through s2 with a sliding window of length s1 and check if it’s a permutation by counting number of occurence of every characters.
C++ implementation:
class Solution {
public:
bool checkInclusion(string s1, string s2) {
if (s1.size() > s2.size())
return false;
array<int, 26> s1map = {}; // all elements will be init to 0
for (auto c : s1)
++s1map.at((int)(c - 'a'));
for (int start = 0; start < s2.size() - s1.size() + 1; ++start) {
array<int, 26> s2map = {};
for (int i = start; i < start + s1.size(); ++i)
++s2map.at((int)(s2[i] - 'a'));
if (s1map == s2map)
return true;
}
return false;
}
};
Python implementation:
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
s1map = [0] * 26
for char in s1:
s1map[ord(char) - ord('a')] += 1
# Sliding window
for start in range(len(s2) - len(s1) + 1):
s2map = [0] * 26
for char in range(start, start + len(s1)):
s2map[ord(s2[char]) - ord('a')] += 1
if s1map == s2map:
return True
return False
Daily coding problems
December 2nd: 328. Odd Even Linked List
Accepted Python solution:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def move2Nodes(self, node: ListNode) -> ListNode:
node.next = node.next.next
return node.next
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head == None:
return head
oddNode: ListNode = head
evenNode: ListNode = head.next
firstEvenElement: ListNode = evenNode
while evenNode != None and evenNode.next != None:
oddNode = self.move2Nodes(oddNode)
evenNode = self.move2Nodes(evenNode)
oddNode.next = firstEvenElement
return head
Accepted C++ solution:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void movePointer2Nodes(ListNode*& pointer) {
pointer -> next = pointer -> next -> next;
pointer = pointer -> next;
}
ListNode* oddEvenList(ListNode* head) {
if (head == NULL) {
return head;
}
ListNode *oddPointer = head, *evenPointer = head -> next;
ListNode *firstEvenElement = evenPointer;
// Intuition: Use 2 pointers,
// iterate them by 2 nodes in turn,
// then link the last element of odd to
// the first element of even
while (evenPointer != NULL && evenPointer -> next != NULL) {
movePointer2Nodes(oddPointer);
movePointer2Nodes(evenPointer);
}
oddPointer -> next = firstEvenElement;
return head;
}
};
However, this one got Runtime Error:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void movePointer2Nodes(ListNode*& pointer) {
pointer -> next = pointer -> next -> next;
pointer = pointer -> next;
}
ListNode* oddEvenList(ListNode* head) {
ListNode *oddPointer = head, *evenPointer = head -> next;
ListNode *firstEvenElement = evenPointer;
// Intuition: Use 2 pointers,
// iterate them by 2 nodes in turn,
// then link the last element of odd to
// the first element of even
while (evenPointer != NULL && evenPointer -> next != NULL) {
movePointer2Nodes(oddPointer);
movePointer2Nodes(evenPointer);
}
oddPointer -> next = firstEvenElement;
return head;
}
};
without comparing it with the above accepted code, can you figure out where’s the flaw? :D
December 7th: 1290. Convert Binary Number in a Linked List to Interger
Nothing much to discuss here. Let’s do some elementary math.
At first I thought bitwise operators must be faster than doing normal operations, so I tried this:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
int getDecimalValue(ListNode* head) {
int decimal = 0;
ListNode* node = head;
while (node != NULL) {
decimal = (decimal << 1) | node -> val;
node = node -> next;
}
return decimal;
}
};
And it ran at 7ms. Not that bad. However, when I change this line:
decimal = (decimal << 1) | node -> val;
Which are bitwise operators, to normal operators:
decimal = decimal * 2 + node -> val;
It ran at 4ms - slightly faster. Why?
By the way, here’s the Python implementation (faster than 97.4%, and please don’t care about space complexity lol):
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def getDecimalValue(self, head: ListNode) -> int:
digits: List[str] = []
node = head
while node != None:
digits.append(str(node.val))
node = node.next
return int("".join(digits), 2)
December 8th: 563. Binary Tree Tilt
Just basic recursive function. To find the tilt of a node, we first need to find its children sum. The same is also true for higher nodes, hence this C++ implementation:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int nodeSum(TreeNode* node, int& total) {
if (node == NULL)
return 0;
int leftSum = nodeSum(node -> left, total);
int rightSum = nodeSum(node -> right, total);
total += abs(leftSum - rightSum);
return leftSum + rightSum + node -> val;
}
int findTilt(TreeNode* root) {
int answer = 0;
nodeSum(root, answer);
return answer;
}
};
Faster than 95.64% by the way :D. And here’s Python version of that exact algorithm:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findTilt(self, root: Optional[TreeNode]) -> int:
answer: int = 0
def nodeSum(node: TreeNode):
nonlocal answer
if node == None:
return 0
leftSum: int = nodeSum(node.left)
rightSum: int = nodeSum(node.right)
tilt = abs(leftSum - rightSum)
answer += tilt
return node.val + leftSum + rightSum
nodeSum(root)
return answer
December 9th: 1306. Jump Game III
What came to your mind first? Recursive check function, right?
I’ve to admit, it’s quite slow and memory-ineffective. But hey, it’s simple to understand, and relatively short to implement. :D
class Solution {
public:
bool canReach(vector<int>& arr, int start) {
if (start < 0 || start > arr.size() || arr[start] < 0)
return false;
if (arr[start] == 0) return true;
arr[start] *= -1; // mark iterated indexes
return canReach(arr, start + arr[start]) || canReach(arr, start - arr[start]);
}
};
Here’s Python-translated version:
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
# Depth first search
if start < 0 or start >= len(arr) or arr[start] < 0:
return False
if arr[start] == 0:
return True
arr[start] *= -1
return self.canReach(arr, start + arr[start]) or self.canReach(arr, start - arr[start])
December 13th: 1446. Consecutive Characters
Nothing much here - just count it! :v
Here’s 93.39% faster than others Python implementation:
class Solution:
def maxPower(self, s: str) -> int:
if len(s) <= 1:
return len(s)
maxPower = 0
power = 0
currentChar: chr = s[0]
for char in s:
if char == currentChar:
power += 1
maxPower = max(power, maxPower)
else:
currentChar = char
power = 1
return maxPower
And 100% faster, 0ms execution time C++ implementation:
class Solution {
public:
int maxPower(string s) {
if (s.size() == 1)
return s.size();
char currentChar = s[0];
int power = 0, maxPower = 0;
for (char c:s) {
if (c == currentChar)
maxPower = max(maxPower, ++power);
else {
currentChar = c;
power = 1;
}
}
return maxPower;
}
};
December 14th: 938. Range Sum of BST
Another nothing-much-to-say problem. Let’s just traverse the tree and do exactly as the problem required.
Here’s the Python implementation:
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
if root == None: return 0
if low <= root.val and root.val <= high:
return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)
return self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)
And the C++ implementation:
class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
if (root == NULL) return 0;
if (low <= root -> val && root -> val <= high)
return root -> val + rangeSumBST(root -> left, low, high) + rangeSumBST(root -> right, low, high);
return rangeSumBST(root -> left, low, high) + rangeSumBST(root -> right, low, high);
}
};
Try to guess the performance of them both? :D
To my surprise, here’s a comparison of that exact algorithm in 2 languages:
See the difference? C++ ran twice as fast, with 3 times as much memory usage. An unexpected trade-off. Guess the Python’s garbage collector’s shown off its mightiness after all. :D