class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return n;
        //pre : record the end index of the different number array
        //cur : record the current checking index
        int pre = 0, cur = 0;
        while (cur < n) {
            if (nums[cur] == nums[pre]) ++cur;
            else {
                nums[pre+1] = nums[cur];
                pre++;
                cur++;
            }
        }
        return pre + 1;
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 2;
        int n = nums.size();
        if (n <= k) return n;
        int pre = 1, cur = 1, count = 1;
        while (cur < n) {
            if (nums[cur] != nums[cur-1]) {
                count = 1;
                nums[pre++] = nums[cur];
            }
            else {
                //only record the duplicate numbers for k times at most 
                if (count < k) {
                    nums[pre++] = nums[cur];
                    count++;
                }
            }
            cur++;
        }
        return pre;
    }
};

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* cur = head;
        while (cur && cur->next) {
            //duplicate value, we delete the next node 
            if(cur->val == cur->next->val) {
                ListNode* temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            }
            else {
                cur = cur->next;
            }
        }
        return head;
    }
};

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* start = new ListNode(0);
        start->next = head;
        //pre record all the unique value node 
        ListNode* pre = start;
        while (pre->next) {
            ListNode* cur = pre->next;
            //skip all the duplicate value node 
            while (cur->next && cur->next->val == cur->val) {
                ListNode* temp = cur;
                cur = cur->next;
                delete temp;
            }
            //cur point to the duplicate value , we skip all the duplicate value 
            if (cur != pre->next) pre->next = cur->next;
            //no duplicate value, just move forward 
            else pre = pre->next;
        }
        return start->next;
    }
};

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != val) nums[res++] = nums[i];
        }
        return res;
    }
};

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;
    }
};

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); ++i) {
            if (m.find(nums[i]) != m.end() && i - m[nums[i]] <= k) return true;
            else m[nums[i]] = i;
        }
        return false;
    }
};

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        multiset<long long> bst;
        for (int i = 0; i < nums.size(); i++) {
            if (bst.size() == k + 1) bst.erase(bst.find(nums[i - k - 1]));
            auto lb = bst.lower_bound(nums[i] - t);
            if (lb != bst.end() && (*lb - nums[i] <= t)) return true;
            bst.insert(nums[i]);
        }
        return false;
    }
};

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low = 1;
        int high = nums.size();
        int mid = 0, count = 0;
        while (low < high) {
            mid = (low + high) / 2;
            count = 0;
            for(auto num : nums) 
                if (num <= mid)  count++;
            if (count <= mid)
                low = mid + 1;
            else 
                high = mid;
        }
        return low;
    }
};

class Solution {
public:
    string removeDuplicateLetters(string s) {
        int m[256] = {0}, visited[256] = {0};
        string res = "0";
        //1st pass to get the frequency of each word
        for (auto a : s) ++m[a];
        for (auto a : s) {
            --m[a];
            if (visited[a]) continue;
            while (a < res.back() && m[res.back()]) {
                visited[res.back()] = 0;
                res.pop_back();
            }
            res += a;
            visited[a] = 1;
        }
        return res.substr(1);
    }
};