✅ 34. Find First and Last Position of Element in Sorted Array

🟢Using regular binary search

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]

🟡Using the concept of lower bound and upper bound

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]

🔴Using the bisect method (import bisect)

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]
    

👾C++ implementation using STL (lower_bound and upper_bound)

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

🌟🚀 @AceCoding Presents! 🚀🌟

✅ 74. Search a 2D Matrix

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

🌟🚀 @AceCoding Presents! 🚀🌟

💻 IP Lab File 📂🚀

#IPLAB #IP #3rdYear #AceCoding

@AceCoding presents

🟥 Hard Medium (1945) is nearly a hard question; binary search

🧐 It took me around 35 min but I think I was lucky this time

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

@AceCoding
https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/

🟡 Easy Medium (1541) leetCode Question: 1283. Find the Smallest Divisor Given a Threshold

Solution: Straight-forward easy to understand

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

🌟🚀 @AceCoding Presents! 🚀🌟

https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/

Applications are Open for A2SV G6 Education!

The time has come for A2SV to welcome new members! We’re looking for team-oriented individuals with a never-give-up mentality, ready to drive tech excellence and solve impactful challenges.

📅 Application opens: November 14, 2024
📅 Deadline: November 20, 2024, at 11:59 PM EAT

🎓 Eligibility

Open to current students from Addis Ababa University (AAU), Addis Ababa Science and Technology University (AASTU), and Adama Science and Technology University (ASTU). If you're not from these schools or have already graduated, stay tuned for future remote applications!

🔍 Requirements

- Familiarity with at least one programming language
- Experience with platforms like LeetCode or Codeforces
- Completed at least 40 problems on LeetCode or Codeforces

🤖 Selection Process

- First Round Filtering: Initial application review
- Technical & Behavioral Interviews: For selected candidates, to assess skills and fit for the program

⌛️ Don’t wait! Start your application early to ensure a standout submission. 🎯

🔗 Apply now: link

#A2SV #TechEducation #EmpoweringAfrica #ApplyNow

👆For the above question

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

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

In Java string literals (like "hello") are automatically stored in a special memory region called the string pool. When we use a string literal directly in your code, the JVM checks if that string already exists in the string pool. If it does, it reuses the same reference (i.e., the same object). If it doesn't, it adds the string to the pool.

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

What Happens When You Use new String()?
If you create a string using the new String() constructor, you explicitly create a new object in memory, even if the content of the string is the same.

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

In this case, "hello" in the string pool and the new String("hello") object are not the same object in memory, so == will return false.

🌟🚀 @AceCoding Presents! 🚀🌟

🚨 ALX Entrance Assessment Answer key! 🚨

The ALX entrance Assessment has 30-40 questions—trivial but boring. 😅

I’ve put together a FREE PDF with all the questions and answers to help you breeze through it! 📝

👉 Download the FREE PDF now!

#ALX #EntranceAssessment #TechCareer 🌍

🌟🚀 @AceCoding Presents! 🚀🌟

🚨 Exciting News 🚨
ALX Ethiopia is NOW OPEN! 🎉

Ready to kickstart your career with world-class tech training? 🚀
💰 Only $5/month ✔️
❌ $200 💸

Here are the amazing programs available to you:

🔹 ALX Pathway
🔹 Virtual Assistant
🔹 Professional Foundations
🔹 AI Career Essentials
🔹 Front-End Web Development
🔹 Back-End Web Development
🔹 AWS Cloud Computing
🔹 Salesforce Administrator
🔹 Data Science
🔹 Data Analytics

Don't miss out— Get started for only $5/month! 💥
👉 Learn More & Apply: ALX Programs
👉 Get the full ALX Entrance Assessment Answers: ALX Assessment key

#TechTraining #CareerGrowth #ALX #Ethiopia #FutureLeaders 🌍✨

🌟🚀 @AceCoding Presents! 🚀🌟

