Leetcode with dani

▎860. Lemonade Change Difficulty: Easy At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by the array bills). Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5. Note that you do not have any change in hand at first. ▎Problem Statement Given an integer array bills where bills[i] is the bill the i-th customer pays, return true if you can provide every customer with the correct change, or false otherwise. ▎Examples Example 1:

Input: bills = [5, 5, 5, 10, 20]
Output: true
Explanation:
- From the first 3 customers, we collect three $5 bills.
- From the fourth customer, we collect a $10 bill and give back a $5.
- From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

Example 2:

Input: bills = [5, 5, 10, 10, 20]
Output: false
Explanation:
- From the first two customers, we collect two $5 bills.
- For the next two customers, we collect a $10 bill and give back a $5 bill.
- For the last customer, we cannot give the change of $15 back because we only have two $10 bills.
Since not every customer received the correct change, the answer is false.

▎Constraints

• 1 ≤ bills.length ≤ 10⁵

• bills[i] is either 5, 10, or 20.

▎Solution Code

from typing import List

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        c5 = 0  # Count of $5 bills
        c10 = 0 # Count of $10 bills
        
        for i in bills:
            if i == 5:
                c5 += 1
            elif i == 10:
                c10 += 1
                c5 -= 1
            else: # i == 20
                if c10 > 0:
                    c10 -= 1
                    c5 -= 1
                else:
                    c5 -= 3
            
            # Check if we have enough $5 bills to give change
            if c5 < 0:
                return False
        
        return True

976. Largest Perimeter Triangle Easy Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0. Example 1: vbnet Copy Edit Input: nums = [2,1,2] Output: 5 Explanation: You can form a triangle with three side lengths: 1, 2, and 2. Example 2: vbnet Copy Edit Input: nums = [1,2,1,10] Output: 0 Explanation: - You cannot use the side lengths 1, 1, and 2 to form a triangle. - You cannot use the side lengths 1, 1, and 10 to form a triangle. - You cannot use the side lengths 1, 2, and 10 to form a triangle. As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

▎976. Largest Perimeter Triangle

Difficulty: Easy

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

▎Example 1:

Input: 

nums = [2, 1, 2]

Output: 

5

Explanation: You can form a triangle with three side lengths: 1, 2, and 2.

▎Example 2:

Input: 

nums = [1, 2, 1, 10]

Output: 

0

Explanation:

• You cannot use the side lengths 1, 1, and 2 to form a triangle.

• You cannot use the side lengths 1, 1, and 10 to form a triangle.

• You cannot use the side lengths 1, 2, and 10 to form a triangle.

As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

▎Approach

To solve this problem, we can follow these steps:

1. Sort the Array: Start by sorting the array in non-decreasing order.

2. Check Triplets: Iterate through the sorted array from the end to the beginning and check for valid triplets that can form a triangle using the Triangle Inequality Theorem.

3. Return the Perimeter: If a valid triplet is found, calculate and return their perimeter. If no valid triplet is found, return 0.

▎Implementation

Here’s a Python implementation of the approach:

def largestPerimeter(nums):
    # Sort the array in non-decreasing order
    nums.sort()
    
    # Iterate from the end of the sorted list to find a valid triangle
    for i in range(len(nums) - 1, 1, -1):
        # Check if nums[i-2], nums[i-1], nums[i] can form a triangle
        if nums[i - 2] + nums[i - 1] > nums[i]:
            # If they can, return their perimeter
            return nums[i - 2] + nums[i - 1] + nums[i]
    
    # If no valid triangle is found, return 0
    return 0

# Example usage:
print(largestPerimeter([2, 1, 2]))  # Output: 5
print(largestPerimeter([1, 2, 1, 10]))  # Output: 0

▎Conclusion

This solution efficiently finds the largest perimeter of a triangle that can be formed from three lengths in the given array. If no such triangle exists, it correctly returns 0.

▎Greedy Algorithm Problems ▎Easy LeetCode Easy Problems Join our Telegram Channel 1. 455. Assign Cookies 2. 860. Lemonade Change 3. 1217. Minimum Cost to Move Chips to The Same Position 4. 1005. Maximize Sum Of Array After K Negations 5. 1221. Split a String in Balanced Strings 6. 605. Can Place Flowers 7. 680. Valid Palindrome II ▎Medium LeetCode Medium Problems Join our Telegram Channel 8. 55. Jump Game 9. 45. Jump Game II 10. 134. Gas Station 11. 376. Wiggle Subsequence 12. 402. Remove K Digits 13. 435. Non-overlapping Intervals 14. 452. Minimum Number of Arrows to Burst Balloons 15. 621. Task Scheduler 16. 678. Valid Parenthesis String 17. 763. Partition Labels 18. 767. Reorganize String 19. 122. Best Time to Buy and Sell Stock II 20. 406. Queue Reconstruction by Height 21. 738. Monotone Increasing Digits 22. 984. String Without AAA or BBB 23. 1405. Longest Happy String 24. 1564. Put Boxes Into the Warehouse I ▎Hard LeetCode Hard Problems Join our Telegram Channel 25. 135. Candy 26. 330. Patching Array 27. 502. IPO 28. 757. Set Intersection Size At Least Two 29. 871. Minimum Number of Refueling Stops 30. 968. Binary Tree Cameras 31. 1235. Maximum Profit in Job Scheduling 32. 1642. Furthest Building You Can Reach 33. 1792. Maximum Average Pass Ratio 34. 1943. Describe the Painting ▎Resources • A2SV • Join our Telegram Channel

