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

Jan 2023 Daily Leetcode: Leetcode in Rust/C++

Introduction

In the past, I have tried to improve my algorithm skills but I didn't stick with it. To motivate myself and stay on track, I plan to solve at least one algorithm per day and document my progress in this post. Additionally, I want to practice my favorite programming language, Rust, by writing the code for these algorithms in it. This will help me become more familiar with Rust.

Leetcode

1480. Running sum of 1d Array

Description

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Solution

  • Runtime: O(n)
  • Space: O(n)
1impl Solution {
2    pub fn running_sum(nums: Vec<i32>) -> Vec<i32> {
3        let mut sum: i32 = 0;
4        let mut results: Vec<i32> = vec![0; nums.len()];
5        for i in 0..nums.len() {
6            sum += nums[i];
7            results[i] = sum;
8        }
9
10        results
11    }
12}

724. Find Pivot Index

Description

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

Solution

  • Runtime: O(n)
  • Space: O(1)
1impl Solution {
2    pub fn pivot_index(nums: Vec<i32>) -> i32 {
3        // right = the total sum of the array at the beginning
4        let mut right:i32 = nums.iter().sum();
5        let mut left:i32 = 0;
6
7        // find the pivot by deciding if current is the pivot
8        for (i, x) in nums.iter().enumerate() {
9            right -= x;
10            if left == right {
11                return i as i32;
12            }
13            left += x;
14        }
15        // return -1 if no pivot
16        -1
17    }
18}

205. Isomorphic Strings

Description

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Solution

  • Runtime: O(n)
  • Space: O(n)
1use std::collections::HashMap;
2
3impl Solution {
4    pub fn is_isomorphic(s: String, t: String) -> bool {
5        if s.len() != t.len() {
6            return false;
7        }
8        let mut s_map = HashMap::new();
9        let mut t_map = HashMap::new();
10        
11        for (i, (sc,tc)) in s.chars().zip(t.chars()).enumerate() {
12            // get the mapped char in t, or insert the associated char tc
13            let s_entry = s_map.entry(sc).or_insert(tc);
14            // get the mapped char in s, or insert the associated char sc
15            let t_entry = t_map.entry(tc).or_insert(sc);
16
17            // key point is that
18            //  no two chars mapped to same char, for both chars in s and t
19            // *s_entry != tc <=> sc is already mapped to another char that is not tc
20            // *t_entry != sc <=> tc is already mapped to another char that is not sc
21            if  *s_entry != tc || *t_entry != sc {
22                return false;
23            }
24        }
25        true
26    }
27}

392. Is Subsequence

Description

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Solution

  • Runtime: O(n)
  • Space: O(1)
1use std::collections::HashMap;
2impl Solution {
3    pub fn is_subsequence(s: String, t: String) -> bool {
4        let mut s_iter = s.chars().peekable();
5        for c in t.chars() {
6            // early stop if s reaches the end before t is finished
7            if s_iter.peek().is_none() {
8                return true;
9            }
10            else if Some(c) == s_iter.peek().map(|x| *x) {
11                // advance s iterator
12                print!("{:?}",s_iter.peek().map(|x| *x));
13                s_iter.next();
14            }
15        }
16        
17        // check if s iterator reaches the end
18        if s_iter.peek().is_none() {
19            return true;
20        }
21
22        return false;
23    }
24}

21. Merge Two Sorted Lists

Description

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Solution

The algorithm is also called Two Finger Algorithm.

  • Runtime: O(n)
  • Space: O(1)
1// Definition for singly-linked list.
2// #[derive(PartialEq, Eq, Clone, Debug)]
3// pub struct ListNode {
4//   pub val: i32,
5//   pub next: Option<Box<ListNode>>
6// }
7// 
8// impl ListNode {
9//   #[inline]
10//   fn new(val: i32) -> Self {
11//     ListNode {
12//       next: None,
13//       val
14//     }
15//   }
16// }
17impl Solution {
18    pub fn merge_two_lists(list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
19        let mut sentinel = Box::new(ListNode::new(0));
20        let mut current = &mut sentinel;
21        // redeclaring into mutable
22        let mut list1 = list1;
23        let mut list2 = list2;
24
25        // while if both linkedlist is not appended
26        while list1.is_some() || list2.is_some() {
27            if let (Some(ref box1), Some(ref box2)) = (list1.as_ref(), list2.as_ref()) {
28                // add the header of list 1
29                if box1.val < box2.val {
30                    // move to the current, current takes the ownship
31                    // note current is the Box type
32                    current.next = list1.take();
33                    // list1 = list1.next = the following ...
34                    list1 = current.next.as_mut().unwrap().next.take();
35                } else {
36                    current.next = list2.take();
37                    list2 = current.next.as_mut().unwrap().next.take();
38                }
39            }
40            else if list1.is_some() {
41                current.next = list1.take();
42                    // list1 = list1.next = the following ...
43                list1 = current.next.as_mut().unwrap().next.take();
44            } 
45            else {
46                current.next = list2.take();
47                list2 = current.next.as_mut().unwrap().next.take();
48            }
49
50            current = current.next.as_mut().unwrap();
51        } 
52        sentinel.next
53    }
54}

