leetcode Question: Kth Smallest Element in a BST

Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Analysis:


Remind the concept of BST (see here), a tree traversal will solve this problem.
The idea is to keep an array of length K, to hold the k smallest nodes. Each time when visiting a node, save it to the array if the array is not full. The end (or front depending on your save order) element is the Kth smallest node.

If insert and delete operations often happen, we can only check this array of length K, if any node in this array is deleted, search and insert the next element from the array's last node. If new node is inserted as the child of one node in the array, insert this node to its proper position of array, and move every other accordingly.


Code(C++):

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void search(TreeNode* root, int &k, vector<TreeNode*> &list_k){
        if (root->left){ search(root->left, k, list_k);}
        k = k-1;
        if (k>=0){
            list_k[k] = root;
        }else{
            return;
        }
        if (root->right){search(root->right, k, list_k);}
    }
    int kthSmallest(TreeNode* root, int k) {
        vector<TreeNode*> list_k(k,NULL);
        search(root,k, list_k);
        return list_k[0]->val;
    }
};

Code(Python):

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def search(self, root, k, list_k):
        if root.left:
            self.search(root.left, k, list_k)
        k[0] = k[0] -1
        if k[0] >= 0:
            list_k.append(root)
        else:
            return
        if root.right:
            self.search(root.right, k, list_k)
    
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        list_k = []
        self.search(root, [k], list_k)
        return list_k[-1].val

leetcode Question: Majority Element II

Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Analysis:


This problem can be solved using the  Boyer-Moore majority vote algorithm.

Before we are digging into this algorithm, let's see one basic observation:
How many majority elements at most in this problem?
Answer: Two.  
Explanation: At most there are 3 elements appear exactly n/3 times. So for more than n/3 times, at most there are 2 elements.

Now we discuss the Moore majority vote algorithm. Quoted from wiki:
"
The algorithm is carried out in two steps:

1. Eliminate all elements except one.

Iterating through the array of numbers, maintain a current candidate and a counter initialized to 0. With the current element x in iteration, update the counter and (possibly) the candidate:

If the counter is 0, set the current candidate to x and the counter to 1. If the counter is not 0, increment or decrement the counter based on whether x is the current candidate.

2. Determine if the remaining element is a valid majority element.

With the candidate acquired in step 1, iterate through the array of numbers and count its occurrences. Determine if the result is more than half of the sequence's length. If so, the candidate is the majority. Otherwise, the sequence doesn't contain a majority.

"

The key idea of this algorithm is "decrement" of the counter when new elements are different from all the current candidates.  This "decrement" operation is to cancel out the elements that do not appear most times in the array. Therefore, after one scan, the candidates are the elements which appear most of the times. The last  step is to check if these candidates are satisfied with the condition of more than n/3 times.




Code (C++):

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> res;
        int a,b;
        int ca = 0;
        int cb = 0;
        
        for (int i=0;i<nums.size();i++){
            if (nums[i] == a || ca == 0){
                a = nums[i];
                ca += 1;
            }else if(nums[i] == b  || cb == 0){
                b = nums[i];
                cb += 1;
            }else{
                ca --;
                cb --;
            }
        }
        
        ca = 0;
        cb = 0;
        for (int i=0;i<nums.size();i++){
            if (nums[i] == a){ ++ca; }
            else if (nums[i] == b){ ++cb; }
        }
        
        if (ca > floor(nums.size()/3) ){ res.push_back(a);}
        if (cb > floor(nums.size()/3)){ res.push_back(b);}
        
        return res;
    }
};

Code (Python):

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = []
        a = 0
        b = 0
        ca = 0
        cb = 0
        
        for num in nums:
            if num == a or ca == 0:
                a = num
                ca += 1
            elif num == b or cb == 0:
                b = num
                cb += 1
            else:
                ca -= 1
                cb -= 1
        
        ca = 0
        cb = 0
        for num in nums:
            if num == a:
                ca += 1
            elif num == b:
                cb += 1
        if ca > math.floor(len(nums)/3):
            res.append(a)
        if cb > math.floor(len(nums)/3):
            res.append(b)
        
        return res