Leetcode with dani

▎678. Valid Parenthesis String 💻 Difficulty: Medium Given a string s containing only three types of characters: '(', ')', and '*', return true if s is valid. ▎Rules for a valid string: ✅ Any left parenthesis '(' must have a corresponding right parenthesis ')'. ✅ Any right parenthesis ')' must have a corresponding left parenthesis '('. ✅ Left parenthesis '(' must go before the corresponding right parenthesis ')'. ✅ '*' can be treated as '(', ')', or an empty string "". ▎Examples Example 1: Input: s = "()" Output: true Example 2: Input: s = "(*)" Output: true Example 3: Input: s = "(*))" Output: true ▎Constraints: • 1 <= s.length <= 100 • s[i] is '(', ')', or '*'. --- ▎Solution (Greedy Approach)

def checkValidString(s: str) -> bool:
    low = high = 0  # low: min open count, high: max open count
    
    for char in s:
        if char == '(':
            low += 1
            high += 1
        elif char == ')':
            low = max(0, low - 1)  # Decrease open count but not below zero
            high -= 1
        else:  # '*'
            low = max(0, low - 1)  # Treat '*' as ')'
            high += 1  # Treat '*' as '('
        
        if high < 0:  # Too many ')', invalid
            return False
    
    return low == 0  # If low is zero, valid parentheses

# Test cases
print(checkValidString("()"))     # True
print(checkValidString("(*)"))    # True
print(checkValidString("(*))"))   # True

▎Explanation

We keep track of the possible range of open parentheses using low and high:  

• low (minimum open count) decreases when ')' appears but never goes below 0.  

• high (maximum open count) increases when '(' or '*' (treated as '(') appears.  

• If high becomes negative at any point, the string is invalid.  

• Finally, if low == 0, the string is valid.  

🚀 Time Complexity: O(n)  
🔹 Space Complexity: O(1)

Codeforces Round 1009 (Div. 3) will take place on the 11th of March at 14:35 UTC.  Please, join by the link https://codeforces.com/contests/2074?locale=en

Just a motivation 😄

Codeforces Round #1008 (Div. 1, Div. 2) will take place on the 10th of March at 14:35 UTC. Please, join by the link https://codeforces.com/contests/2077,2078?locale=en

▎2366. Minimum Replacements to Sort the Array Difficulty: Hard You are given a 0-indexed integer array nums. In one operation, you can replace any element of the array with any two elements that sum to it. For example, if nums = [5, 6, 7], you can replace nums[1] (which is 6) with two numbers, say 2 and 4, since 2 + 4 = 6. This transforms the array into [5, 2, 4, 7]. Return the minimum number of operations required to make the array sorted in non-decreasing order. ▎Examples Example 1:

Input: nums = [3, 9, 3]
Output: 2
Explanation:
- Operation 1: Replace 9 with [3, 6] → Array becomes [3, 3, 6, 3]
- Operation 2: Replace 6 with [3, 3] → Array becomes [3, 3, 3, 3, 3]
Thus, a total of 2 operations are required.

Example 2:

Input: nums = [1, 2, 3, 4, 5]
Output: 0
Explanation: 
The array is already in non-decreasing order. Therefore, no operations are needed.

▎Constraints

• 1 ≤ nums.length ≤ 10⁵

• 1 ≤ nums[i] ≤ 10⁹

▎Solution Code

class Solution:
    def minimumReplacement(self, nums: List[int]) -> int:
        operations = 0
        n = len(nums)
        
        # Start from the second last element and move backward
        for i in range(n - 2, -1, -1):
            if nums[i] > nums[i + 1]:
                # Calculate how many parts we need to break nums[i] into
                parts = (nums[i] + nums[i + 1] - 1) // nums[i + 1]
                operations += parts - 1
                
                # Set nums[i] to the maximum value allowed
                nums[i] = nums[i] // parts
        
        return operations

▎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 😋