206. Reverse Linked List

Description

Given the head of a singly linked list, reverse the list, and return the reversed list.

Solution

  • Runtime: O(n)
  • Space: O(1)
1// Definition for singly-linked list.
2// #[derive(PartialEq, Eq, Clone, Debug)]
3// pub struct ListNode {
4//   pub val: i32,
5//   pub next: Option<Box<ListNode>>
6// }
7// 
8// impl ListNode {
9//   #[inline]
10//   fn new(val: i32) -> Self {
11//     ListNode {
12//       next: None,
13//       val
14//     }
15//   }
16// }
17use std::mem;
18impl Solution {
19    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
20        let mut reversed_list: Option<Box<ListNode>> = None;
21        let mut current_node = head;
22
23        while let Some(mut node) = current_node {
24            // replace next with none, but return the old next
25            current_node = mem::replace(&mut node.next, None);
26            // attached the reversed_list in the next
27            node.next = reversed_list;
28            // put node as header of th reversed_list
29            reversed_list = Some(node);
30        }
31        reversed_list
32    }
33}
  • Runtime: O(n)
  • Space: O(1)
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* reverseList(ListNode* head) {
14        if(head==nullptr) {
15            return head;
16        }
17
18        ListNode* prev = nullptr;
19        ListNode* curr = head;
20        ListNode* next = head->next;
21
22        while(next) {
23            curr->next = prev;
24            prev = curr;
25            curr = next;
26            next = next->next;
27        }
28        curr->next = prev;
29        return curr;
30    }
31};

Switching to C++

I have to admit that Rust is a very difficult language for me and some of the functions in the standard library seem like magic to me. Coding algorithms in Rust has been distracting for me because I have to focus so much on the language itself. Therefore, for the rest of this blog, I will be using C++ instead.

876. Middle of the Linked List

Description

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Solution

The easiest way is to count the number of nodes in the linked list and reiterate the linked list from the head. However, this takes two passes through the same linked list. A better solution takes one pass. We need to use two pointers, one is faster, one is slower. When the faster one reaches the end, the slower one reaches the middle of the linked list.

  • Runtime: O(n)
  • Space: O(1)
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* middleNode(ListNode* head) {
14        ListNode *fast, *slow = head;
15
16        while (fast->next!=nullptr) {
17            slow = slow->next;
18            // if there is even length of nodes
19            if (fast->next->next == nullptr) {
20                break;
21            }
22            fast = fast->next->next;
23        }
24        return slow;
25    }
26};

142. Linked List Cycle II

Description

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Solution

Similar idea to the last question - Middle of the linked list, we need a fast pointer and a slow pointer. When the fast pointer catches the slow pointer, there is a cycle. However, finding and returning the exact entry node of the cycle is non-trivial. The algorithm is called Floyd Algorithm and it is Okay if one spend one hour just to understand it. Remeber,when you are tackling this problem you are as creative as Floyd was solving the exact same problem.

  • Runtime: O(n) <=> algorithm stops when slow pointer reaches the entry of the loop
  • Space: O(1) <=> three pointers
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9class Solution {
10public:
11    ListNode *detectCycle(ListNode *head) {
12        // trivial
13        if(!head||!head->next){
14            return nullptr;
15        }
16        ListNode *slow = head;
17        ListNode *fast = head;
18        ListNode *entry = head;
19
20        // slow is slower than fast, so we break the eloop when fast reaches the end
21        while(fast->next&&fast->next->next) {
22            slow = slow->next;
23            fast = fast->next->next;
24            // slow and fast meets => there is a loop 
25            if(slow == fast) {
26                // need to find the entry point of the loop;
27                // distance from head to the node = distance from the meet point to the node(forward direction)
28                while(entry!=slow) {
29                    entry = entry->next;
30                    slow = slow->next;
31                }
32                return entry;
33            }
34        }
35
36        // no loop
37        return nullptr;
38    }
39};

121. Best Time to Buy and Sell Stock

Description

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Solution

We want to buy low and sell high. We keep two pointers, one is for identify the low, and the other one is to identify the high. Ask ourselves one question "You currently have low and high, how can you improve the profit?" => new low, and new high.

  • Runtime: O(n)
  • Space: O(1)
1class Solution {
2public:
3    int maxProfit(vector<int>& prices) {
4        int max = 0;
5        int low = prices[0];
6        int high = prices[0];
7        
8        for(int i:prices){
9            if(i > high){
10                high = i;
11                if(high-low > max)
12                    max = high - low;
13            }
14            else if (i<low){
15                // need to reset high, since we cannot sell on previous dates
16                low = high = i;
17            }
18        }
19        
20        return max;
21    }
22};

409. Longest Palindrome

Description

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

An example is

Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

Solution

The order of the characters in the string does not matter, you can construct your own palindrome with existing characters. Thus, the answer is a simple greedy algorithm. The intuition is to add two same character to the palindrome whenever encountered.

  • Runtime: O(n)
  • Space: O(n)
