1. Array (Q6 unfinished)

1. Remove Duplicates from Sorted Array

https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/727/

STL erase() method:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty())
            return 0;
        else if(nums.size()==1)
            return 1;
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        return nums.size();
    }
};

go over method:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int bypass = 0;
        int n = nums.size();
        for(int i = 1; i < n; i++){
            if(nums[i] == nums[i-1]) 
                bypass++;
            else 
                nums[i-bypass] = nums[i];
        }
        return n-bypass;
    }
};

2. Remove Duplicates from Sorted Array

https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/564/

binary tree method(TLE):

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        profit = buyOrSell(prices, 0, 0, 0);
        return profit;
    }
private:
    int buyOrSell(vector<int>& prices, int curr, int stock, int profit){
        if(curr == prices.size())
            return profit;
        int r1, r2;
        if(stock == 1){
            r1 = buyOrSell(prices, curr+1, 0, profit + prices[curr]); //sell
            r2 = buyOrSell(prices, curr+1, 1, profit);                //not sell
        } else if(stock==0) {
            r1 = buyOrSell(prices, curr+1, 1, profit - prices[curr]); //buy
            r2 = buyOrSell(prices, curr+1, 0, profit);                //not buy
        }
        return max(r1, r2);
    }
};

max():

idea: https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/564/discuss/39420/Three-lines-in-C++-with-explanation

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int result = 0;
        for (int i = 1; i < prices.size(); i++) 
            result += max(prices[i] - prices[i - 1], 0);    
        return result;
    }
};

3. Rotate Array

https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/646/

add and delete method:

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if(k==0) return;
        int tail = nums[nums.size() - 1];
        nums.insert(nums.begin(), tail);
        nums.erase(nums.begin() + nums.size() - 1);
        rotate(nums, k - 1);
    }
};

STL rotate() method:

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if(k > nums.size())
            k = k % n;
        std::rotate(nums.begin(), nums.begin() + (n - k), nums.end());
    }
};

4. Contains Duplicate

https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/578/

sort and remove duplicate method:

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int full_len = nums.size();
        int shorten_len;
        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        shorten_len = nums.size();
        return !(full_len == shorten_len);
    }
};

sort and compare neighbours:

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] == nums[i-1]){
                return true;
            }
        }
        return false;
    }
};

5. Single Number

https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/549/

hashmap method:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> map;
        for(int i = 0; i < nums.size(); i++){
            map[nums[i]]++;
        }
        for(unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++){
            if(it->second == 1)
                return it->first;
        }
        return 0;
    }
};

jump 2 method:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end()); //sorting
        for(int i = 0; i < nums.size() - 1; i+=2){ //2 jumps 1 time
            if(nums[i] != nums[i+1]){ //if a pair is not the same number, the number of purpose is inside
                if((i > 0 && nums[i] != nums[i-1]) || (i == 0)){
                    return nums[i];
                }
                if(nums[i+1] != nums[i+2]){
                    return nums[i+1];
                }
            }
        }
        return nums[nums.size()-1];
    }
};

6. Intersection of Two Arrays II

https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/674/

7. Plus One

https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/559/

carry method:

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int i = digits.size() - 1;

        int carry = 0;

        while(i >= 0){
            if(digits[i] + 1 == 10){
                digits[i] = 0;
                carry = 1;
                i--;
            } else {
                digits[i]++;
                break;
            }
        }

        if(i < 0 && carry == 1){
            digits.insert(digits.begin(), 1);
        }

        return digits;
    }
};

8. Move Zeroes

https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/567/

re-assignment method:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int nonZero = 0;

        for(int i = 0; i < nums.size(); i++){
            if(nums[i] != 0){
                nums[nonZero] = nums[i];
                nonZero++;
            }
        }

        for(; nonZero < nums.size(); nonZero++){
            nums[nonZero] = 0;
        }
    }
};

9. Two Sum

https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/546/

hashmap and find() method:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashmap;

        int n = nums.size();

        for(int i = 0; i < n; i++)
            hashmap[nums[i]] = i;

        for(int i = 0; i < n; i++){
            unordered_map<int, int>::iterator got = hashmap.find(target-nums[i]);

            if(got !=hashmap.end() && got->second != i)
                return {i, got->second};
        }

        return {};
    }
};

10. Valid Sudoku

https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/769/

go over all numbers to check availability based on sudoku rules:

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {

        int sub_r, sub_c;

        for(int r = 0; r < 9; r++){
            for(int c = 0; c < 9; c++){
                //if has numbers
                if(isdigit(board[r][c])){
                    //for rows
                    for(int r_o = 0; r_o < 9; r_o++){
                        if(board[r_o][c] == board[r][c] && r_o != r){
                            return false;
                        }
                    }

                    //for columns
                    for(int c_o = 0; c_o < 9; c_o++){
                        if(board[r][c_o] == board[r][c] && c_o != c){
                            return false;
                        }
                    }

                    //for 3*3 grids
                    if(r <= 2){
                        sub_r = 0;
                    } else if(r >= 3 && r <= 5){
                        sub_r = 1;
                    } else {
                        sub_r = 2;
                    }

                    if(c <= 2){
                        sub_c = 0;
                    } else if(c >= 3 && c <= 5){
                        sub_c = 1;
                    } else {
                        sub_c = 2;
                    }

                    for(int r_s = 3*sub_r; r_s < 3*(sub_r + 1); r_s++){
                        for(int c_s = 3*sub_c; c_s < 3*(sub_c + 1); c_s++){
                            if(board[r_s][c_s] == board[r][c] && !(r_s == r && c_s == c)){
                                return false;
                            }
                        }
                    }
                }
            }
        }

        return true;
    }

};

11. Rotate Image

https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/770/

reverse row sequence and swap diagonally:

class Solution {
public:
    /*
     * clockwise rotate
     * first reverse up to down, then swap the symmetry 
     * 1 2 3     7 8 9     7 4 1
     * 4 5 6  => 4 5 6  => 8 5 2
     * 7 8 9     1 2 3     9 6 3
    */
    void rotate(vector<vector<int>> &matrix) {
        reverse(matrix.begin(), matrix.end());

        for (int i = 0; i < matrix.size(); i++) {
            for (int j = i + 1; j < matrix[i].size(); j++)
                swap(matrix[i][j], matrix[j][i]);
        }
    }
};