Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Solution:
class Solution {
public:
    int partition(vector<int>& nums, int st, int end) {
        int pivot = nums[end];
        int i = st, iter = st;
        while (i < end) {
            if (nums[i] <= pivot) {
                iter_swap(nums.begin() + i, nums.begin() + iter);
                iter++;
            }
            i++;
        }
        iter_swap(nums.begin() + end, nums.begin() + iter);
        return iter;
    }
   
    int quickPK(vector<int>& nums, int st, int end, int k) {
        int p = partition(nums, st, end);
       
        if (p == k) {
            return nums[p];
        } else if (p > k) {
            return quickPK(nums, st, p - 1, k);
        } else {
            return quickPK(nums, p+1, end, k);
        }
    }
   
    int findKthLargest(vector<int>& nums, int k) {
        int size = nums.size();
        int end = nums.size() - 1, start = 0;
        return quickPK(nums, start, end, size - k);
    }
};

Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

class TrieNode {
    public:
    vector<TrieNode *> child;
    bool isWord;
    TrieNode(): isWord(false) {
        for (int i = 0; i < 26; i++) {
            child.push_back(NULL);
        }
    }
};

class Trie {
    TrieNode *root;
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode();
    }
 
    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode *trav = root;
        int size = word.size();
        for (int i = 0; i < size; i++) {
            char ch = word[i];
            if (trav -> child[ch - 'a'] == NULL) {
                trav -> child[ch - 'a'] = new TrieNode();
            }
            trav = trav -> child[ch - 'a'];
        }
        trav -> isWord = true;
    }
 
    /** Returns if the word is in the trie. */
    bool search(string word) {
        TrieNode *trav = root;
        for (int i = 0; i < word.size(); i++) {
            char ch = word[i];
            if (trav -> child[ch - 'a'] == NULL) {
                return false;
            } else {
                trav = trav -> child[ch - 'a'];
            }
        }
        return trav->isWord;
    }
 
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string word) {
        TrieNode *trav = root;
 
        for (int i = 0; i < word.size(); i++) {
            char ch = word[i];
            if (trav -> child[ch - 'a'] == NULL) {
                return false;
            } else {
                trav = trav -> child[ch - 'a'];
            }
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * bool param_2 = obj.search(word);
 * bool param_3 = obj.startsWith(prefix);
 */


=========== Another attempt ======
class TrieNode {
public:
    TrieNode() {
        for (int i = 0; i < 26; i++) {
            child[i] = NULL;
        }
        is_word = false;
    }
    TrieNode* child[26];
    bool is_word;
};

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode();
    }
   
    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode *trav = root;
        // Assume word is non empty.
        for (int i = 0; i < word.size(); i++) {
            char ch = word[i];
            if (trav -> child[ch - 'a'] == NULL) {
                trav -> child[ch - 'a'] = new TrieNode();
            }
            trav = trav -> child[ch - 'a'];
        }
        trav -> is_word = true;
    }
   
    /** Returns if the word is in the trie. */
    bool search(string word) {
        TrieNode *trav = root;
        for (int i = 0; i < word.size(); i++) {
            char ch = word[i];
            if (trav -> child[ch - 'a'] == NULL) {
                return false;
            }
            trav = trav -> child[ch - 'a'];
        }
        return trav -> is_word;
    }
   
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        TrieNode *trav = root;
        for (int i = 0; i < prefix.size(); i++) {
            char ch = prefix[i];
            if (trav -> child[ch - 'a'] == NULL) {
                return false;
            }
            trav = trav -> child[ch - 'a'];
        }
        return true;
    }
private:
    TrieNode* root;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count 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.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

Solution:

class Solution {
public:
    bool dfs(vector<vector<char>>& grid, int i, int j,
             vector<vector<bool>>& visited, int& ans) {
        if (i < 0 || i >= grid.size() ||
            j < 0 || j >= grid[0].size() ||
            visited[i][j] || grid[i][j] == '0') {
           return false;
        }
        visited[i][j] = true;
        dfs(grid, i, j + 1, visited, ans);
        dfs(grid, i, j - 1, visited, ans);
        dfs(grid, i + 1, j, visited, ans);
        dfs(grid, i - 1, j, visited, ans);
        return true;
       
    }
    int numIslands(vector<vector<char>>& grid) {
        int ans = 1;
        int row = grid.size();
        if (row == 0) {
            return 0;
        }
        int col = grid[0].size();
        vector<vector<bool> > visited(grid.size(), vector<bool>(grid[0].size(), false));
       
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (dfs(grid, i, j, visited, ans)) {
                    ans++;
                }
            }
        }
        return ans - 1;
    }
};

