🤡Leet Code Extra

Q: Find Minimum in Rotated Sorted Array II & Find Minimum in Rotated Sorted Array --- upvote - Solution 👍

class Solution {
public:
    
    void searchMinimum(vector<int>& nums, int& min, int s, int e) {
        if(s >= e) {
            if(min > nums[s]) min = nums[s];
            return;
        }
        
        int mid = s+(e-s)/2;
        searchMinimum(nums, min, s, mid);
        searchMinimum(nums, min, mid+1, e);
    }

    int findMin(vector<int>& nums) {

        int min = INT_MAX;
        searchMinimum(nums, min, 0, nums.size()-1);
        return min;
        
    }
};

Q1: Shortest Palindrome -> 50 test cases Passed :)

class Solution {
public:
    string shortestPalindrome(string str) {
        string ans = "";
        int s = 0;
        int new_s = 0;
        int e = str.length()-1;
        int count = 0;
        while(s <= e){
            if(str[s] == str[e]) {
                ans += str[s];
                s++; e--;
            }
            else{
                ans += str[e--];
            }
        }
        while(s != str.length()){
            ans += str[s++];
        }
        return ans;
    }
};

Q2: Valid Anagram

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length() == t.length()){
            sort(s.begin(), s.end());
            sort(t.begin(), t.end());

            for(int i = 0; i < s.length(); i++){
                if(s[i] != t[i])
                    return false;
            }
            return true;
        }
        return false;
    }
};

Q3: Kth Largest Element in an Array

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int count = 0;
        int ans;
        if(nums.size() == 1)
            return nums[0];
        
        sort(nums.begin(), nums.end()); 

        for(int i = nums.size()-1; i >= 0; i--) {
            ans = nums[i];
            if(++count == k) {
                ans = nums[i];
                break;
            }
        }
        return ans;
    }
};

Q4: Search Insert Position

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int s = 0;
        int e = nums.size()-1;

        while(s <= e) {
            
            // if array first element is > target
            if(nums[s] > target)
                return s;
            
            // if array last element is < target
            if(nums[e] < target)
                return e+1;

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

            if(nums[mid] == target)
                return mid;
  
            // nums = [1,3], target = 2
            else if(nums[mid] < target)
                s = mid+1;  // move to line 10
                
            // nums = [1,3,5,6], target = 2
            else if(nums[mid] > target)
                e = mid - 1; // move to line 14
            
        }
        return -1;
    }
};


T.C = O(logn);
S.C = O(1);

Q5: Pow(x, n)

Complexity

• Time complexity: The time complexity of the pow() function is O(log(n)).

• Space complexity: The auxiliary space complexity is O(1).

Code

class Solution {
public:
     double myPow(double x, int n) {
        return pow(x, n);
    }
};

Q6: Majority Element -> Unlimited Errors hehehe :)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int max, ans;
        if(nums.size() == 1)
            return nums[0];
            
        for(int i = 0; i < n-1; i++){
            if(nums[i] == nums[i+1]){
                ans = nums[i];
                max++;
            }
            else{
                max = ans; 
                ans = 0;
            }
            ```cpp
            //else{
            //     previous = New;
            //     if(previous > New){
            //         ans = nums[i];
            //     }
            //     else{

            //     }
            // }
```
        }
        return ans;
    }
};

Q7: Length of Last Word

class Solution {
public:
    int lengthOfLastWord(string s) {
        int count = 0;
        int index;
        for(int  i = s.size()-1; i >= 0; i--){
            if(isalnum(s[i])){
                index = i;
                break;
            }
        }
        for(int i = index; i >= 0; i--){
            if(!isalnum(s[i])){
                return count;
            }
            count++;
        }
        return count;
    }
};

Q8: Find Minimum in Rotated Sorted Array

class Solution {
public:
    inline int findMin(vector<int>& arr) {
        return getPivot(arr);
    }