🌟 A2SV Past Interview Questions 🌟


Hey everyone! 📢 If you're preparing for an A2SV interview, here are some
common questions you might encounter. Get ready to shine! ✨

Common Questions:

1.Tell me about yourself.
2. What do you know about A2SV and why do you want to join us?
3. Describe a time when you had to step out of your comfort zone to achieve something.
4. How do you give back to your community?
5. What are your strengths and weaknesses?

Additional Questions:


Introduce yourself 👩.
What is the hardest decision you've had to make?
Tell us about a time when there was a disagreement in a group. How did you resolve it?
How did you hear about A2SV?
Are you committed to the cause?


Good luck with your preparations! You've got this. 💪😊

Feel free to reach out if you need more tips or have any questions. Let's conquer this together! 🚀👩‍💻👨‍💻



I hope this will makes you feel more prepared and confident! If there's anything more you'd like to add or adjust, just let me know in the discussion group 😊.

🟡 Medium leetcode question: 287. Find the Duplicate Number

🟢 Using Cycle sort

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]

👨‍💻 Optimized Cycle sort

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

🔴 Cycle detection Algorithm (Floyd's torties and hare / slow and fast pointer algorithm)

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)

🌟🚀 @AceCoding Presents! 🚀🌟

https://leetcode.com/problems/find-the-duplicate-number/

🔴 Cycle detection Algorithm (Floyd's torties and hare / slow and fast pointer algorithm)

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

🌟🚀 @AceCoding Presents! 🚀🌟

🟡 1561. Maximum Number of Coins You Can Get

💻 This is a very good question on Greedy Algorithm and sorting
for those who don't know Greedy is a type of Algo or technique used to solve some problems efficiently ( By being GREEDY every time 😄 that is why it's called greedy)

📊 Most Efficient Solution both in time and space complexity

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)

🌟🚀 @AceCoding Presents! 🚀🌟

https://leetcode.com/problems/maximum-number-of-coins-you-can-get/

👨‍💻 Here is a detail explanation for the above question👆

class Solution:
    def maxCoins(self, piles: List[int]) -> int:
        # first determine how many piles each person will get 
        piles_per_person = len(piles) // 3
        # sort the piles in descending order 
        piles.sort(reverse=True)
        # Hypothetically we want to give the least piles in the sorted pile for bob
        # [9,8,7,6,5,4,3,2,1] 1, 2, 3 are given for bob
        p = piles_per_person 
        score = piles[1:-p:2] # starting from the second value and increment by 2 until we reach len(piles) - piles_per_person
        return sum(score)

🌟🚀 @AceCoding Presents! 🚀🌟

https://leetcode.com/problems/maximum-number-of-coins-you-can-get/

📢 A2SV past years interview questions 📝


©️Ethio Toolkit

You have some apples and a basket that can carry up to 5000 units of weight. Given an integer array weight where weight[i] is the weight of the ith apple, 

return the maximum number of apples you can put in the basket.

Example 1:

Input: weight = [100,200,150,1000]

Output: 4

Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.

Example 2:

Input: weight = [900,950,800,1000,700,800]

Output: 5


Constraints:

1 <= weight.length <= 1000

1 <= weight[i] <= 1000

This problem is lighter version of a classic interview question: "1561. Maximum Number of Coins You Can Get" 💰which we have solved on Ace Coding.

✅ Solution: ©️Ace Coding

def maxNumberOfApples(weight):
    weight.sort()
    total_weight = 0
    count = 0

    for w in weight:
        if total_weight + w <= 5000:
            total_weight += w
            count += 1
        else:
            
    return count

🚀 @AceCoding Presents! 🚀🌟

🔔 Quick Reminder!

If you found this problem helpful, make sure to share it with your friends. Remember the saying:

If you want to go fast, go alone. If you want to go far, go together. 💪

Let’s solve these challenges together and grow as a community! 🚀

🌟🚀 @AceCoding Presents! 🚀🌟