======== No need of visited information =====

void dfs(vector<vector<char>> &grid, int x, int y) {
 4         if (x < 0 || x >= grid.size()) return;
 5         if (y < 0 || y >= grid[0].size()) return;
 6         if (grid[x][y] != '1') return;
 7         grid[x][y] = 'X';
 8         dfs(grid, x + 1, y);
 9         dfs(grid, x - 1, y);
10         dfs(grid, x, y + 1);
11         dfs(grid, x, y - 1);
12     }
13     
14     int numIslands(vector<vector<char>> &grid) {
15         if (grid.empty() || grid[0].empty()) return 0;
16         int N = grid.size(), M = grid[0].size();
17         int cnt = 0;
18         for (int i = 0; i < N; ++i) {
19             for (int j = 0; j < M; ++j) {
20                 if (grid[i][j] == '1') {
21                     dfs(grid, i, j);
22                     ++cnt;
23                 }
24             }
25         }
26         return cnt;
27     }

Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
private:
    stack<TreeNode *> st;
   
public:
    BSTIterator(TreeNode *root) {
        while (root != NULL) {
            st.push(root);
            root = root -> left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !st.empty();
    }

    /** @return the next smallest number */
    int next() {
        int val;
        if (!st.empty())  {
            TreeNode * trav = st.top();
            val = trav -> val;
            st.pop();
            if (trav -> right) {
                TreeNode *tmp = trav -> right;
                while (tmp != NULL) {
                    st.push(tmp);
                    tmp = tmp -> left;
                }
            }
        }
        return val;
    }
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Solution:

class Solution {
public:
    // Recursive.
    bool recursive_wordBreakhelper(string s, int index, vector<string>& wordDict) {
        int size = s.size();
        bool ans;
        if (index == size) {
            return true;
        }
        for (int i = 0; i + index - 1 < size; i++) {
            string sub = s.substr(index, i);
            vector<string>::iterator it =
                find(wordDict.begin(), wordDict.end(), sub);
            if (it != wordDict.end()) {
                ans = recursive_wordBreakhelper(s, index + i, wordDict);
                if (ans) {
                    return true;
                }
            }
        }
        return false;
    }
 
    // Dynamic.
    bool wordBreakhelper(string s, vector<string>& wordDict) {
        vector<bool> ans(s.size() + 1, false);
        ans[0] = true;
        for (int i = 0; i < s.size(); i++) {
            for (int j = i; j >= 0; j--) {
                string sub = s.substr(j, i - j + 1);
                vector<string>::iterator it =
                        find(wordDict.begin(), wordDict.end(), sub);
                if (ans[j] && it != wordDict.end()) {
                    ans[i + 1] = true;
                }
            }
        }
        return ans[s.size()]; // since s is non-empty.
    }
 
    bool wordBreak(string s, vector<string>& wordDict) {
        return wordBreakhelper(s, wordDict);
    }
};

========== Another attempt  (DP) ========
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> st(wordDict.begin(), wordDict.end());
        int size = s.size();
        vector<bool> dp(size + 1, false);
        dp[0] = true;
     
        for (int i = 0; i < size; i++) {
            for (int j = i; j >= 0; j--) {
                string sbstr = s.substr(j, i - j + 1);
                if (st.count(sbstr) && dp[j]) {
                    dp[i+1] = true;
                }
            }
        }
        return dp[size];
    }
};