XIX Open Olympiad in Informatics - Final Stage, Day 1 (Unrated, Online Mirror, IOI rules) will take place on the 7th of March at 08:05 UTC. Please, join by the link https://codeforces.com/contests/2079

UNRATED

solution

class Solution:
    def minMoves(self, target: int, maxDoubles: int) -> int:
        count = 0
        while target>1 and maxDoubles>0:
            if target%2:
                count+=1
            target = target//2
            maxDoubles-=1
            count += 1
        count += target -1
        return count

🔹 2139. Minimum Moves to Reach Target Score 🟠 Medium | 📌 Topics: Greedy, Math 😋 Problem Statement: You are playing a game with integers. You start with 1 and want to reach target. You can perform two types of moves: ✅ Increment: Add 1 → x = x + 1 (Unlimited) ✅ Double: Multiply by 2 → x = 2 * x (At most maxDoubles times) Return the minimum number of moves needed to reach target starting from 1. 🔹 Examples: 🔹 Example 1: 🔹 Input: target = 5, maxDoubles = 0 🔹 Output: 4 🔹 Explanation: Only incrementing: 1 → 2 → 3 → 4 → 5 🔹 Example 2: 🔹 Input: target = 19, maxDoubles = 2 🔹 Output: 7 🔹 Explanation: 1 → 2 → 3 → 4 → 8 → 9 → 18 → 19 🔹 Example 3: 🔹 Input: target = 10, maxDoubles = 4 🔹 Output: 4 🔹 Explanation: 1 → 2 → 4 → 5 → 10 🔹 Constraints: ✔️ 1 ≤ target ≤ 10⁹ ✔️ 0 ≤ maxDoubles ≤ 100 Link

u can submit in this website for those who dont have https://neetcode.io/problems/meeting-schedule-ii

🔥 Premium Question: Meeting Rooms II 🔥 Find the minimum number of days required to schedule all meetings without conflicts. 🔗 Problem Link ▎Problem Statement: Given an array of meeting time interval objects consisting of start and end times [[start_1, end_1], [start_2, end_2], ...] (where start_i < end_i), determine the minimum number of days required to schedule all meetings without any overlaps. ▎Example 1: 🔹 Input: intervals = [(0, 40), (5, 10), (15, 20)] 🔹 Output: 2 🔹 Explanation: • Day 1: (0, 40) • Day 2: (5, 10), (15, 20) ▎Example 2: 🔹 Input: intervals = [(4, 9)] 🔹 Output: 1 ✅ Note: • (0, 8), (8, 10) is not considered a conflict at 8. ▎Constraints: • 0 <= intervals.length <= 500 • 0 <= intervals[i].start < intervals[i].end <= 1,000,000 💬 Drop your solutions in the comments! 🚀

do u like this type of questions 😋

this is an interesting question , try it after that u can see my solution here

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        maxReach = 0
        for i, jump in enumerate(nums):
            if i > maxReach:
                return False
            maxReach = max(maxReach, i + jump)
            if maxReach >= len(nums) - 1:
                return True
        return False

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        last = len(nums)-1
        for i in range(len(nums)-2,-1,-1):
            if nums[i]+i >= last:
                last = i
        return nums[0] >= last

▎Problem: 462. Minimum Moves to Equal Array Elements II Difficulty: Medium Topics: Array, Greedy, Median Companies: [Google, Facebook, Microsoft] ▎Problem Description Given an integer array nums of size n , return the minimum number of moves required to make all array elements equal. In one move, you can increment or decrement an element of the array by 1. Note: Test cases are designed so that the answer will fit in a 32-bit integer. ▎Examples Example 1: Input:

nums = [1, 2, 3]

Output:

2

Explanation:
Only two moves are needed (each move increments or decrements one element):

• Step 1: [1, 2, 3] => [2, 2, 3]

• Step 2: [2, 2, 3] => [2, 2, 2]

---

Example 2:

Input:

nums = [1, 10, 2, 9]

Output:

16

▎Constraints

•  n = nums.length 

•  1 ≤ n ≤ 10⁵ 

