logologo
“That which we need the most will be found where we least want to look.” - Carl Jung.

Feb 2023 Daily Leetcode: Leetcode in C++/RUST

48. Sort List

Description

Given the head of a linked list, return the list after sorting it in ascending order.

Solution

Merge sort is constantly used when it comes to sort a linked list. This question also appears in my algorithm course's final exam.

  • Runtime: O(nlgn)
  • Space: O(lgn) - O(lgn) is the call graph
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    ListNode* sortList(ListNode* head) {
14        // empty list or only one element
15        if(!head||!head->next) 
16            return head;
17        ListNode* mid = split(head);
18        ListNode* left = sortList(head);
19        ListNode* right = sortList(mid);
20        
21        return merge(left,right);
22    }
23    
24    // famous two finger algorithm
25    ListNode* merge(ListNode* f1, ListNode* f2){
26        ListNode* sentinel = new ListNode(0);
27        ListNode* it = sentinel;
28        
29        while(f1&&f2){
30            if(f1->val < f2->val) {
31                it->next = f1;
32                f1 = f1->next;
33            }
34            else{
35                it->next = f2;
36                f2 = f2->next;
37            }
38            it = it->next;
39        }
40        
41        while(f1){
42            it->next = f1;
43            f1 = f1->next;
44            it = it->next;
45        }
46        
47        while(f2){
48            it->next = f2;
49            f2 = f2->next;
50            it = it->next;
51        }
52        
53        return sentinel->next;
54    }
55    
56    ListNode* split(ListNode* head) {
57        ListNode *midPrev = nullptr;
58        while(head && head->next) {
59            midPrev = (midPrev == nullptr) ? head : midPrev->next;
60            head = head->next->next;
61        }
62        ListNode* mid = midPrev->next;
63        // detach the linked list into two halves
64        midPrev->next = nullptr;
65        
66        // return the second half, i.e, the detached
67        return mid;
68    }
69};

2131. Longest Palindrome by Concatenating Two Letter Words

Description

You are given an array of strings words. Each element of words consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

A palindrome is a string that reads the same forward and backward.

Solution

  • Runtime: O(n)
  • Space: O(n)
1class Solution {
2public:
3    int longestPalindrome(vector<string>& words) {
4        unordered_map<string, int> table;
5        int result = 0;
6        for(auto str: words){
7            string rev(1,str[1]);
8            rev+=str[0];
9            if(table[rev]>0){
10                table[rev]-=1;
11                result+=4;
12            }
13            else{
14                table[str]+=1;
15            }
16        }
17        for(auto it:table){
18            if(it.second>0&&it.first[0]==it.first[1]){
19                result+=2;
20                return result;
21            }
22        }
23        
24        return result;
25    }
26};

621. Task Scheduler

Description

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

Solution

  • Runtime: O(n)
  • Space: O(1) : O(26) to be precise.
1class Solution {
2public:
3    int leastInterval(vector<char>& tasks, int n) {
4        unordered_map<char, int> table;
5        for(char &c:tasks){
6            table[c]++;
7        }
8        
9        int time = 0;
10
11        // greedy algorithm, the most heavy tasks goes first, use a max heap to retrieve the heavies taks in log26
12        priority_queue<int> readyQueue;
13        for(auto it:table){
14            if(it.second>0)
15                readyQueue.push(it.second);
16        }
17
18        // (a, b):  - a is the remaining cycles needed to complete this task
19        //          - b is the next time this task can be executed
20        queue<pair<int,int>> waitQueue;
21
22        // if there is tasks remaining
23        while(!readyQueue.empty() || !waitQueue.empty()){
24            time++;
25            // if there is work in ready queue
26            if(!readyQueue.empty()){
27                // remove the task 
28                int occur = readyQueue.top();
29                readyQueue.pop();
30                if(occur-1>0)
31                    // move the task to waitQueue, and "do" 1 cycle's work
32                    waitQueue.push({occur-1,time+n});
33            }
34            
35            // if there is work in the waitQueue
36            if(!waitQueue.empty()){
37                // the front() would always has the smallest wake time
38                // check if we can wake up the earliest task
39                if(waitQueue.front().second<=time){
40                    // wake up the task
41                    readyQueue.push(waitQueue.front().first);
42                    waitQueue.pop();
43                }
44            }
45        }
46    
47        return time;
48    }
49};

543. Diameter of Binary Tree

Description

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Solution

  • Runtime: O(n)
  • Space: O(n) : call stack if the tree is a straight line
