# Arrays 101

###### tags: `LeetCode筆記`

## :memo: Merge Sorted Array (Easy)

### 作法 Two pointers <-,<-
nums1的長度是m+n
利用兩個變數去分別記錄兩個array現在"從尾部"掃到哪裡，誰大就存誰到nums1裡面(k)
**程式碼最後不用檢查while(i>=0)因為數值都是放在num1這個陣列**
**時間: O(N)**
**空間: O(1)**

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = nums1.size() - 1;
        
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
};

## :memo: Sort Array By Parity (Easy)
偶數數字要在奇數數字前，偶數奇數數字堆順序不計

### 作法 Two pointers -><-
頭尾比較互換，頭找到奇，尾找到偶互換
**時間: O(N)**
**空間: O(1)** **best**

class Solution {
    vector<int> sortArrayByParity(vector<int>& nums) {
        int i = 0; 
        int j = nums.size() - 1;
        
        while (i < j) {
            if (nums[i] % 2 > nums[j] % 2) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }

            if (nums[i] % 2 == 0) i++;
            if (nums[j] % 2 == 1) j--;
        }

        return nums;
    }
}

## :memo: Squares of a Sorted Array (Easy)

### 作法 Two pointers -><-
**時間: O(N)**
**空間: O(N)**

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);

        int left = 0;
        int right = n - 1;

        for (int i = n - 1; i >= 0; i--) {
            int square;
            if (abs(nums[left]) < abs(nums[right])) {
                square = nums[right];
                right--;
            } else {
                square = nums[left];
                left++;
            }
            result[i] = square * square;
        }
        
        return result;
    }
};

## :memo: Remove Element (Easy)

### 作法 Two pointers ->->

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0;
        int k = 0;
        
        for (i = 0; i < nums.size(); i++) {
            if (nums[i] != val) {    // 不能跟"val"一樣
                nums[k] = nums[i];
                k++;
            }
        }
        
        return k;
    }
};

## :memo: Remove Duplicates from Sorted Array (Easy)

### 作法 Two pointers ->->

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int insertIndex = 1;
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i - 1] != nums[i]) {    //不能跟"前一項"一樣
                nums[insertIndex++] = nums[i];
            }
        }
        
        return insertIndex;
    }
};

## :memo: Third Maximum Number (Easy)
https://leetcode.com/problems/third-maximum-number/solutions/2614958/official-solution/
Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.

### 作法 Min Heap
用一個大小裝三個的min heap去追蹤前三大，top會代表第三大的元素，第一第二不一定
當有比top還大就push掉舊top，insert新的，直到掃過所有元素，這個方法比Max-Heap還要節省空間
**時間: O(N)**
**空間: O(1)**

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        priority_queue<int, vector<int>, greater<int>> minHeap;
        unordered_set<int> taken;
        
        for (int index = 0; index < nums.size(); ++index) {
            // If current number was already taken, skip it.
            if (taken.count(nums[index])) {
                continue;
            }
            
            // If min heap already has three numbers in it.
            // Pop the smallest if current number is bigger than it.
            if (minHeap.size() == 3) {
                if (minHeap.top() < nums[index]) {
                    taken.erase(minHeap.top());
                    minHeap.pop();
                    
                    minHeap.push(nums[index]);
                    taken.insert(nums[index]);
                }
            } 
            // If min heap does not have three number we can push it.
            else {
                minHeap.push(nums[index]);
                taken.insert(nums[index]);
            }
        }
        
        // 'nums' has only one distinct element it will be the maximum.
        if (minHeap.size() == 1) {
            return minHeap.top();
        }
        // 'nums' has two distinct elements.
        else if (minHeap.size() == 2) {
            // int firstNum = minHeap.top();
            // minHeap.pop();
            // return max(firstNum, minHeap.top());
            minHeap.pop();
            return minHeap.top();
        }
        
        return minHeap.top();
    }
};

