// First missing positive

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        if (nums.empty()) {
            return 1;
        }
        
        int low = 0, high = nums.size() - 1;
        while (low < high) {
            while (low < high && nums[low] > 0) low++;
            while (low < high && nums[high] <= 0) high--;
            if (low < high)
                swap(nums, low, high);
        }
        
        int endOfPositives = nums[low] > 0 ? low : low - 1;
        int start = 0;
        
        for (int i = 0; i <= endOfPositives; i++) {
            if (nums[i] > endOfPositives + 1) {
                continue;
            }

            int idxToNegate = nums[i];
            if (idxToNegate < 0) {
                idxToNegate *= -1;
            }
            
            if (nums[idxToNegate - 1] > 0) {
                nums[idxToNegate - 1] *= -1;
            }
        }
        
        for (int i = 0; i <= endOfPositives; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        
        return endOfPositives + 2;
    }
    
private:
    void swap(vector<int> &nums, int i, int j) {
        int k = nums[i];
        nums[i] = nums[j];
        nums[j] = k;
    }
};


// Group anagrams
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> result;
        unordered_map<string, vector<string>> um;
        for (string str: strs) {
            string sortedString = str;
            sort(sortedString.begin(), sortedString.end());
            um[sortedString].push_back(str);
        }
        
        for (auto e: um) {
            result.push_back(e.second);
        }
        return result;
    }
};

// Find duplicate with constant space and time complexity.
class Solution {
public:
    
// [1, 2, 3, 4, 5, 4]
int findDuplicate(vector<int>& nums) {
        // Fast and Slow pointers:
        if (nums.empty() || nums.size() == 1) {
            return -1;   
        }
        int slowIdx = nums[0], fastIdx = nums[0];
        do {
            slowIdx = nums[slowIdx];
            fastIdx = nums[nums[fastIdx]];
        } while (slowIdx != fastIdx);
        
        slowIdx = nums[0];
        while (slowIdx != fastIdx) {
            slowIdx = nums[slowIdx];
            fastIdx = nums[fastIdx];
        }
        return slowIdx;
    }
};


// Add two numbers
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = new ListNode(0);
        ListNode *prevNode = nullptr;
        int carry = 0;
        
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int sum = carry;
            if (l1 != nullptr) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != nullptr) {
                sum += l2->val;
                l2 = l2->next;
            }
            if (prevNode == nullptr) {
                head->val = sum % 10;
                prevNode = head;
            } else {
                prevNode->next = new ListNode(sum % 10);
                prevNode = prevNode->next;
            }
            carry = sum / 10;
        }
        return head;
    }
};

// Merge intervals - sort by startTime
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        sort(intervals.begin( ), intervals.end( ), []( const auto& lhs, const auto& rhs)
{
   return lhs[0] < rhs[0];
});
    vector<int> curInterval = intervals[0];
    for (int i = 1; i < intervals.size(); i++) {
        if (curInterval[1] >= intervals[i][0]) {
            curInterval[1] = max(curInterval[1], intervals[i][1]);
            curInterval[0] = min(curInterval[0], intervals[i][0]);
        } else {
            result.push_back(curInterval);
            curInterval = intervals[i];
        }
    }
    result.push_back(curInterval);
    return result;
}
};

// Max sub array
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        int sum = 0, maxSum = numeric_limits<int>::min();
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (sum > maxSum) {
                maxSum = sum;    
            }
            if (sum < 0) {
                sum = 0;
            }
        }
        return maxSum;
    }
};


// Insert Delete GetRandom in O(1) time
class RandomizedSet {
public:
    RandomizedSet() {
        
    }
    bool insert(int val) {
        if (m.find(val) != m.end()) return false;
        nums.emplace_back(val);
        m[val] = nums.size() - 1;
        return true;
    }
    bool remove(int val) {
        if (m.find(val) == m.end()) return false;
        int last = nums.back();
        m[last] = m[val];
        nums[m[val]] = last;
        nums.pop_back();
        m.erase(val);
        return true;
    }
    int getRandom() {
        return nums[rand() % nums.size()];
    }
private:
    vector<int> nums;
    unordered_map<int, int> m;
};