1. Array and Strings (Q4 unfinished)

1. 3Sum

https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/776/

test all paths (time limit exceeded):

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        if(n <= 2)
            return {};
        vector<vector<int>> result;
        vector<int> curr = {};
        threeSum(nums, result, curr, 0);
        for(int i = 0; i < result.size(); i++){
            sort(result[i].begin(), result[i].end());
        }
        sort(result.begin(), result.end());
        result.erase(unique(result.begin(), result.end()), result.end());
        return result;
    }
private:
    void threeSum(vector<int>& nums, vector<vector<int>>& result, vector<int>& curr, int index){
        if(curr.size() == 3){
            if(curr[0] + curr[1] + curr[2] == 0){
                result.push_back(curr);
            }
            return;
        }
        for(int i = index; i < (nums.size() - (2 - curr.size())); i++){
            curr.push_back(nums[i]);
            threeSum(nums, result, curr, (i + 1));
            curr.pop_back();
        }
    }
};

2 pointers:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        if(n <= 2) //if length <= 2, cannot get 3 numbers
            return {};
        vector<vector<int>> result;
        sort(nums.begin(), nums.end()); //sort in ascending order
        int l;
        int r;
        for(int i = 0; i < n - 2; i++){ //use 3 indexes, i l r, the rightest i is the 3rd last one
            if(nums[i] > 0) //if nums[i] > 0, it means nums[l] > 0 and nums[r] > 0
                break;
            if (i > 0 && nums[i] == nums[i - 1]) //skip duplicates
                continue;
            l = i + 1;
            r = n - 1;
            while (l < r) {
                if (nums[i] + nums[l] + nums[r] == 0) {
                    result.push_back({nums[i], nums[l], nums[r]});
                    l++;
                    r--;
                    while (l < r && nums[l] == nums[l - 1]) //skip duplicates
                        l++;
                    while (l < r && nums[r] == nums[r + 1]) //skip duplicates
                        r--;
                } else if (nums[i] + nums[l] + nums[r] < 0) { // adjust l 
                  l++;
                } else { // adjust r
                  r--;
                }
            }
        }
        return result;
    }
};

2. Set Matrix Zeroes

https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/777/

use the first row/col as an indicator:

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        const int m = matrix.size();
        const int n = matrix[0].size();
        bool frow_set_0 = false; 
        bool fcol_set_0 = false;
        for(int r = 0; r < m; r++){ //dicide to set the first row into 0 
            if(matrix[r][0]==0){
                fcol_set_0 = true;
                break;
            }
        }
        for(int c = 0; c < n; c++){ //dicide to set the first column into 0 
            if(matrix[0][c]==0){
                frow_set_0 = true;
                break;
            }
        }
        for(int r = 0; r < m; r++){
            for(int c = 0; c < n; c++){
                if(matrix[r][c]==0){ //use corresponding grids in the first row/col as indicators
                    matrix[r][0] = 0;
                    matrix[0][c] = 0;
                }
            }
        }
        for(int r = 1; r < m; r++){ //set rows
            if(matrix[r][0]==0){
                for(int c = 1; c < n; c++){
                    matrix[r][c] = 0;
                }
            } 
        }
        for(int c = 1; c < n; c++){ //set columns
            if(matrix[0][c]==0){
                for(int r = 1; r < m; r++){
                    matrix[r][c] = 0;
                }
            } 
        }
        if(frow_set_0){ //set the first row
            for(int c = 0; c < n; c++){
                matrix[0][c] = 0;
            }
        }
        if(fcol_set_0){ //set the first column
            for(int r = 0; r < m; r++){
                matrix[r][0] = 0;
            }
        }
    }
};

3. Group Anagrams

https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/778/

copy the vector and organize:

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> result;
        if(strs.size()==1){ //if only one category
            result.push_back(strs);
            return result;
        }
        int n = strs.size();
        vector<string> copy = strs; //a copy of strings
        vector<int> reserved (n, 0); //a boolean indicator
        int left = n;
        for(int i = 0; i < n; i++){ //sort copy array elements in ascending orders
            sort(copy[i].begin(), copy[i].end());
        }
        vector<string> curr;
        while(left > 0){
            for(int i = 0; i < n; i++){
                if(reserved[i]==0){ //if it's not used, use the current one as a standard
                    curr.push_back(strs[i]); 
                    reserved[i] = 1; 
                    left--;
                    for(int j = i + 1; j < n; j++){ 
                        if(reserved[j]==0 && copy[i] == copy[j]){ //compare with organized copy vector
                            curr.push_back(strs[j]); //push all anagrams in original vector
                            reserved[j] = 1; //show that this place is used
                            left--;
                        }
                    }
                    result.push_back(curr);
                    curr.clear();
                }
            }
        }
        return result;
    }
};

4. Longest Substring Without Repeating Characters

https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/779/

5. Longest Palindromic Substring

https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/780/

filter with sliding window and sub function:

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        if(n <= 1) //extreme cases
            return s;
        for(int len = n; len > 0; len--){ //length of the possible longest palindrome
            for(int i = 0; i <= n - len; i++){ //left index of that palindrome
                if(s[i] == s[i + len - 1]){
                    if(isPalindrome(s.substr(i, len)))
                        return s.substr(i, len);
                }
            }
        }
        return "";
    }
private:
    bool isPalindrome(string s){ //boolean to show is this substring a palindromic substring
        int l = 0;
        int r = s.length() - 1;
        while(l < r){
            if(s[l] != s[r])
                return false;
            l++;
            r--;
        }
        return true;
    }
};

6. Increasing Triplet Subsequence

https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/781/

2 pointers and sub function:

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        if(n < 3) //unable to form a base case
            return false;
        for(int l = 0; l < n - 2; l++){
            for(int r = n - 1; r > l + 1; r--){
                if(nums[r] - nums[l] > 1){ //if get 2 possible pointers and they are not neighbors
                    if(includeIncreasingTriplet(nums, l, r)){ //use sub function
                        return true;
                    }
                }
            } 
        }
        return false;
    }
private:
    bool includeIncreasingTriplet(vector<int>& nums, int l, int r) { //is there an increasing triplet
        int l_val = nums[l];
        int r_val = nums[r];
        for(int i = l + 1; i < r; i++){
            if(l_val < nums[i] && nums[i] < r_val){
                return true;
            }
        }
        return false;
    }
};

7. Missing Ranges

https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/782/

introduce boundaries as part of the list

class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        vector<string> result;
        //add boundaries into the list
        nums.push_back(lower-1);
        nums.push_back(upper+1);
        sort(nums.begin(), nums.end()); 
        string curr = "";
        for(int i = 0; i < nums.size() - 1; i++){
            curr = aRange(nums[i], nums[i+1]); 
            if(curr.length() > 0) //push possible missing ranges
                result.push_back(curr);
        }
        return result;
    }
private:
    string aRange(int a, int b){
        if(b-a <= 1) //if no missing values
            return "";
        else if(b-a == 2) //if one missing value
            return to_string(a + 1);
        return to_string(a + 1) + "->" + to_string(b - 1); //if over 2 missing values
    }
};