======== Another attempt (recursive with memorization) ====
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> st(wordDict.begin(), wordDict.end());
        unordered_map<string, bool> mp;
        return helper(s, 0, st, mp);
    }
   
    bool helper(string s, int idx, unordered_set<string>& st, unordered_map<string, bool>& mp){
        if (idx == s.size()) {
            return true;
        }
       
        string str = s.substr(idx);
        if (mp.count(str)) {
            return mp[str];
        }
       
        for (int i = idx; i < s.size(); i++) {
            string sb_str = s.substr(idx, i - idx + 1);
            if (st.count(sb_str)) {
                string str_remain = s.substr(i + 1);
                bool ans_exist = helper(s, i + 1, st, mp);
                mp[str_remain] = ans_exist;
                if (ans_exist) {
                    return true;
                }
            }
        }
        return false;
    }
};

Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int count = 1;
        int ans = 0, size = nums.size();
        if (size == 0 || size == 1) {
            return size;
        }
     
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums[i] != nums[i + 1]) {
                nums[ans++] = nums[i];
                count = 1;
            } else {
                count++;
                if (count == 2) {
                    nums[ans++] = nums[i];
                }
            }
        }
        nums[ans] = nums[size - 1];
        return ans + 1;
    }
};

============= Another attempt ==========
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int size = 0, iter = 1, count = 1;
       
        if (nums.size() == 0) {
            return size;
        }
       
        while (iter < nums.size()) {
            if (nums[iter] == nums[size]) {
                count++;
                if (count == 2) {
                    nums[size + 1] = nums[iter];
                    size++;
                }
            } else {
                count = 1;
                nums[size + 1] = nums[iter];
                size++;
            }
            iter++;
        }
        nums.resize(size + 1);
        return size + 1;
    }
};

============= Optimized ==============
class Solution { public: int removeDuplicates(vector<int>& nums) { if(nums.size()<3) return nums.size(); int index=2; for(int i=2;i<nums.size();i++){ if(nums[i]!=nums[index-2]) nums[index++] = nums[i]; } return index; } };

Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

class Solution {
public:
    bool dfs(vector<vector<char>>& board, vector<vector<bool>>& visited,
             int i, int j, string word, int start) {          
        if (start == word.size()) {
            return true;
        }    
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() ||
            visited[i][j] || board[i][j] != word[start]) {
            return false;
        }
     
        visited[i][j] = true;
        bool ans = dfs(board, visited, i + 1, j, word, start + 1) ||
                   dfs(board, visited, i, j + 1, word, start + 1) ||
                   dfs(board, visited, i, j - 1, word, start + 1) ||
                   dfs(board, visited, i - 1, j, word, start + 1);
        if (ans == true) {
            return ans;
        }
        visited[i][j] = false;
        return false;
     
    }
 
    bool exist(vector<vector<char>>& board, string word) {
        bool ans = false;
        if (word.empty()) {
            return ans;
        }
        int row = board.size();
        int col = (board.size() != 0 ? board[0].size() : 0);
     
        vector<vector<bool>> visited(row, vector<bool>(col, false));
     
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                ans = dfs(board, visited, i, j, word, 0);
                if (ans) {
                    return true;
                }
            }
        }
        return false;
    }
};



=============== Faster if don't used visited matrix, instead use the same board =========
char letter = board[ y ][ x ]; board[ y ][ x ] = '*'; bool success = DFS( board, y, x + 1, word, index + 1 ) || DFS( board, y, x - 1, word, index + 1 ) || DFS( board, y + 1, x, word, index + 1 ) || DFS( board, y - 1, x, word, index + 1 ); board[ y ][ x ] = letter;

Simplify Path

Solution:

Problem:

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"




class Solution {
public:
 
    void split(string str, vector<string>& folders, char dil) {
        stringstream ss(str);
        string split_str;
        while (getline(ss, split_str, dil)) {
            folders.push_back(split_str);
        }
        return;
    }
    string simplifyPath(string path) {
        stack<string> st;
     
        vector<string> folders;
        split(path, folders, '/');
     
        for (int i = 0; i < folders.size(); i++) {
            if (folders[i] == "..") {
                if(!st.empty()) {
                    st.pop();
                }
            } else if (folders[i] != "." && folders[i] != "") {
                st.push(folders[i]);
            }
        }
        string ans;
        while (!st.empty()) {
            ans = "/" + st.top() + ans;
            st.pop();
        }
        return (ans.empty() ? "/": ans);
    }
};


============= Updated ========
class Solution {
public:
    vector<string> split(string str, char delim) {
        vector<string> ans;
        stringstream ss(str);
        string token;
        while(getline(ss, token, delim)) {
            ans.push_back(token);
        }
        return ans;
    }
   