### 作法 Sorted set

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        // Sorted set to keep elements in sorted order.
        set<int> sortedNums;
        
        // Iterate on all elements of 'nums' array.
        for (int& num : nums) {
            // Do not insert same element again.
            if (sortedNums.count(num)) {
                continue;
            }
            
            // If sorted set has 3 elements.
            if (sortedNums.size() == 3) {
                // And the smallest element is smaller than current element.
                if (*sortedNums.begin() < num) {
                    // Then remove the smallest element and push the current element.
                    sortedNums.erase(sortedNums.begin());
                    sortedNums.insert(num);
                }
                
            } 
            // Otherwise push the current element of nums array.
            else {
                sortedNums.insert(num);
            }
        }
        
        // If sorted set has three elements return the smallest among those 3.
        if (sortedNums.size() == 3) {
            return *sortedNums.begin();
        }
        
        // Otherwise return the biggest element of nums array.
        return *sortedNums.rbegin();
    }
};

### 作法 Three pointers
1. 用long long的最小值

long long firstMax = numeric_limits<long long>::min();
long long secondMax = numeric_limits<long long>::min();
long long thirdMax = numeric_limits<long long>::min();

2. 用pair<int, bool>

pair<int, bool> firstMax = {-1, false};
pair<int, bool> secondMax = {-1, false};
pair<int, bool> thirdMax = {-1, false};

## :memo: Duplicate Zeros (Easy)

### 作法 Two pass
**時間: O(N)**
**空間: O(1)**

class Solution {
    public void duplicateZeros(int[] arr) {
        int possibleDups = 0;
        int length_ = arr.size() - 1;

        // Find the number of zeros to be duplicated
        // Stopping when left points beyond the last element in the original array
        // which would be part of the modified array
        for (int left = 0; left <= length_ - possibleDups; left++) {
            // Count the zeros
            if (arr[left] == 0) {
                // Edge case: This zero can't be duplicated. We have no more space,
                // as left is pointing to the last element which could be included  
                if (left == length_ - possibleDups) {
                    // For this zero we just copy it without duplication.
                    arr[length_] = 0;
                    length_ -= 1;
                    break;
                }
                possibleDups++;
            }
        }

        // Start backwards from the last element which would be part of new array.
        int last = length_ - possibleDups;

        // Copy zero twice, and non zero once.
        for (int i = last; i >= 0; i--) {
            if (arr[i] == 0) {
                arr[i + possibleDups] = 0;
                possibleDups--;
                arr[i + possibleDups] = 0;
            } else {
                arr[i + possibleDups] = arr[i];
            }
        }
    }
}

## :memo: Check If N and Its Double Exist (Easy)
Given an array arr of integers, check if there exist two indices i and j such that:
1\. i != j
2\. 0 <= i, j < arr.length
3\. arr[i] == 2 * arr[j]


### 作法
用unordered_map<int, int> hash去紀錄是否有符合條件的hash[i]>0
條件:
i % 2 == 0 && hash[i / 2] > 0) || hash[2 * i] > 0

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        unordered_map<int, int> hash;
        
        for (int i : arr) {
            if ((i % 2 == 0 && hash[i / 2] > 0) || hash[2 * i] > 0) {
                return true;
            }            
            hash[i]++;
        }
        
        return false;
    }
};

## :memo: Valid Mountain Array (Easy)

### 作法
1. 一開始檢查第一種情況:
1.陣列size為一回傳false
2. 接著檢查第二種情況:
1.頭尾比鄰近高回傳false
3. 接著檢查第三種情況:
1.從頭往尾直到i比i+1還高回傳false
2.從尾往頭直到j比j-1還高回傳false
4. 然後最後確認檢查i是否等於j:
1.是就回傳true
2.不是就回傳false

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        int i = 0;
        int j = 0;
        
        if (arr.size() == 1) {
            return false;
        }
        
        if (arr[0] >= arr[1] || arr[arr.size() - 1] >= arr[arr.size() - 2]) {
            return false;
        }
        
        for (i = 0; i < arr.size() - 1; i++) {
            if (arr[i] >= arr[i + 1]) {
                break;
            }
        }
        for (j = arr.size() - 1; j > 0; j--) {
            if (arr[j] >= arr[j - 1]) {
                break;
            }
        }
        
        if (i == j) {
            return true;
        }
        
        return false;
    }
};

