---
# System prepended metadata

title: Leetcode 30 days May Challenge

---

# Leetcode 30 days May Challenge 
![leetcode_logo](https://assets.leetcode.com/static_assets/public/images/LeetCode_Sharing.png)
## Week-1
### Day1: First Bad Version
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have `n` versions `[1, 2, ..., n]` and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API `bool isBadVersion(version)` which will return whether `version` is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

**Example:**
```markdown
Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3)-> false
call isBadVersion(5)-> true
call isBadVersion(4)-> true

Then 4 is the first bad version. 
```
***
Approach-1: 
> Brute Force (`Linear Scan`) - TLE with large input <br>
> Time Complexity - O(n) <br>
> Space Complexity - O(1)
```cpp=
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        for (int i = 1; i <= n; i++) {
            if (isBadVersion(i) == true) {
                return i;
                break;
            }
        }
        return -1;
    }
};
```
*Submission Analysis* - 
```markdown
12 / 22 test cases passed.
Status: Time Limit Exceeded(TLE)
Last executed input: 1420736637 1150769282 [n, first_bad_number]
```
***
Approach-2: 
> `Binary Search` for bad Version
> Time Complexity - O(logn)
> Space Complexity - O(1)
```cpp=
class Solution {
public:
     int firstBadVersion(int n) {
        int l = 1, r = n;
         while (l <= r) {
             int mid = l + (r-l)/2;
             if (isBadVersion(mid) == true && isBadVersion(mid-1) == false)
                 return mid;
             else if (isBadVersion(mid) == true && isBadVersion(mid-1) == true)
                 r = mid;
             else 
                 l = mid+1;
         }
         return -1;
     }
};
```
*Submission Analysis* - 
```markdown
22 / 22 test cases passed.
Status: Accepted
Runtime: 0 ms
Memory Usage: 5.8 MB
```

### Day2: Jewels and Stones
You're given strings `J` representing the types of stones that are jewels, and `S` representing the stones you have.  Each character in `S` is a type of stone you have.  You want to know how many of the stones you have are also jewels.

The letters in `J` are guaranteed distinct, and all characters in `J` and `S` are letters. Letters are case sensitive, so `"a"` is considered a different type of stone from `"A"`.

**Example 1:**
```markdown
Input: J = "aA", S = "aAAbbbb"
Output: 3
```
**Example 2:**
```markdown
Input: J = "z", S = "ZZ"
Output: 0
```
**Note:**

- `S` and `J` will consist of letters and have length at most 50.
- The characters in `J` are distinct.
***
Approach-1: 
> Approach - Linear scan ( For each stone, check if it is a jewel) <br>
> Time Complexity - O(J*S) <br>
> Space Complexity - O(1)
```cpp
class Solution {
public:
    /* For each stone, check if it is a jewel. */
    int numJewelsInStones(string J, string S) {
        int count = 0;
        for (char& ch_s : S) {
            for (char& ch_j : J) {
                if (ch_s == ch_j) {
                    count++;
                }
            }
        }
        return count;
    }
```
*Submission Analysis* - 
```markdown
254 / 254 test cases passed.
Status: Accepted
Runtime: 0 ms
Memory Usage: 6 MB
```
Approach-2:
> `Set` of Stones and check if jewels is there (Since jewels are `unique`, given) <br>
> Time Complexity - O(J + S) <br>
> Space Complexity - O(S)
```cpp
int numJewelsInStones(string J, string S) {
        set<char> jewels;      // <- Set O(logJ) <- Balanced BST based
        for (char& j : J) {
            jewels.insert(j);    
        }
        
        int count = 0;
        for (char& s : S) {
            if (jewels.find(s) != jewels.end()) {
                count++;
            }
        }
        return count;
    }
```
*Submission Analysis* - 
```markdown
254 / 254 test cases passed.
Status: Accepted
Runtime: 0 ms (But, actually more in approximation)
Memory Usage: 6.3 MB
```
> NOTE: Another variation can be:-
```cpp
unordered_multiset<char> jewels;// <- `Unordered_Mutiset` O(1) <- Hash based [Here took more time and space, why?]
```
*Submission Analysis* - 
```markdown
254 / 254 test cases passed.
Status: Accepted
Runtime: 0 ms (But, actually more in approximation) then `Set`
Memory Usage: 6.5 MB
```
***
### Day3: P3...