1class Solution {
2public:
3    int longestPalindrome(string s) {
4        unordered_set<char> set;
5        int result = 0;
6        //  add two same character to the palindrome whenever encountered
7        for(char i : s){
8            if(set.find(i) != set.end()){
9                set.erase(i);
10                result += 2;
11            }
12            else{
13                set.insert(i);
14            }
15        }
16
17        // If we have a spare, unique character at our disposal, we can insert it in the middle of our palindrome to create a new one.
18        if(!set.empty()){
19            result += 1;
20        }
21
22        return result;
23    }
24};

589. N-ary Tree Preorder Traversal

Description

Given the root of an n-ary tree, return the preorder traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

Solution

  • Runtime: O(n)
  • Space: O(1)
1/*
2// Definition for a Node.
3class Node {
4public:
5    int val;
6    vector<Node*> children;
7
8    Node() {}
9
10    Node(int _val) {
11        val = _val;
12    }
13
14    Node(int _val, vector<Node*> _children) {
15        val = _val;
16        children = _children;
17    }
18};
19*/
20
21class Solution {
22public:
23    vector<int> preorder(Node* root) {
24        vector<int> result;
25        preorder_traverse(root, result);
26        return result;
27    }
28    
29    void preorder_traverse(Node* node, vector<int> &result){
30        if(!node){
31            return;
32        }
33        result.push_back(node->val);
34        for(auto child:node->children){
35            preorder_traverse(child,result);
36        }
37    }
38};

An interative solution is

1class Solution {
2public:
3    vector<int> preorder(Node* root) {
4        if(!root){
5            return {};
6        }
7        
8        vector<int> result;
9        stack<Node *> nodes;
10        nodes.push(root);
11        
12        Node* curr;
13        while(!nodes.empty()){
14            curr = nodes.top();
15            nodes.pop();
16            result.push_back(curr->val);
17            
18            for(int i=curr->children.size()-1 ;i>=0;i--){
19                nodes.push(curr->children[i]);
20            }
21            
22        }
23        
24        return result;
25    }
26
27};

102. Binary Tree Level Order Traversal

Description

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

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    vector<vector<int>> levelOrder(TreeNode* root) {
15        if(!root) {
16            return {};
17        }
18        
19        vector<vector<int>> result;
20        vector<TreeNode *> levelNodes;
21        levelNodes.push_back(root);
22
23        while (!levelNodes.empty()) {
24            int currentLevelSize = levelNodes.size();
25            vector<int> currentLevelVals;
26            for(int i=0; i< currentLevelSize; i++){
27                // get the val into 
28                currentLevelVals.push_back(levelNodes[i]->val);
29                // push left to next level
30                if(levelNodes[i]->left){
31                    levelNodes.push_back(levelNodes[i]->left);
32                }
33                // push right to next level
34                if(levelNodes[i]->right){
35                    levelNodes.push_back(levelNodes[i]->right);
36                }
37            }
38            // erase last level nodes
39            levelNodes.erase(levelNodes.begin(),levelNodes.begin()+currentLevelSize);
40            result.push_back(currentLevelVals);
41        }
42
43        return result;
44    }
45};

102. Binary Tree Level Order Traversal

Description

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

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

Solution

  • Runtime: O(lgn)
  • Space: O(1)
1class Solution {
2public:
3    int search(vector<int>& nums, int target) {
4        int left = 0;
5        int right = nums.size()-1;
6
7        while(left <= right) {
8            int mid = (left+right)/2;
9            if(nums[mid] == target){
10                return mid;
11            } 
12            else if (nums[mid] > target){ // look at the left side
13                right = mid - 1;
14            }
15            else { // look at right side
16                left = mid + 1;
17            }
18        }
19
20        return -1;
21    }
22};

278. First Bad Version

Description

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Solution

  • Runtime: O(lgn)
  • Space: O(1)
1// The API isBadVersion is defined for you.
2// bool isBadVersion(int version);
3
4class Solution {
5public:
6    int firstBadVersion(int n) {
7        int left = 1;
8        int right = n;
9
10        while(left <= right) {
11            // ... this seems awkward, but this is the right way to get mid without overflow
12            int mid = (left / 2) + (right / 2) + ((left % 2 + right % 2) / 2);
13            if(isBadVersion(mid)){
14                if(mid==1 || !isBadVersion(mid-1))
15                    return mid;
16                else 
17                    right = mid - 1;
18            } 
19            else { // look at right side
20                left = mid + 1;
21            }
22        }
23
24        return -1;
25    }
26};

98. Validate Binary Search Tree

Description

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

Solution

This algorithm relies on the fact that inorder traversal of a valid binary search tree is in increasing(in some other problems, non-decreasing) order

  • Runtime: O(lgn)
  • 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    bool isValidBST(TreeNode* root) {
15        if(!root)
16        {
17            return true;
18        }
19        // DFS - stack, BFS - queue
20        std::vector<TreeNode *> stack;
21        TreeNode *pre = nullptr;
22
23        while(root||!stack.empty())
24        {
25            while(root)
26            {
27                // put all the in-node in the stack
28                stack.push_back(root);
29
30                // all the way to the most left
31                root = root->left;
32            }
33            // go up
34            root = stack.back();
35            stack.pop_back();
36            
37            // check if bigger than the previous node
38            if(pre && root->val <= pre->val)
39            {
40                return false;
41            }
42            // update previous
43            pre = root;
44            // go right branch
45            root = root->right;
46        }
47        return true;
48    }
49};