## :memo: Replace Elements with Greatest Element on Right Side (Easy)

### 作法
這題要**從尾巴arr.size() - 1開始往前跑**，並且用temp和maximum去swap

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int maximum = -1;
        int temp = 0;
        
        for (int i = arr.size() - 1; i >= 0; i--) {
            temp = arr[i];
            arr[i] = maximum;
            maximum = max(maximum, temp);            
        }
        
        return arr;
    }
};

## :memo: Move Zeroes (Easy)

### 作法 1 (Space Sub-Optimal)
**時間: O(N)**
**空間: O(N)**
宣告一個同大小的陣列去存正確答案的再assign給nums

void moveZeroes(vector<int>& nums) {
    int n = nums.size();

    // Count the zeroes
    int numZeroes = 0;
    for (int i = 0; i < n; i++) {
        numZeroes += (nums[i] == 0);
    }

    // Make all the non-zero elements retain their original order.
    vector<int> ans;
    for (int i = 0; i < n; i++) {
        if (nums[i] != 0) {
            ans.push_back(nums[i]);
        }
    }

    // Move all zeroes to the end
    while (numZeroes--) {
        ans.push_back(0);
    }

    // Combine the result
    for (int i = 0; i < n; i++) {
        nums[i] = ans[i];
    }
}

### 作法 2 (Space Optimal, Operation Sub-Optimal)
**時間: O(N)**
**空間: O(1)**
利用一個變數lastNonZeroFoundAt記錄不是0的數字有幾個，記錄同時一樣從頭往前擺不是0的數字，最後從lastNonZeroFoundAt開始往後擺0，**i會跑得比lastNonZeroFoundAt還快**

void moveZeroes(vector<int>& nums) {
    int lastNonZeroFoundAt = 0;
    // If the current element is not 0, then we need to
    // append it just in front of last non 0 element we found. 
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != 0) {
            nums[lastNonZeroFoundAt++] = nums[i];
        }
    }
 	// After we have finished processing new elements,
 	// all the non-zero elements are already at beginning of array.
 	// We just need to fill remaining array with 0's.
    for (int i = lastNonZeroFoundAt; i < nums.size(); i++) {
        nums[i] = 0;
    }
}

### 作法 3 (Optimal)
**時間: O(N) However, the total number of operations are optimal.**
**空間: O(1)**
兩個變數lastNonZeroFoundAt,cur寫在一個for迴圈

void moveZeroes(vector<int>& nums) {
    for (int lastNonZeroFoundAt = 0, cur = 0; cur < nums.size(); cur++) {
        if (nums[cur] != 0) {
            swap(nums[lastNonZeroFoundAt++], nums[cur]);
        }
    }
}

## :memo: Find All Numbers Disappeared in an Array (Easy)

### 作法 1 Hash Table

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> hashtable(nums.size(), 0);
        vector<int> res;
        
        for (int i = 0; i < nums.size(); i++) {
            hashtable[nums[i] - 1] = 1;
        }
        
        for (int i = 0; i < hashtable.size(); i++) {
            if (hashtable[i] == 0) {
                res.push_back(i + 1);
            }
        }
        
        return res;
    }
};

### 作法 2 O(1) Space InPlace Modification Solution
**時間: O(N)**
**空間: O(1)**
當遇到數值多少就去把(index=數值-1)內的數字*(-1)，
最後去看哪些index內的數字為正數，
數字為正數的index值+1是缺少的數值


class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        // Iterate over each of the elements in the original array
        for (int i = 0; i < nums.size(); i++) {
            
            // Treat the value as the new index
            int newIndex = abs(nums[i]) - 1;
            
            // Check the magnitude of value at this new index
            // If the magnitude is positive, make it negative 
            // thus indicating that the number nums[i] has 
            // appeared or has been visited.
            if (nums[newIndex] > 0) {
                nums[newIndex] *= -1;
            }
        }
        
        // Response array that would contain the missing numbers
        vector<int> result;
        
        // Iterate over the numbers from 1 to N and add all those
        // that have positive magnitude in the array
        for (int i = 1; i <= nums.size(); i++) {
            
            if (nums[i - 1] > 0) {
                result.push_back(i);
            }
        }
        
        return result;
    }
};

