# Leet Code Extra

## `Q:` [Find Minimum in Rotated Sorted Array II](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/) & [Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/) --- upvote - [Solution](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/solutions/4912937/divide-and-conquer-approach-find-min-in-o-lgn) :thumbsup:

```cpp
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](https://leetcode.com/problems/shortest-palindrome/) -> 50 test cases Passed :)

```cpp
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](https://leetcode.com/problems/valid-anagram/)

```cpp
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](https://leetcode.com/problems/kth-largest-element-in-an-array/)

```cpp
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](https://leetcode.com/problems/search-insert-position/)

{% code lineNumbers="true" %}

```cpp
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);
```

{% endcode %}

## `Q5:`    [ Pow(x, n)](https://leetcode.com/problems/powx-n/)

## Complexity <a href="#complexity" id="complexity"></a>

* **Time complexity:** The time complexity of the pow() function is O(log(n)).
* **Space complexity:** The auxiliary space complexity is O(1).

## Code <a href="#code" id="code"></a>

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

## `Q6:`    [Majority Element](https://leetcode.com/problems/majority-element/) -> Unlimited Errors hehehe :)&#x20;

````cpp
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](https://leetcode.com/problems/length-of-last-word/)

```cpp
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](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)

```cpp
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](https://leetcode.com/problems/plus-one/) --> infinite Errors :(&#x20;

```cpp
#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](https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/)

{% code overflow="wrap" fullWidth="false" %}

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

{% endcode %}

## `Q11:`  [Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/)&#x20;

#### &#x20;aik dam perfect code h bss TLE de rha heheh :)

```cpp
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](https://leetcode.com/problems/single-number/)

```cpp
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](https://www.codingninjas.com/studio/problems/easy_6613919?topList=tiger-analytics-interview-questions\&leftPanelTab=0)

```cpp
#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](https://www.codingninjas.com/studio/problems/k-largest-element_1062624?topList=tiger-analytics-interview-questions\&leftPanelTab=0)

```cpp
#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](https://www.codingninjas.com/studio/problems/intersection-of-2-arrays_1082149?topList=tiger-analytics-interview-questions\&leftPanelTab=0)

```cpp
#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](https://leetcode.com/problems/maximum-subarray/)

```cpp
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](https://leetcode.com/problems/add-digits/)

```cpp
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](https://leetcode.com/problems/find-greatest-common-divisor-of-array/)

```cpp
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);
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dsa-cpp.gitbook.io/nafees/leet-code-extra.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.