< Nafees />
github
  • Assignments - DSA
  • Long Integer Operations
  • OOP
    • Introduction
    • Implementation
  • Sorting Algorithms
    • Selection Sort
    • Bubble Sort
    • Insertion Sort
    • Shell Sort
    • Shuffle
    • Merge Sort
    • Convex Hull
    • Quick sort
    • System Sort
    • Heap-Sort
  • Binary Search
  • Binary Search By Recursion
  • Two-Pointer
  • String
  • LeetCode 75
    • Array/String
    • Hash Map
    • BST
    • Binary Search
  • Top Interview 150
    • Linked-List
  • Leetcode Programming Skill
    • Math
  • Leetcode 75
  • 🤡Leet Code Extra
  • Arrays
    • 1-D Array
    • 2-D Arrays
  • 👨‍🍳Basic Math - Codechef
  • ☠️Recursion
  • 😁Public Member Functions
    • Strings Functions
  • 👾Linked List
    • What's Linked List & Implementation?
      • Singly Linked List
      • Doubly Linked List
    • Problems
  • 📚Stack
    • What's Stack & Implementation?
      • Stack Using Array
      • Stack using LL
    • Problems
  • 🏧Queue
    • What's Queue & Implementation?
      • Simple Queue
      • Queue using LL
      • Circular Queue
      • Deque using Linked List
      • STL Deque
    • Problems
  • 🏧Priority Queue
    • What's Priority Queue & Implementation
      • OrderedArrayMaxPQ.Java
      • Maximum-Oriented PQ using Binary Heap
      • Minimum-Oriented PQ using Binary Heap
    • Problems
  • 🗓️Hash Table
    • What's Hash Table & Implementation
      • ST - Seperate Chaining
      • ST - Linear Probing
    • Problems
  • 🎴Symbol Table
    • What's Symbol Table and implementation
      • ST Using Binary search (ordered array)
      • ST Using Binary Search Tree
      • ST Using Left-Leaning Red-Black Tree
      • ST Using Hash Table
    • Problems
  • 🔗Union-Find (Dynamic Connectivity problem)
    • What is a Union Find Data Structure?
    • Implementation
  • 🎋Binary Tree
    • What's Binary Tree & Implementation?
      • Traversal
      • Red-Black BST
  • 🌴Trie
    • What's Trie & Implementation?
    • Problems
  • 😎Project
    • Expression Evaluation
Powered by GitBook
On this page
  • Merge Strings Alternatively
  • Reverse Vowels - 479/480 :)
  • Kids With the Greatest Number of Candies
  • Product of Array Except Self
  • Max Number of K-Sum Pairs
  • Maximum Average Subarray I - TLE
  • 334. Increasing Triplet Subsequence
  • 283. Move Zeroes
  • 392. Is Subsequence
  • 151. Reverse Words in a String
  • 643. Maximum Average Subarray I - 115 / 127 test cases passed
  • 2095. Delete the Middle Node of a Linked List
  • 206. Reverse Linked List
  • 328. Odd Even Linked List

Was this helpful?

Leetcode 75

PreviousMathNextLeet Code Extra

Last updated 11 months ago

Was this helpful?

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

- 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;
    }
};
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;
    }
};
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;
    }
};
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;
    }
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;
    }
};
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;
    }
};
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]);
            }
        }
    }
};
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();
    }
};
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;
    }
};
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;
    }
};
/**
 * 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;
    }
};
/**
 * 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;
    }
};
/**
 * 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;
    }
};

- TLE

- 115 / 127 test cases passed

Merge Strings Alternatively
Reverse Vowels
Kids With the Greatest Number of Candies
Product of Array Except Self
Max Number of K-Sum Pairs
Maximum Average Subarray I
334. Increasing Triplet Subsequence
283. Move Zeroes
392. Is Subsequence
151. Reverse Words in a String
643. Maximum Average Subarray I
2095. Delete the Middle Node of a Linked List
206. Reverse Linked List
328. Odd Even Linked List
Page cover image