Leetcode 75

Merge Strings Alternatively

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        string res;
        int k = 0;
        for(int i = 0; i < word1.size(); i++) {
            res.push_back(word1[i]);
            if(k < word2.size()) res.push_back(word2[k++]);
        }
        
        for(; k < word2.size(); k++) {
            res.push_back(word2[k]);
        }
        return res;
    }
};

Reverse Vowels - 479/480 :)

class Solution {
public:
    bool isVowel(char ch) {
        return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' || ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U');
    }
    void search(string str, int s, int e, int &j) {
        if(s >= e) {
            if(isVowel(str[e])) j = e;
            return;
        }

        int mid = s+(e-s)/2;
        search(str, s, mid, j);
        search(str, mid+1, e, j);
    }

    string reverseVowels(string s) {
        int j = -1;
        int e = s.length();

        for(int i = 1; i <= e; i++) {
            if(isVowel(s[i-1])) {
                search(s, i, e, j);
                if(j != -1) {
                    e = j-1;
                    swap(s[i-1], s[j]);
                    j = -1;
                }
            }
        }
        return s;
    }
};

Kids With the Greatest Number of Candies

class Solution {
public:
    
    void search(vector<int> candies, int sumOFEach, int s, int e, bool& isGreater) {
        if(s >= e) {
            if(sumOFEach < candies[s]) {
                isGreater = false;
            }
            return;
        }
        int mid = s+(e-s)/2;
        search(candies, sumOFEach, s, mid, isGreater);
        search(candies, sumOFEach, mid+1, e, isGreater);
    }

    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        vector<bool> result;

        for(int i = 0; i < candies.size(); i++) {
            bool isGreater = true;
            search(candies, candies[i]+extraCandies, 0, candies.size()-1, isGreater);
            result.push_back(isGreater);
        }
        return result;
    }
};

Product of Array Except Self

class Solution {
public:

    void productOfArr(vector<int>& nums, int s, int e, int& zeroProduct, int& product, int& zeroCount) {
        if(s>=e) {
            if(nums[s] != 0){
                zeroProduct *= nums[s];
            }
            if(nums[s] == 0)
                zeroCount++;
            product *= nums[s];
            return;
        }

        int mid = s+(e-s)/2;
        productOfArr(nums, s, mid, zeroProduct, product, zeroCount);
        productOfArr(nums, mid+1, e, zeroProduct, product, zeroCount);
    }

    vector<int> productExceptSelf(vector<int>& nums) {
    
        vector<int> res(nums.size(), 0);
        int size = nums.size();
        int zeroCount = 0;
        int product = 1;
        int zeroProduct = 1;

        productOfArr(nums, 0, size-1, zeroProduct, product, zeroCount); // O(lgn)
        
        // If there exist zeros more than one, then the whole array will be zero!

        if(zeroCount <= 1) {
            for(int i = 0; i < size; i++){ // O(n)
                if(nums[i] == 0) res[i] = zeroProduct;
                else res[i] = product/nums[i];
            }
        }

        return res;
    }
};

Max Number of K-Sum Pairs

Solution - I --- O(nlgn) with TLE :)

class Solution {
public:

    void findPair(vector<int>& nums, int& firstElem, int s, int e, int& count, int k, bool& isFound) {
        if(s >= e) {
            if(nums[s] != INT_MIN  && firstElem + nums[s] == k && !isFound) {
                isFound = true;
                nums[s] = INT_MIN;
                count++;
            }
            return;
        }

        int mid = s+(e-s)/2;

        findPair(nums, firstElem, s, mid, count, k, isFound);
        findPair(nums, firstElem, mid+1, e, count, k, isFound);
    }

    int maxOperations(vector<int>& nums, int k) {
        int count = 0;

        for(int i = 0; i < nums.size()-1; i++) {
            bool isFound = false;
            findPair(nums, nums[i], i+1, nums.size()-1, count, k, isFound);
        }
        
        return count;
    }
};

Solution - II --- O(nlgn + lgn --> nlgn)

int maxOperations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());

        int s = 0;
        int e = nums.size()-1;
        int count = 0;
        while(s < e) {
            int sum = nums[s] + nums[e]; 
            if(sum == k) {
                count++;
                s++;
                e--;
            }
            else if(sum < k) s++;
            else e--;
        }

        return count;
    }

Maximum Average Subarray I - TLE

class Solution {
public:
    
    void getSum(vector<int>& nums, double& newSum, int s, int e) {
        if(s >= e) {
            newSum += nums[s];
            return;
        }

        int mid = s+(e-s)/2;
        getSum(nums, newSum, s, mid);
        getSum(nums, newSum, mid+1, e);
    }

    double findMaxAverage(vector<int>& nums, int k) {
        double oldSum = INT_MIN;

        for(int i = 0; i <= nums.size()-k; i++) {
            double newSum = 0.0;
            getSum(nums, newSum, i, i+k-1);
            newSum /= k;
            if(newSum > oldSum) 
                oldSum = newSum;
        }
        return oldSum;
    }
};

334. Increasing Triplet Subsequence

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int fMin = INT_MAX, sMin= INT_MAX;

        for(int i = 0; i < nums.size(); i++) {
            if(fMin > nums[i]) {
                fMin = nums[i];
            }
            else if(sMin > nums[i] && nums[i] != fMin) {
                sMin = nums[i];
            }
            else if(nums[i] > fMin && nums[i] > sMin) {
                return true;
            }
        }
        return false;
    }
};