A fancy way to do inorder traversal.

1public List<Integer> inorderTraversal(TreeNode root) {
2    List<Integer> list = new ArrayList<>();
3    if(root == null) return list;
4    Stack<TreeNode> stack = new Stack<>();
5    while(root != null || !stack.empty()){
6        while(root != null){
7            stack.push(root);
8            root = root.left;
9        }
10        root = stack.pop();
11        list.add(root.val);
12        root = root.right;
13        
14    }
15    return list;
16}

235. Lowest Common Ancestor of a Binary Search Tree

Description

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Solution

  • Runtime: O(lgn)
  • 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(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10
11class Solution {
12public:
13    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
14        if(q->val<p->val){
15            swap(q,p);
16        }
17        
18        if(root==p||root==q||(root->val < q->val&&root->val > p->val)){
19            return root;
20        }
21        else if(root->val > q->val && root->val > p->val){
22            return lowestCommonAncestor(root->left, p, q);
23        }
24        else{
25            return lowestCommonAncestor(root->right, p, q);
26        }
27    }
28};

733. Flood Fill

Description

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.

Return the modified image after performing the flood fill.

Solution

  • Runtime: O(mn)
  • Space: O(1)

This algorithm also teaches how to traverse a 2d array with DFS.

1class Solution {
2public:
3    void dfs(vector<vector<int>> &image, int i, int j, int val, int newColor){
4        // 1.check if the [i][j] is inside the 2d array
5        // 2. check if already the color
6        // 3. check if the old color is same
7        if(i<0 || i>=image.size() || j<0 || j>= image[0].size() || image[i][j] == newColor || image[i][j] != val)
8        {
9            return;
10        }
11        // populated adjacent water
12        image[i][j] = newColor;
13        // populate/flood four directions
14        dfs(image, i-1, j, val, newColor);
15        dfs(image, i+1, j, val, newColor);
16        dfs(image, i, j-1, val, newColor);
17        dfs(image, i, j+1, val, newColor);
18    }
19    
20    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
21        dfs(image, sr, sc, image[sr][sc], color);
22        return image;
23    }
24};

200. Number of Islands

Description

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Solution

  • Runtime: O(mn)
  • Space: O(1)

This algorithm also teaches how to traverse a 2d array with DFS.

1class Solution {
2public:
3    void dfs(vector<vector<char>>&grid, int i, int j){
4        // outbound
5        if(i < 0 || i>= grid.size() || j < 0 || j>=grid[0].size()){ // note, it is grid[0].size() for the number of columns
6            return;
7        }
8        // the cell is already counted(#) or it is water (0)
9        if(grid[i][j]!='1'){
10            return;
11        }
12        
13        // mark the island as counted
14        grid[i][j]='#';
15        
16        dfs(grid, i-1, j);
17        dfs(grid, i+1, j);
18        dfs(grid, i, j-1);
19        dfs(grid, i, j+1);
20    }
21    
22    int numIslands(vector<vector<char>>& grid) {
23        int islands = 0;
24        
25        for(int i=0; i<grid.size(); i++){
26            for(int j=0; j<grid[0].size(); j++){
27                // when find a island
28                if(grid[i][j]=='1'){
29                    islands++;
30                    // use dfs to mark the entire island as counted.
31                    dfs(grid, i, j);
32                }
33            }
34        }
35        
36        return islands;
37    }
38};

509. Fibonacci Number

Description

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

Solution

  • Runtime: O(n)
  • Space: O(n)
1// a dynamic programming solution
2class Solution {
3public:
4    int fib(int n) {
5        if( n<=1 ){
6            return n;
7        }
8        
9        vector<int> table(n+1);
10        table[0] = 0;
11        table[1] = 1;
12        for(int i=2; i<table.size(); i++){
13            // fib(n) = fib(n-1) + fib(n-2)
14            table[i] = table[i-1] + table[i-2];
15        }
16        
17        return table[n];
18    }
19};

70. Climbing Stairs

Description

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution

  • Runtime: O(n)
  • Space: O(n)
1class Solution {
2public:
3    int climbStairs(int n) {
4        if (n<2){
5            return 1;
6        }else if(n==2){
7            return 2;
8        }
9        // subproblem <=> how many ways to reach top from top-i
10        vector<int> table(n+1);
11        // ahh.. table[0] is a dummy
12        table[0] = table[1] = 1;
13        table[2] = 2;
14        for(int i=3; i<table.size(); i++){
15            // either make 1 step or 2 steps
16            table[i] = table[i-1] + table[i-2]; 
17        }
18        // top-n is the starting
19        return table[n];
20    }
21};

746. Min Cost Climbing Stairs

Description

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Solution

  • Runtime: O(n)
  • Space: O(n)