•  -10⁹ ≤ nums[i] ≤ 10⁹ 

▎Explanation

To minimize the number of moves, you want to choose a target value that minimizes the sum of the absolute differences between each element and that target. It can be proven that the best target value is the median of the array.

If the array is sorted, the median minimizes the sum of absolute deviations. Thus, the minimum number of moves is given by:

moves = ∑ᵢ₌₀ⁿ⁻¹ | nums[i] - median |

▎Sample Python Implementation

def minMoves2(nums):
    # Sort the array to find the median.
    nums.sort()
    n = len(nums)
    median = nums[n // 2]  # Get the median value
    
    # Compute the total moves as the sum of absolute differences.
    moves = sum(abs(num - median) for num in nums)
    return moves

# Example usage:
nums1 = [1, 2, 3]
print(minMoves2(nums1))  # Output: 2

nums2 = [1, 10, 2, 9]
print(minMoves2(nums2))  # Output: 16

This implementation efficiently calculates the minimum number of moves required to make all elements in the array equal by leveraging the properties of the median. The sorting step ensures we can easily access the median value for our calculations.

▎Problem: 453. Minimum Moves to Equal Array Elements Difficulty: Medium Topics: Array, Greedy, Mathematics ▎Problem Description Given an integer array nums of size n , return the minimum number of moves required to make all array elements equal. In one move, you can increment n - 1 elements of the array by 1. ▎Examples Example 1: Input:

nums = [1, 2, 3]

Output:

3

Explanation: Only three moves are needed (remember each move increments two elements): • Step 1: [1, 2, 3] => [2, 3, 3] • Step 2: [2, 3, 3] => [3, 4, 3] • Step 3: [3, 4, 3] => [4, 4, 4] --- Example 2: Input:

nums = [1, 1, 1]

Output:

0

▎Constraints • n = nums.length • 1 ≤ n ≤ 10⁵ • -10⁹ ≤ nums[i] ≤ 10⁹ The answer is guaranteed to fit in a 32-bit integer. ▎Explanation The key insight is to realize that incrementing n - 1 elements by 1 is equivalent to decrementing a single element by 1. Therefore, the problem can be reinterpreted as finding the total number of decrement operations required to make all elements equal to the minimum element in the array. This is because each move essentially reduces the difference between an element and the minimum value. If minVal is the minimum value in nums, then the number of moves is given by:

moves = ∑ᵢ₌₀ⁿ⁻¹ (nums[i] - minVal)

▎Sample Python Implementation

def minMoves(nums):
    # Find the minimum value in the array.
    minVal = min(nums)
    # Compute the total number of moves required.
    moves = sum(num - minVal for num in nums)
    return moves

# Example usage:
nums = [1, 2, 3]
print(minMoves(nums))  # Output: 3

For more answers and solutions, visit LeetCode.

For more answers and solutions, visit LeetCode.

Problem: 2602. Minimum Operations to Make All Array Elements Equal Difficulty: Medium Topics: Array, Sorting, Binary Search, Prefix Sum ▎Problem Description You are given an array nums consisting of positive integers. You are also given an integer array queries of size m. For the ith query, you want to make all the elements of nums equal to queries[i]. You can perform the following operation on the array any number of times: Operation: Increase or decrease an element of the array by 1. Return an array answer of size m where answer[i] is the minimum number of operations required to make all elements of nums equal to queries[i]. Note: After each query, the array is reset to its original state. ▎Examples Example 1: Input:

nums = [3, 1, 6, 8]
queries = [1, 5]

Output:

[14, 10]

Explanation:

• For the first query (q = 1):

    • Decrease nums[0] 2 times: from 3 to 1.

    • Decrease nums[2] 5 times: from 6 to 1.

    • Decrease nums[3] 7 times: from 8 to 1.

    • Total operations = 2 + 5 + 7 = 14.

• For the second query (q = 5):

    • Increase nums[0] 2 times: from 3 to 5.

    • Increase nums[1] 4 times: from 1 to 5.

    • Decrease nums[2] 1 time: from 6 to 5.

    • Decrease nums[3] 3 times: from 8 to 5.

    • Total operations = 2 + 4 + 1 + 3 = 10.

---

Example 2:

Input:

nums = [2, 9, 6, 3]
queries = [10]

Output:

[20]

Explanation:

• Increase each element in the array to 10:

    • Operations for each element: 

        • 8 (from 2 to 10),

        • 1 (from 9 to 10),

        • 4 (from 6 to 10),

        • 7 (from 3 to 10).

    • Total operations = 8 + 1 + 4 + 7 = 20.

▎Constraints

• n = nums.length

• m = queries.length

• 1 ≤ n, m ≤ 10⁵

• 1 ≤ nums[i], queries[i] ≤ 10⁹

---

What is the object-oriented method to get rich? Inherit it! 😂😂"