## :memo: Max Consecutive Ones II (Medium)
Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0.

### 作法
利用變數index_zero去記錄目前所要計算的1序列中的遇到的第一個0所在的index，並同時記錄temp為暫時1序列的長度，並把flag設為1，表示不會再去把遇到的第二個0的index標為zero_index，如果遇到第二個0，temp--，並判斷temp是否為max_consecu，是就更新，並把3個變數初始化為0，同時也要去判斷是否掃到底，到底要break，以上為同一個if-else if，最後又另一個if去判斷temp是否為max_consecu。

int findMaxConsecutiveOnes(int* nums, int numsSize) {
    int index_zero = 0;
    int max_consecu = 0;
    int temp = 0;
    int flag = 0;
        
    for (int i = 0; i < numsSize; i++)
    {
        temp++;
        if (nums[i] == 0 && !flag)
        {
            index_zero = i;
            flag = 1;
        }
        else if (nums[i] == 0)
        {
            temp--;
            if (temp > max_consecu)
            {
                max_consecu = temp;     
            }
            i = index_zero;
            index_zero = 0;
            flag = 0;
            temp = 0;
        }
        else if (i == numsSize - 1)
        {
            if (temp > max_consecu)
            {
                max_consecu = temp;
                printf("%d\n", max_consecu);
            }
            break;
        }
        if (temp > max_consecu)
        {
            max_consecu = temp;            
        }        
    }
    
    return max_consecu;
}

### 作法 Sliding window

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int longestSequence = 0;
        int left = 0;
        int right = 0;
        int numZeroes = 0;

        // while our window is in bounds
        while (right < nums.size()) {

            // add the right most element into our window
            if (nums[right] == 0) {
                numZeroes++;
            }

            // if our window is invalid, contract our window 不能有連續兩個0
            while (numZeroes == 2) {
                if (nums[left] == 0) {
                    numZeroes--;
                }
                left++;
            }

            // update our longest sequence answer
            longestSequence = max(longestSequence, right - left + 1);

            // expand our window
            right++;
        }
        
        return longestSequence;
    }
};

## :memo: Product of Array Except Self (Medium)
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is **guaranteed** to fit in a **32-bit** integer.

You must write an algorithm that runs in O(n) time and without using the division operation.


### 作法
如果nums[i]==0就要有另一個處理:重算leftsum和prefixsum

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ans;
        int prefixSum = 1;
        
        int ProductOfAll = 1;
        for (int n : nums) {
            ProductOfAll *= n;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            int remain = 0;
            if (nums[i] != 0) {
                remain = ProductOfAll * prefixSum / nums[i];    
                ProductOfAll /= nums[i];
                prefixSum *= nums[i];            
                ans.push_back(remain);
            } else {
                ProductOfAll = 1;
                prefixSum = 1;
                for (int j = i + 1; j < nums.size(); j++) {
                    ProductOfAll *= nums[j];
                }
                for (int j = i - 1; j >= 0; j--) {
                    prefixSum *= nums[j];
                }
                remain = ProductOfAll * prefixSum;
                prefixSum *= nums[i];
                ans.push_back(remain);
            }                        
        }
        
        return ans;
    }
};

## :memo: 刷題檢討
1. 在寫程式之前花時間用筆去寫完整個code
2. 盡量減少使用debugger的次數，用紙筆去trace
3. 整體都是Easy難度，寫Easy難度的題目必須要做到時間花費少以及錯誤次數降低才行，
**多宣告變數去降低時間複雜度**，面試要想想一些follow-up
### 各種陣列解題技巧使用時機
#### Two pointers
1. 已先做好大小排序
2. 不計較output的大小排序

#### Two pass
1. 需要擁有陣列的特定元素資訊才能操作陣列的情境下

#### Sliding window
1. 檢查陣列的小片段

#### 利用Input的陣列
1. 回傳值不是Input的陣列