1class Solution {
2public:
3    int minCostClimbingStairs(vector<int>& cost) {
4
5        int n = cost.size();
6        
7        // think backwards, table[i] = the cost of climbing to top from top-i-1... stair
8        vector<int> table(n);
9        // reaches the top from top-1
10        table[0] = cost[cost.size()-1];
11        // reaches the top from top-2
12        table[1] = cost[cost.size()-2];
13        
14        for(int i=2; i<table.size(); i++)
15        {
16            // either make 1 step or 2 steps
17            int oneStep = cost[cost.size()-i-1]+table[i-1];
18            int twoStep = cost[cost.size()-i-1]+table[i-2];
19            // plus current stair's cost
20            table[i] = min(oneStep,twoStep);
21        }
22
23        // the first step is either 1st stair, or 2nd stair
24        return min(table[n-1],table[n-2]);
25    }
26};

62. Unique Paths

Description

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Solution

  • Runtime: O(mn)
  • Space: O(mn)
1class Solution {
2public:
3
4    
5    int uniquePaths(int m, int n) {
6        vector<vector<int>> table(m, vector<int>(n));
7        // base cases
8        // can only go down
9        for(int i=0; i< m; i++){
10            table[i][n-1] = 1;
11        }
12        // can only go right
13        for(int i=0; i<n; i++){
14            table[m-1][i] = 1;
15        }
16        
17        for(int i=m-2; i>=0 ; i--){
18            for(int j=n-2; j>=0; j--){
19                // either go down or right
20                table[i][j] = table[i+1][j] + table[i][j+1];
21            }
22        }
23        
24        return table[0][0];
25    }
26};

438. Find All Anagrams in a String

Description

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Solution

  • Runtime: O(n): Note n is the size of s.
  • Space: O(1): pChars and wChars are only 26-ints constant size.
1class Solution {
2public:
3    vector<int> findAnagrams(string s, string p) {
4        if(p.size()>s.size()){
5            return {};
6        }
7        
8        vector<int> pChars(26, 0);
9        vector<int> wChars(26, 0);
10        vector<int> result;
11        
12        for(int i=0; i<p.size(); i++)
13        {
14            pChars[p[i]-'a']++;
15            wChars[s[i]-'a']++;
16        }
17        
18        if(pChars==wChars){
19                result.push_back(0);
20        }
21        
22        for(int i=p.size(); i<s.size(); i++){
23            // add new char into window 
24            wChars[s[i]-'a']++;
25            // delete last char on the left side of the window
26            wChars[s[i-p.size()]-'a']--;
27            if(pChars==wChars){
28                result.push_back(i-p.size()+1);
29            }
30        }
31        return result;
32    }
33};

424. Longest Repeating Character Replacement

Description

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Solution

Keep a window squeezed by left and right. For each window instance, find the most frequent char and its frequency. Check if the window size(number of character in the substring) can be filled by the most frequent char with k replacement. If so, enlarge right and update the maximum length; otherwise, shift left and seek new window instances starting from left+1.

  • Runtime: O(n)
  • Space: O(1)
1class Solution {
2public:
3    int characterReplacement(string s, int k) {
4        vector<int> count(26,0);
5        
6        int left = 0;
7        int mostFrequentCount = 0;
8        int maxLength = 0;
9        
10        for(int right = 0; right < s.length(); right ++ ){
11           // new char in the window
12           count[s[right]-'A']++;
13           // update the most frequent count if necessary
14           mostFrequentCount = max(mostFrequentCount, count[s[right]-'A']);
15           if(right - left + 1 - mostFrequentCount - k <= 0) {
16               maxLength = right - left + 1;
17           }
18           else {
19               // not enough replacement, shift the window to right
20               count[s[left]-'A']--;
21               left ++;
22           }
23           
24        }
25
26        return maxLength;
27        
28    }
29};

1. Two Sum

Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Solution

This question can also be solved by two pointers if the nums are ordered.

  • Runtime: O(n)
  • Space: O(n)
1class Solution {
2public:
3    vector<int> twoSum(vector<int>& nums, int target) {
4        unordered_map<int, int> occurrence;
5
6        for(int i=0 ; i< nums.size(); i++){
7            if(occurrence.find(target - nums[i])!=occurrence.end()){
8                return {occurrence[target - nums[i]], i};
9            }
10            else {
11                occurrence[nums[i]] = i;
12            }
13        }
14
15        return {};
16    }
17};

299. Bulls and Cows

Description

You are playing the Bulls and Cows game with your friend.

You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:

The number of "bulls", which are digits in the guess that are in the correct position. The number of "cows", which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.

Given the secret number secret and your friend's guess guess, return the hint for your friend's guess.

The hint should be formatted as "xAyB", where x is the number of bulls and y is the number of cows. Note that both secret and guess may contain duplicate digits.

Solution

  • Runtime: O(n)
  • Space: O(n)
1class Solution {
2public:
3    string getHint(string secret, string guess) {
4        unordered_map<char, int> occurrence;
5        
6        // count the characters in the hashmap
7        for(char &c : guess){
8            occurrence[c]++;
9        }
10        
11        // count the number of bulls, priv(bull) > priv(cow)
12        int bull = 0;
13        for(int i=0; i<secret.size(); i++){
14            if (secret[i]==guess[i]){
15                bull ++;
16                occurrence[guess[i]]--;
17            }
18        }
19        
20        // count the number of cow
21        int cow = 0;
22        for(int i=0; i<secret.size(); i++){
23            if (secret[i]!=guess[i]){
24                if (occurrence[secret[i]]>0){
25                    occurrence[secret[i]]--;
26                    cow++;
27                }
28            }
29        }
30        return to_string(bull)+"A"+to_string(cow)+"B";
31    }
32};