283. Move Zeroes

class Solution {
public:

    void searchNonZero(vector<int>& nums, int s, int e, int& j, bool& isFound) {
        if(s>=e) {
            if(!isFound && nums[s] != 0) {
                j = s;
                isFound = true;
            }
            return;
        }

        int mid = s+(e-s)/2;
        searchNonZero(nums, s, mid, j, isFound);
        searchNonZero(nums, mid+1, e, j, isFound);
    }

    void moveZeroes(vector<int>& nums) {
        if(nums.size() == 1) return;
        for(int i  = 0; i < nums.size()-1; i++) {
            int j = -1;
            bool isFound = false;
            if(nums[i] == 0) {
                searchNonZero(nums, i+1, nums.size()-1, j, isFound);
            }
            if(j != -1) {
                swap(nums[i], nums[j]);
            }
        }
    }
};

392. Is Subsequence

class Solution {
public:

    void search(string t, char ch, int& j, int s, int e, bool& isFound, int& count) {
        if(s>=e) {
            if(t[e] == ch && !isFound) {
                j = e+1;
                count++;
                isFound = true;
            }
            return;
        }

        int mid = s+(e-s)/2;
        search(t, ch, j, s, mid, isFound, count);
        search(t, ch, j, mid+1, e, isFound, count);
    }
    
    bool isSubsequence(string s, string t) {
        int j = 0;
        int count = 0;
        cout << s.size();

        for(int i = 0; i < s.size(); i++) {
            bool isFound = false;
            if(j < t.size())
                search(t, s[i], j, j, t.size(), isFound, count);
            if(!isFound) return false;
        }
         return count == s.size();
    }
};

151. Reverse Words in a String

class Solution {
public:
    
    string reverseWords(string s) {
        string temp = "";
        int i = 0;
        int k = 0;
        while(i < s.size()) {
            if(temp.empty() && s[i] == ' ' || k > 0 && temp[k-1] == ' ' && s[i] == ' ') {
                while(s[i] == ' ') 
                    i++;
            }
            else  {    
                temp += s[i++];
                k++;
            }
        } 
        
        s.clear();
        int n = temp[temp.size()-1] == ' ' ? temp.size()-1: temp.size();
        for(int i = 0; i < n; i++) {
            s += temp[i];
        }
        temp.clear();
        string res = "";
        
        for(int i = s.size()-1; i >= 0; i--) {
            if(s[i] == ' ') {
                int j = temp.size()-1;
                while(j >= 0) {
                    res += temp[j];
                    j--;
                }
                res += " ";
                temp.clear();
            }
            else {
                temp += s[i];
            }
        }
        int j = temp.size()-1;
        while(j >= 0) {
            res += temp[j];
            j--;
        }
        return res;
    }
};

643. Maximum Average Subarray I - 115 / 127 test cases passed

class Solution {
public:
    void sol(vector<int>& nums, int s, int e, int& curSum) {
        if(s >= e) {
            curSum += nums[s];
            return;
        }
        int mid = s + (e-s)/2;
        sol(nums, s, mid, curSum);
        sol(nums, mid+1, e, curSum);
    }
    double findMaxAverage(vector<int>& nums, int k) {
        int prevSum = INT_MIN;
        int curSum = 0;
        for(int i = 0; i <= nums.size()-k; i++) {
            curSum = 0;
            sol(nums, i, i+k-1, curSum);
            prevSum = max(prevSum, curSum);
        }
        return (double)prevSum/k;
    }
};

2095. Delete the Middle Node of a Linked List

/**
 * 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* deleteMiddle(ListNode* head) {
        if(head -> next == nullptr) {
            return nullptr;
        }
        ListNode* temp = head;
        int count = 0;
        while(temp != nullptr) {
            temp = temp -> next;
            count++;
        } 
        if(count % 2 == 0) count++;
        
        int i = 0;
        ListNode* cur = nullptr;
        temp = head;
        while(i < count / 2) {
            cur = temp;
            temp = temp -> next;
            i++;
        }
        if(temp == nullptr) 
            cur -> next = temp;
        else
            cur -> next = temp -> next;
        return head;
    }
};

206. Reverse Linked List

/**
 * 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* reverseList(ListNode* head) {
        // handle first Node
        if(head == nullptr || head -> next == nullptr) return head;

        ListNode* prev = head;
        ListNode* cur = head -> next;
        ListNode* temp = head -> next -> next;
        prev -> next = nullptr;

        // handle middle Nodes
        while(temp != nullptr) {
            cur -> next = prev;
            prev = cur;
            cur = temp;
            temp = temp -> next;
        }

        // handle last Node
        cur -> next = prev;
        head = cur;
        return head;
    }
};

328. Odd Even Linked List

/**
 * 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* oddEvenList(ListNode* head) {
        if(head == nullptr || head -> next == nullptr || head -> next -> next == nullptr) return head;
        
        ListNode* odd = head;
        ListNode* even = head -> next;
        // always point the next of odd to even's first node
        ListNode* evenFirstNode = head -> next;
        
        while(even  != nullptr && even -> next != nullptr) {
            odd -> next = even -> next;
            odd = odd -> next;
            
            even -> next = odd -> next;
            odd -> next = evenFirstNode;
            
            even = even -> next;
        }

        return head;
    }
};