“A year from now you may wish you had
started today”

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def first():
            l, r = 0, len(nums)-1
            first = -1 
            while l <= r:
                mid = (l+r)//2
                if nums[mid] == target:
                    first = mid
                    r = mid - 1
                elif nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
            return first
        def last():
            l, r = 0, len(nums)-1
            last = -1 
            while l <= r:
                mid = (l+r)//2
                if nums[mid] == target:
                    last = mid
                    l = mid + 1
                elif nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
            return last

        f = first()
        if f == - 1: return [-1, -1]
        la = last()
        return [f, la]

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def lower_bound():
            l, r = 0, len(nums)-1
            ans = len(nums)
            while l <= r:
                mid = (l+r)//2
                if nums[mid] >= target:
                    ans = mid
                    r = mid - 1
                else:
                    l = mid + 1
            return ans
        def upper_bound():
            l, r = 0, len(nums)-1
            ans = len(nums)
            while l <= r:
                mid = (l+r)//2
                if nums[mid] > target:
                    ans = mid
                    r = mid - 1
                else:
                    l = mid + 1
            return ans
        
        lb = lower_bound()
        up = upper_bound() - 1
        if lb <= up:
            return [lb, up]
        return [-1, -1]

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        lb = bisect.bisect_left(nums, target)
        if lb >= len(nums) or nums[lb] != target:
            return [-1, -1]
        ub = bisect.bisect_right(nums, target)
        return [lb, ub-1]
    

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto lb = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        if (lb >= nums.size() || nums[lb] != target)
            return {-1, -1};
        auto ub = upper_bound(nums.begin(), nums.end(), target) - nums.begin();
        return {(int)lb, (int)ub-1};
    }
};

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = len(matrix)
        col = len(matrix[0])
        l, r = 0, (row * col) - 1
        while l <= r:
            mid = (l+r)//2
            # i = mid // col
            # j = mid % col
            i, j = divmod(mid, col) # one liner for the above
            if matrix[i][j] == target:
                return True
            elif target >= matrix[i][j]:
                l = mid + 1
            else:
                r = mid - 1
        return False

Time complexity = O(n×log(maxDays)) ; Space complexity = O(1)

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        max_days = max(bloomDay)
        min_days = -1
        L, R = 0, max_days
        while L <= R:
            mid = (L+R)//2
            count = 0
            m_count = 0
            for bloom in bloomDay:
                if mid >= bloom:
                    count += 1
                    if count >= k:
                        m_count += 1
                        count = 0
                else:
                    count = 0
            if m_count >= m:
                min_days = mid
                R = mid - 1  
            else:
                L = mid + 1
            
        return min_days

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        max_num = max(nums)
        divisor = max_num
        L, R = 1, max_num # make sure to start from 1, if L = 0 we might encounter a runtime error, division by zero
        while L <= R:
            mid = (L+R)//2

            total_sum = sum((num + mid - 1)//mid for num in nums)
           # math.ceil(num / mid) is the same as (num+mid-1)//mid, the second on is more facter on CPU.
            if total_sum <= threshold:
                divisor = mid
                R = mid - 1
            else:
                L = mid + 1
        return divisor

String input = new String("hello");
System.out.println(input == "hello");  

String input = "hello";
System.out.println(input == "hello");

String input = "hello";
System.out.println(input == "hello");  // True

String input = new String("hello");
System.out.println(input == "hello");  // false

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        i = 0 
        while i < len(nums):
            correct_pos = nums[i] - 1
            if nums[i] != nums[correct_pos]:
                nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
            else:
                i +=1 
        
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return nums[i]

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        i = 0 
        while i < len(nums):
            if nums[i] != i + 1:
                correct_pos = nums[i] - 1
                if nums[i] != nums[correct_pos]:
                    nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
                else:
                    return nums[i]
                
            else:
                i += 1
        
        return -1

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = nums[nums[0]]
        fast = nums[nums[nums[0]]]

        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]
        
        slow = nums[0]

        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        
        return slow

Time complexity : O(n) & Space Complexity: O(1)

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = nums[nums[0]]
        fast = nums[nums[nums[0]]]

        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]
        
        slow = nums[0]

        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        
        return slow

class Solution:
    def maxCoins(self, piles: List[int]) -> int:
        piles_per_person = len(piles) // 3
        piles.sort(reverse=True)
        sum = 0 
        for i in range(1, len(piles) - piles_per_person, 2):
            sum += piles[i]
        return sum

Time complexity : O(n*log n) & Space Complexity: O(1)