844. Backspace String Compare

Description

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Solution

The challenge point of this problem is to only use O(1) space in O(n) time. Intuition is the backspace character never void character after it. That is #a never voids a. Thus, if we walk the strings in reverse order, we do not need to revisiting some of the previous characters.

  • Runtime: O(n)
  • Space: O(1)
1class Solution {
2public:
3    bool backspaceCompare(string s, string t) {
4        // prepare to traverse in the reversed order
5        int i=s.size()-1, j=t.size()-1;
6        
7        // remeber how many characters to erase
8        int skip_s = 0;
9        int skip_t = 0;
10
11        // need to finish the list
12        while(i>=0 || j>=0) {
13            // walk until the next non-erased character
14            while(i>=0) {
15                if(s[i]=='#') {
16                    skip_s++;
17                    i--;
18                }
19                else if(skip_s>0){
20                    // erase a character
21                    skip_s--;
22                    i--;
23                }
24                // at the next consumable character
25                else {
26                    break;
27                }
28            }
29            // walk until the next non-erased character
30            while(j>=0 ) {
31                if(t[j]=='#') {
32                    skip_t++;
33                    j--;
34                }
35                else if(skip_t>0){
36                    // erase a character
37                    skip_t--;
38                    j--;
39                }
40                // consume another character
41                else {
42                    break;
43                }
44            }
45            // compare those two characters
46            if( i>=0 && j>=0 && s[i]!=t[j]){
47                return false;
48            }
49            if ((i >= 0) != (j >= 0))
50                    return false;
51            // so far so good, keep traversing
52            i--;
53            j--;
54        }
55        return true;
56    }
57};

394. Decode String

Description

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 10^5.

Solution

When dealing with nested structured, e.g. brackets, stack is a natural way to solve the problems. The key is to start to pop whenever encounter a closing bracket until reaches the opening bracket.

  • Runtime: O(n)
  • Space: O(n)
1class Solution {
2public:
3    string repeat(int n, string s){
4        string result;
5        for (int i=0; i<n ;i++){
6            result += s ; 
7        }
8        return result;
9    }
10    
11    string decodeString(string s) {
12        stack<string> stack;
13        
14        for(char &c : s) {
15            if(c!=']'){
16                stack.push(string(1,c));
17            }
18            else { // start to pop when closing 
19                string temp;
20                // accumulate inner chars
21                while(stack.top()!="["){
22                    temp = stack.top() + temp;
23                    stack.pop();
24                }
25                // pop '['
26                stack.pop();
27                
28                string repeation;
29                // get the number of repeating
30                while(!stack.empty() && (stack.top()[0]>='0' && stack.top()[0]<='9')){
31                    repeation = stack.top() + repeation;
32                    stack.pop();
33                }
34                // apply the repeation and push back to the stack
35                stack.push(repeat(stoi(repeation), temp));
36            }
37        }
38        
39        // concate all the stack strings to get result
40        string result;
41        while(!stack.empty()){
42            result = stack.top() + result;
43            stack.pop();
44        }
45        return result;
46    }
47};

1046. Last Stone Weight

Description

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are destroyed, and If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

Solution

Use a priority queue (max-heap) to finding the heaviest stones (stones with max weights) in O(lgn) time. Insert back the remaining in another O(lgn) time.

  • Runtime: O(nlgn)
  • Space: O(1) - no extra space consumption; simply operate on the given vector
1class Solution {
2public:
3    int lastStoneWeight(vector<int>& stones) {
4        // by default, it is max-heap
5        priority_queue<int> maxq(stones.begin(), stones.end());
6
7        while(maxq.size()>1){
8            int stone1 = maxq.top();
9            maxq.pop();
10
11            int stone2 = maxq.top();
12            maxq.pop();
13
14            int theRest = stone1 - stone2;
15            if (theRest > 0) {
16                maxq.push(theRest);
17            }
18        }
19
20        return maxq.empty()? 0:maxq.top();
21    }
22};

692. Top K Frequent Words

Description

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Solution

  • Runtime: O(nlgn)
  • Space: O(n)
1// implementation of less comparator
2class cComparator {
3public:
4    bool operator()(pair<string, int> word1, pair<string, int> word2){
5        if(word1.second == word2.second) {
6            return word1.first > word2.first;
7        }
8        else {
9            return word1.second < word2.second;
10        }
11    }
12};
13
14class Solution {
15public:
16    vector<string> topKFrequent(vector<string>& words, int k) {
17        unordered_map<string, int> occurrence;
18        // count the occurrence
19        for(string &word: words) {
20            occurrence[word]++;
21        }
22
23        // create a less comparator
24        priority_queue<pair<string,int>, vector<pair<string,int>>, cComparator> maxq;
25        
26        for(auto &it: occurrence) {
27                maxq.push({it.first, it.second});
28        }
29
30        vector<string> result;
31
32        while(!maxq.empty()) {
33            // only want to the k-biggest 
34            if(k==0){
35                break;
36            }
37            result.push_back(maxq.top().first);
38            maxq.pop();
39            k--;
40        }
41
42        return result;
43    }
44};