    string form_ans(stack<string> st) {
        string ans;
       
        while (!st.empty()) {
            ans = st.top() + ans;
            ans = "/" + ans;
            st.pop();
        }
        if (ans == "") {
            return "/";
        }
        return ans;
       
    }
   
    string simplifyPath(string path) {
        stack<string> st;
        vector<string> strs = split(path, '/');
       
        for (int i = 0; i < strs.size(); i++) {
            if (strs[i] != ".." && strs[i] != "." && strs[i] != "") {
                st.push(strs[i]);
            } else if (strs[i] == "..") {
                if (!st.empty()) {
                    st.pop();
                }
            }
        }
        string ans = form_ans(st);
        return ans;
    }
};

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

class Solution {
public:
    void LC(string digits, map<char, string> mp, vector<string>& sol) {
        for (int i = 0; i < digits.size(); i++) {
            string letter = mp[digits[i]];
            int sol_size = sol.size();
            vector<string> tmp;
            for (int k = 0; k < sol_size; k++) {
                for (int j = 0; j < letter.size(); j++) {
                    tmp.push_back(sol[k] + string(1, letter[j]));
                }
            }
            sol = tmp;
            tmp.clear();
        }
        return;
    }
 
    vector<string> letterCombinations(string digits) {
        vector<string> sol;
     
        if (digits.empty()) {
            return sol;
        }
        sol.push_back("");
     
        map<char,string> mp;
        mp['1'] = "";mp['0'] = "";
        mp['2'] = "abc";mp['3'] = "def";mp['4'] = "ghi";mp['5'] = "jkl";
        mp['6'] = "mno";mp['7'] = "pqrs";mp['8'] = "tuv";mp['9'] = "wxyz";
     
        LC(digits, mp, sol);
        return sol;
    }
};




==== online backtracking =====

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> lettComb;
        string dict[] = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        string comb(digits.size(),'\0');
        findLettComb(digits, 0, dict, comb, lettComb);
        return lettComb;
    }
    
    void findLettComb(string &digits, int index, string dict[], string &comb, vector<string> &lettComb) {
        if(index==digits.size()) {
            lettComb.push_back(comb);
            return;
        }
        
        string lett= dict[digits[index] - '0'];
        for(int i=0; i<lett.size(); i++) {
            comb[index] = lett[i];
            findLettComb(digits, index+1, dict, comb, lettComb);
        }
    }
};

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution:

class Solution {
public:
    void process_vector(vector<int>& tmp, vector<pair<int, int> >& nums) {
        for (int i = 0; i < tmp.size(); i++) {
            nums.push_back(make_pair(tmp[i], i));
        }
    }
   
    static bool comp(pair<int, int> first, pair<int, int> second) {
        return first.first < second.first;
    }
   
    vector<int> twoSum(vector<int>& tmp, int target) {
        vector<int> sol;
        vector<pair<int, int> > nums;
        process_vector(tmp, nums);
        sort(nums.begin(), nums.end(), comp);
        if (nums.size() == 0) {
            return sol;
        }
       
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int temp_sum = nums[left].first + nums[right].first;
            if (temp_sum == target) {
                sol.push_back(nums[left].second);
                sol.push_back(nums[right].second);
                return sol;
            } else if (temp_sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return sol;
    }
};

Diameter of Binary Tree

Given a binary tree, you need to compute 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.

Example:
Given a binary tree 

          1
         / \
        2   3
       / \     
      4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

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

Solution:

/**
 * 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:
    int diameterOfBinaryTree(TreeNode* root) {
        int dia = 0, height = 0;
        height = helper(root, dia);
        // Get edges from number of nodes.
        return dia > 1 ? dia  - 1: 0;
    }
   
    int helper(TreeNode *root, int& dia) {
        if (root == NULL) {
            return 0;
        }
        int left_height = 0, right_height = 0, left_dia = 0, right_dia = 0;
       
        left_height = helper(root -> left, left_dia);
        right_height = helper(root -> right, right_dia);
       
        dia = max(left_height + right_height + 1, max(left_dia, right_dia));
        return max(left_height, right_height) + 1;
    }
};