1/**
2* Definition for a binary tree node.
3* struct TreeNode {
4*     int val;
5*     TreeNode *left;
6*     TreeNode *right;
7*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10* };
11*/
12class Solution {
13public:
14   int diameterOfBinaryTree(TreeNode* root) {
15       int maxD = 0;
16       diamaterHelper(root, maxD);
17       return maxD;
18   }
19
20
21   int diameterHelper(TreeNode* root, int &maxD){
22       if(root==nullptr){
23           return 0;
24       }
25      
26       int left = diameterHelper(root->left, maxD);
27       int right = diameterHelper(root->right, maxD);
28
29
30       // two cases, the maximum is the left height + right height
31       // tree rooted at this node is not optimal, pass up the height
32       if(left+right>maxD)
33           maxD = left+right
34       return max(left,right)+1;
35   }
36};

437. Path Sum III

Description

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Solution

  • Runtime: O(n^2)
  • Space: O(n) : call stack if the tree is a straight line
1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    int pathSum(TreeNode* root, int targetSum) {
15        if(root==nullptr){
16            return 0;
17        }
18        // consider two cases
19        // 1: the root is included in the path -> pathSumInclude
20        // 2: the root is not included in the path -> pathSum
21        return pathSumInclude(root, targetSum)+pathSum(root->left,targetSum)+pathSum(root->right,targetSum);
22    }
23    
24    int pathSumInclude(TreeNode* root, long targetSum) {
25        if(root==nullptr){
26            return 0;
27        }
28        // if we find what we wanted, add 1 
29        if(root->val==targetSum){
30            // but we still need to recurse because there might be nodes added up to 0
31            return 1+pathSumInclude(root->left, targetSum-root->val)+pathSumInclude(root->right, targetSum-root->val);
32        }
33        else{
34            // we need to recurse using pathSumInclude because the path should be continous
35            return pathSumInclude(root->left, targetSum-root->val)+pathSumInclude(root->right, targetSum-root->val);
36        }
37    }
38};

74. Search a 2D Matrix

Description

You are given an m x n integer matrix matrix with the following two properties:

Each row is sorted in non-decreasing order. The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Solution

If you flatten the matrix in to an one-dimension array with size of m*n, the 1d array will be in non decreasing order. Thus, we can perform binary search on the 1d array. The mid indice translation is matrix[mid/n][mid%n]

  • Runtime: O(lg(m*n))
  • Space: O(1)
1class Solution {
2public:
3    bool searchMatrix(vector<vector<int>>& matrix, int target) {
4        int m = matrix.size(), n = matrix[0].size();
5        int left = 0, right = m*n-1;
6        
7        while(left < right){
8            int mid = (left+right)/2;
9            if(matrix[mid/n][mid%n]<target){
10                left = mid+1;
11            }
12            else if (matrix[mid/n][mid%n]>target)
13            {
14                right = mid-1;
15            }
16            else{
17                return true;
18            }
19        }
20        return matrix[left/n][left%n]==target;
21    }
22};

33. Search in Rotated Sorted Array

Description

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Solution

The only difference between this problem with ordinary binary search is there is a pivot point where the ascending ordered list is rotated. If we can find the pivot point, the problem just rolls back to a binary search problem.

  • Runtime: O(lgn)
  • Space: O(1)
1class Solution {
2public:
3    int search(vector<int>& nums, int target) {
4        int low = 0, high = nums.size() - 1;
5
6        // find the smallest element => pivot point
7        while (low < high)
8        {
9            int mid = (low + high) / 2;
10
11            if (nums[mid] > nums[high])
12            {
13                low = mid + 1;
14            }
15            else
16            {
17                high = mid ;
18            }
19        }
20        // find the point that is the pivot
21        int pivot = low;
22
23        low = 0, high = nums.size() - 1;
24        // find the element
25        while (low <= high)
26        {
27            int mid = (low + high) / 2;
28            int realmid = (mid + pivot) % nums.size();
29
30            if (nums[realmid] == target)
31            {
32                return realmid;
33            }
34
35            if (nums[realmid] < target)
36            {
37                low = mid+1;
38            }
39            else{
40                high = mid-1;
41            }
42        }
43
44        return -1;
45    }
46};

108. Convert Sorted Array to Binary Search Tree

Description

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Solution

  • Runtime: O(n)
  • Space: O(1)