202. Happy Number

Description

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Solution

A naive solution is to compute powers and then replace its digits indefinitely. However, the algorithm might not be able to terminate since it could loop endlessly. Thus, we can use Floyd's Cycle-Finding algorithm (recall detecting cycle in linked list) to find a cycle then we can simply return false.

  • Runtime: O(n)
  • Space: O(1)
1class Solution {
2public:
3    int squares(int n){
4        int result = 0;
5        while(n>0){
6            if(n%10>0){
7                result += pow((n%10),2);
8            }
9            n /= 10;
10        }
11        return result;
12    }
13    
14    bool isHappy(int n) {
15        int slow = n;
16        int fast = n;
17        
18        while(slow !=1 && fast!=1) {
19            slow = squares(slow);
20            fast = squares(squares(fast));
21            
22            if(fast == 1) {
23                return true;
24            }
25            
26            if(slow==fast){
27                std::cout << slow << "," << fast << endl;
28                return false;
29            }
30        }
31        
32        return true;
33    }
34};

54. Spiral Matrix

Description

Given an m x n matrix, return all elements of the matrix in spiral order.

Solution

  • Runtime: O(mn)
  • Space: O(1)
1class Solution {
2public:
3    vector<int> spiralOrder(vector<vector<int>>& matrix) {
4        int m = matrix.size();
5        int n = matrix[0].size();
6        int top = 0, left = 0;
7        int bottom = m-1, right = n-1;
8        vector<int> result; 
9        while (top<=bottom && left<=right) {
10            // first row
11            for (int i=left; i<=right && top<=bottom; i++) {
12                result.push_back(matrix[top][i]);
13            }
14            top++;
15            // last column
16            for (int i=top; i<=bottom && left<=right; i++) {
17                result.push_back(matrix[i][right]);
18            }
19            right--;
20            // last row
21            for (int i=right; i>=left && top<=bottom; i--) {
22                result.push_back(matrix[bottom][i]);
23            }
24            bottom--;
25            // first column
26            for (int i=bottom; i>=top && left<=right; i--) {
27                result.push_back(matrix[i][left]);
28            }
29            left++;
30        }
31        return result; 
32    }
33};

1706. Where Will the Ball Fall

Description

You have a 2-D grid of size m x n representing a box, and you have n balls. The box is open on the top and bottom sides.

Each cell in the box has a diagonal board spanning two corners of the cell that can redirect a ball to the right or to the left.

A board that redirects the ball to the right spans the top-left corner to the bottom-right corner and is represented in the grid as 1. A board that redirects the ball to the left spans the top-right corner to the bottom-left corner and is represented in the grid as -1.

We drop one ball at the top of each column of the box. Each ball can get stuck in the box or fall out of the bottom. A ball gets stuck if it hits a "V" shaped pattern between two boards or if a board redirects the ball into either wall of the box.

Return an array answer of size n where answer[i] is the column that the ball falls out of at the bottom after dropping the ball from the ith column at the top, or -1 if the ball gets stuck in the box.

Solution

  • Runtime: O(mn)
  • Space: O(1)
1class Solution {
2public: 
3    vector<int> findBall(vector<vector<int>>& grid) {
4        vector<int> result;
5        for(int i=0; i<grid[0].size(); i++){
6            int row = 0, col = i;
7            
8            while(row<grid.size()){
9                // when the path is \x\ 
10                if(grid[row][col]== 1 && col+1 < grid[0].size() && grid[row][col+1] == 1)             {
11                    row++;
12                    col++;
13                } // when the path is /x/
14                else if(grid[row][col]==-1 && col-1 >= 0 && grid[row][col-1]==-1){
15                    row++;
16                    col--;
17                }
18                else{ // otherwise <-> |x/, \x|, \x/
19                    break;
20                }
21            }
22            
23            result.push_back(row==grid.size()?col:-1);
24        }
25        return result;
26    }
27};

14. Longest Common Prefix

Description

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Solution

  • Runtime: O(n)
  • Space: O(1)
1class Solution {
2public:
3    string longestCommonPrefix(vector<string>& strs) {
4        // gradually strip down the longestCommonPrefix
5        string longest = strs[0];
6        
7        for(int i=1; i<strs.size(); i++) {
8            // if the comparing string is shorter than the current "longest" string
9            if(strs[i].size()<longest.size()) {
10                longest = longest.substr(0,strs[i].size());
11            }
12            // compare each character in the comparing string, and cut if a char is different
13            for(int j=0; j<strs[i].size(); j++) {
14                if(longest[j]!=strs[i][j]){
15                    longest = longest.substr(0,j);
16                    break;
17                }
18            }
19        }
20        
21        return longest;
22    }
23};

43. Multiply Strings

Description

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Solution

  • Runtime: O(mn)
  • Space: O(m)