    int getPivot(vector<int>& arr) {
        // condition for sorted array
        if(arr[0] <= arr[arr.size()-1])
            return arr[0];

        int s = 0;
        int e = arr.size()-1;
        
        while(s < e) {
            int mid = s+(e-s)/2;

            if(arr[mid] >= arr[0])
                s = mid+1;
            else if(arr[mid] < arr[0])
                e = mid;  
     
        }
        return arr[s];
    }
};

Q9: Plus One --> infinite Errors :(

#include<iostream>
#include<vector>
using namespace std;

vector<int> plusOne(vector<int>& digits) {
    int n = digits.size()-1;
    digits[n] += 1;
    
    if(digits[n] >= 10){
        int rem = digits[n] % 10;
        int quo = digits[n] / 10;
        digits.pop_back();
        digits.push_back(quo);
        digits.push_back(rem);
    }
    return digits;
}

int main(){
    vector<int> arr = {100};
    cout << plusOne(arr);
}

Q10: Find the Index of the First Occurrence in a String

int strStr(string haystack, string needle) {
    int found = haystack.find(needle);
    
    if (found != string::npos) // (!(found == npos)) --> print else state
        return found; 
          
    return -1;
}

Q11: Remove Duplicates from Sorted Array

aik dam perfect code h bss TLE de rha heheh :)

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {  
        vector<int> ans;

        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] != nums[i+1])
                ans.push_back(nums[i]);
        }

        nums = ans;
        return nums.size();
    }
};

Q12: Single Number

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        for(int i = 1; i < nums.size()-1; i++)
            if(nums[0] != nums[1])
                return nums[0];

            if(nums[i-1] != nums[i] && nums[i] != nums[i+1]) 
                return nums[i];
        }
        return nums[nums.size()-1];
    }
};

Q13: Sort An Array of 0s, 1s and 2s

#include <bits/stdc++.h> 
void sortArray(vector<int>& arr, int n)
{
    for(int i = 1; i < n; i++) {
        for(int j = 0; j < n-i; j++) {
            if(arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

Q14: K Largest Element

#include <bits/stdc++.h> 
vector<int> Klargest(vector<int> &a, int k, int n) {
    
    vector<int> arr;
    sort(a.begin(), a.end());
    
    for(int i = n-k; i < n; i++) {    // i = 4-2 => 2, i = 3
         arr.push_back(a[i]); // arr[i] = 3, arr[i] = 4
    }
    
    return arr; // 3, 4 returned
}

// input [1, 2, 3, 4], k = 2, n = 4
// output [3, 4].

Q15: Intersection Of Two Sorted Arrays

#include <bits/stdc++.h> 
vector<int> findArrayIntersection(vector<int> &arr1, int n, vector<int> &arr2, int m) {
	if(n < 1 && arr1[0] == arr2[0]) {
        return {arr1[0]};
	}
	vector<int> ans;
	int count = 0, k = 0;

	for(int i = 0; i < n; i++) {
		for(int j = k ; j < m; j++) {
			if(arr1[i] == arr2[j]) {
				ans.push_back(arr1[i]);
				j++;
				k = j;
				break;
			}
		}
	}
	if(ans.size() == 0) 
		return {-1};
	return ans;
}

Q16. 53. Maximum Subarray

class Solution {
public:

    int maxSubArray(vector<int>& nums) {
        int sum = 0;
        int maxSum = INT_MIN;
        for(int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            maxSum = max(maxSum, sum);
            if(sum < 0) sum = 0;
        }
        return maxSum;
    }
};

Q17: Add Digits

class Solution {
public:
    int addDigits(int num) {
        
        int x = num;

        while(num / 10 != 0) {
            x = num / 10;
            int rem = num % 10;
            num = x + rem;
        }
        return num;
    }
};

Q18: 1979. Find Greatest Common Divisor of Array

class Solution {

public:

    int sol(int p, int  q) {
        if(q == 0) return p;
        return sol(q, p%q);
    }

    int findGCD(vector<int>& nums) {
        
        int maxi = INT_MIN, mini= INT_MAX;

        for(int i = 0; i < nums.size(); i++) {
            maxi = max(maxi, nums[i]);
            mini = min(mini, nums[i]);
        }

        return sol(mini, maxi);
    }
};