1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    TreeNode* sortedArrayToBST(vector<int>& nums) {
15        if(nums.size()>0){
16            TreeNode *sentinel = new TreeNode();
17            // build the tree rooted the sentinel's left child
18            helper(sentinel, nums, 0, nums.size()-1, true);
19            return sentinel->left;
20        }
21        return nullptr;
22    }
23    
24    void helper(TreeNode* parent,vector<int>& nums, int left, int right,bool leftChild ){
25
26        if(left<=right){
27            // get the mid element
28            int mid = (left+right)/2;
29            // create new node
30            TreeNode *temp = new TreeNode(nums[mid]);
31            // attach to parent's left
32            if(leftChild){
33                parent->left = temp;
34            } // attach to parent's right
35            else {
36                parent->right = temp;
37            }
38            // recursive build subtrees
39            helper(temp, nums, left, mid-1, true);
40            helper(temp, nums, mid+1, right, false);
41        }
42    }
43};

230. Kth Smallest Element in a BST

Description

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Solution

  • Runtime: O(n)
  • Space: O(n)
1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    int kthSmallest(TreeNode* root, int k) {
15        // this could be done in an inorder traversal
16        // inorder traversal is a form of DFS
17        // use stack to carry the dfs
18        stack<TreeNode*> stack;
19
20        while(!stack.empty()||root){
21            // keep descend to the most left leaf
22            while(root){
23                stack.push(root);
24                root = root -> left;
25            }
26            // traversal backwards
27            root = stack.top();
28            stack.pop();
29         
30            if(--k==0){
31                // if the current is kth smallest, return
32                return root->val;
33            }
34            else{
35                // traversal on the right substree
36                root = root ->right;
37            }
38        }
39        return -1;
40    }
41};

173. Binary Search Tree Iterator

Description

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.

boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.

int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

Solution

  • Runtime: O(1): each operation is constant
  • Space: O(n)
1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class BSTIterator {
13private: 
14    vector<int> nums;
15    int ptr = 0;
16
17    void inorder(TreeNode* root){
18        if(root){
19            inorder(root->left);
20            nums.push_back(root->val);
21            inorder(root->right);
22        }
23    }
24
25public:
26    BSTIterator(TreeNode* root) {
27        inorder(root);
28    }
29    
30    int next() {
31        return nums[ptr++];
32        
33    }
34    
35    bool hasNext() {
36        return ptr < nums.size();
37    }
38};
39
40/**
41 * Your BSTIterator object will be instantiated and called as such:
42 * BSTIterator* obj = new BSTIterator(root);
43 * int param_1 = obj->next();
44 * bool param_2 = obj->hasNext();
45 */

994. Rotting Oranges

Description

You are given an m x n grid where each cell can have one of three values:

0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Solution

  • Runtime: O(mn)
  • Space: O(mn)
1class Solution {
2public:
3    int orangesRotting(vector<vector<int>>& grid) {
4        int m = grid.size();
5        int n = grid[0].size();
6        queue<pair<int,int>> rotten;
7        int fresh = 0;
8        // find the intiial rotten oranges
9        // count the initial number of fresh oranges
10        for(int i=0; i<m; i++){
11            for(int j=0; j<n; j++){
12                if(grid[i][j]==1){ // fresh oranges
13                    fresh++;
14                }
15                else if(grid[i][j]==2){ // rotten oranges
16                    rotten.push({i,j});
17                    // grid[i][j] = -1;
18                }
19            }
20        }
21        int mins = 0;
22        
23        vector<pair<int,int>> directions = {{0,1},{0,-1},{1,0},{-1,0}};
24
25        while(!rotten.empty() && fresh>0){
26            int times = rotten.size();
27            // take a snapshot of the queue at this minute
28            
29            for(int k=0; k<times; k++){
30                auto ro = rotten.front();
31                rotten.pop();
32                for(auto dir : directions) {
33                    int row = ro.first + dir.first;
34                    int col = ro.second + dir.second;
35                    if(row >=0 && row<m && col>=0 && col<n && grid[row][col]==1){
36                        grid[row][col]=2;
37                        rotten.push({row,col});
38                        fresh--;
39                    }
40                }
41            }
42            mins++;
43        }
44
45        return fresh>0?-1:mins;
46    }
47};

417. Pacific Atlantic Water Flow

Description

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Solution

<!-- - Runtime: `O()` - Space: `O()` --> 
1class Solution {
2public:
3    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
4        
5    }
6};

210. Course Schedule II

Description

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Solution

  • Runtime: O()
  • Space: O()