1class Solution {
2public:
3    string add(string num1, string num2) {
4        int carry = 0;
5        int ptr1 = 0;
6        int ptr2 = 0;
7        string result;
8        
9        while(ptr1<num1.size() && ptr2<num2.size()) {
10            int temp = num1[ptr1]-'0' + num2[ptr2]-'0'+carry;
11            if(temp >= 10 ){
12                carry = 1;
13                result+= to_string(temp%10);
14            }
15            else {
16                carry = 0;
17                result+= to_string(temp);
18            }
19            ptr1++;
20            ptr2++;
21        }
22        
23        while(ptr1<num1.size()) {
24            int temp = num1[ptr1]-'0'+carry;
25            if(temp >= 10 ){
26                carry = 1;
27                result+=to_string(temp%10);
28            }
29            else{
30                carry = 0;
31                result+= to_string(temp);
32            }
33            ptr1++;
34        }
35        
36        while(ptr2<num2.size()) {
37            int temp = num2[ptr2]-'0'+carry;
38            if(temp >= 10 ){
39                carry = 1;
40                result+=to_string(temp%10);
41            }
42            else{
43                carry = 0;
44                result+= to_string(temp);
45            }
46            ptr2++;
47        }
48        
49        
50        if(carry){
51            result+="1";
52        }
53        return result;
54    }
55    
56    string multiplyOneDigit(string &num, int digit) {
57        int carry =0;
58        string result;
59        
60        for(auto &c: num) {
61            int temp = (c-'0')*digit+carry;
62            if(temp>=10){
63                // update carry
64                carry = temp/10;
65                // append a digit
66                result += to_string(temp%10);
67            }
68            else{
69                carry = 0;
70                // append a digit
71                result += to_string(temp);
72            }
73        }
74        
75        if(carry > 0){
76            result+=to_string(carry);
77        }
78        
79        return result;
80    }
81    
82    string multiply(string num1, string num2) {
83        if(num1=="0"||num2=="0"){
84            return "0";
85        }
86        
87        reverse(num1.begin(), num1.end());
88        reverse(num2.begin(), num2.end());
89        
90        string result;
91        
92        for(int i=0; i<num2.size(); i++) {
93            result=add(result, string(i,'0')+multiplyOneDigit(num1, num2[i]-'0'));
94        }
95        
96        reverse(result.begin(), result.end());
97        return result;
98    }
99};

19. Remove Nth Node From End of List

Description

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Solution

It is trivial to come up an algorithm that takes 2 passes. The challenege is to remove the node in a single pass without counting the number of nodes in the list.

  • Runtime: O(n)
  • Space: O(1)
1class Solution {
2public:
3    ListNode* removeNthFromEnd(ListNode* head, int n) {
4        
5        ListNode* slow = head;
6        ListNode* fast = head;
7        // fastfoward n places
8        for(int i=0;i<n;i++){
9            fast = fast -> next;
10        }
11        // if input size of the linkedlist == n, that is remove the head itself
12        if (!fast) return head->next;
13        // when fast reaches the end of the list, slow should be just before the n-th last element
14        while(fast->next){
15            slow = slow -> next;
16            fast = fast -> next;
17        }
18        // skip the n-th las element
19        slow->next = slow->next->next;
20        return head;
21    }
22};

234. Palindrome Linked List

Description

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Solution

  • Runtime: O(n)
  • Space: O(1)
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 */
11/**
12 * Definition for singly-linked list.
13 * struct ListNode {
14 *     int val;
15 *     ListNode *next;
16 *     ListNode() : val(0), next(nullptr) {}
17 *     ListNode(int x) : val(x), next(nullptr) {}
18 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
19 * };
20 */
21class Solution {
22public:
23    bool isPalindrome(ListNode* head) {
24        ListNode *slow = head;
25        ListNode *fast = head;
26        
27        // get the middle node or the element just after the middle node
28        while(fast&&fast->next&&fast->next->next) {
29            fast = fast->next->next;
30            slow = slow->next;
31        }
32        
33        // reverse everything after middle point
34        ListNode *reversed = reverse(slow);
35        
36        // check if matches
37        while(reversed && head) {
38            if(reversed->val!=head->val){
39                return false;
40            }
41            reversed=reversed->next;
42            head=head->next;
43        }
44        return true;
45    }
46    
47    // reverse is O(n) and take no space
48    ListNode* reverse(ListNode* head)
49    {
50        ListNode *prev=nullptr, *curr=head, *next=nullptr;
51
52        while(curr)
53        {
54            next = curr->next;
55            curr->next = prev;
56
57            prev = curr;
58            curr = next;
59
60        }
61        
62        return prev;
63    }
64};

328. Odd Even Linked List

Description

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Solution

  • Runtime: O(n)
  • Space: O(1)
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* oddEvenList(ListNode* head) {
14        if(head){
15            ListNode *odd = head;
16            ListNode *even = head->next;
17            ListNode *evenHead = even;  
18            
19            // the major question is when to stop
20            // odd number of nodes => only 1 node left
21            // even number of nodes => when there are two node left
22            while(even && even->next) {
23                // remove the next connection for the even element
24                odd->next = odd->next->next;
25                odd = odd->next;
26                // remove the next connection for the odd element
27                even->next = even->next->next;
28                even = even->next;
29            }
30            odd->next = evenHead;
31        }    
32    
33                
34        return head;
35    }
36};