Leetcode with dani

Educational Codeforces Round 176 (rated for Div. 2) starts in ~2 hours.  Please, join by the link https://codeforces.com/contests/2075

Get ready for a LeetCode problem-solving session with Daniel Mola today at 8:00 PM (2:00 LT)! Don’t forget to share with your friends💥

Unfortunately, due to technical reasons, the round is postponed by 8.5 hours (to the usual scheduled time). We apologize for any inconvenience caused.

135. Candy Hard There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. Return the minimum number of candies you need to have to distribute the candies to the children. Example 1: Input: ratings = [1,0,2] Output: 5 Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively. Example 2: Input: ratings = [1,2,2] Output: 4 Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively. The third child gets 1 candy because it satisfies the above two conditions. Constraints: n == ratings.length 1 <= n <= 2 * 104 0 <= ratings[i] <= 2 * 104

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n  # Give every child 1 candy initially

        # Left-to-right pass: if a child has a higher rating than the left neighbor, give one more candy
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1

        # Right-to-left pass: if a child has a higher rating than the right neighbor, ensure they have more candy
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)

        return sum(candies)

i didnt know it had a simple ans; my ans is like thousand lines

135. Candy Hard There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. Return the minimum number of candies you need to have to distribute the candies to the children. Example 1: Input: ratings = [1,0,2] Output: 5 Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively. Example 2: Input: ratings = [1,2,2] Output: 4 Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively. The third child gets 1 candy because it satisfies the above two conditions. Constraints: n == ratings.length 1 <= n <= 2 * 104 0 <= ratings[i] <= 2 * 104

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n  # Give every child 1 candy initially

        # Left-to-right pass: if a child has a higher rating than the left neighbor, give one more candy
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1

        # Right-to-left pass: if a child has a higher rating than the right neighbor, ensure they have more candy
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)

        return sum(candies)

i didnt know it had a simple ans my ans was like thousands line

135. Candy Hard There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. Return the minimum number of candies you need to have to distribute the candies to the children. Example 1: Input: ratings = [1,0,2] Output: 5 Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively. Example 2: Input: ratings = [1,2,2] Output: 4 Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively. The third child gets 1 candy because it satisfies the above two conditions. Constraints: n == ratings.length 1 <= n <= 2 * 104 0 <= ratings[i] <= 2 * 104

class Solution:
    def candy(self, ratings: List[int]) -> int:
        total = 0
        count = 0
        i=0
        ratings.append(ratings[-1])
        cond = True
        maxm = 0
        while i<len(ratings)-1:
            while i<len(ratings)-1 and ratings[i] > ratings[i+1]:             
                if cond or count:
                    total+= 1+count
                    count+=1
                i+=1
                if count==maxm:
                    count+=1
                    total+=1
                cond = True
            count = 0
            maxm = 0
            while i<len(ratings)-1 and ratings[i] < ratings[i+1]:
                total+= 1+count
                count+=1
                i+=1
                cond = False
                maxm +=1
            while i<len(ratings)-1 and  ratings[i] == ratings[i+1]:
                cond = True
                i+=1
                maxm = 0
            
            count=0
        return len(ratings)+total-1

330. Patching Array Difficulty: Hard Problem Statement: Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] (inclusive) can be formed by the sum of some elements in the array. Return the minimum number of patches required. Example 1: Input: nums = [1, 3], n = 6 Output: 1 Explanation: The combinations of nums are [1], [3], [1, 3], which form possible sums of 1, 3, 4. Now if we add/patch 2 to nums, the combinations become [1], [2], [3], [1, 3], [2, 3], [1, 2, 3], covering all sums 1, 2, 3, 4, 5, 6. Thus, only 1 patch is needed. Example 2: Input: nums = [1, 5, 10], n = 20 Output: 2 Explanation: The two patches can be [2, 4]. Example 3: Input: nums = [1, 2, 2], n = 5 Output: 0 Constraints: 1 <= nums.length <= 1000 1 <= nums[i] <= 10^4 nums is sorted in ascending order. 1 <= n <= 2^31 - 1 Solution :

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        patches = 0
        miss = 1
        i = 0
        while miss <= n:
            if i < len(nums) and nums[i] <= miss:
                miss += nums[i]
                i += 1
            else:
                miss += miss
                patches += 1
        return patches

Hey everyone! This week, we have a special IS Talks session you won’t want to miss! 🎯 Join us for a LeetCode Problem-Solving Session with Daniel Mola (a.k.a. LeetCode with Dani). Daniel is a 3rd-year Information Systems student and the mind behind the popular LeetCode with Dani Telegram channel. 📅 Monday ⏰ 8:00 PM (2:00 LT) Come sharpen your problem-solving skills and learn from one of the best! See you there! 💡🔥

Codeforces Round #1010 (Div. 1, Div. 2) will take place on the 15th of March at 05:35 UTC. Please, join by the link https://codeforces.com/contests/2081,2082?locale=en

let me share one conversation with GPT if i want to apply to FAANG what should i excpected to know ChatGPT said: If you want to apply to FAANG (Facebook/Meta, Amazon, Apple, Netflix, Google), you need to be well-prepared in multiple technical and non-technical areas. Here’s a breakdown of what you should know: 1. Data Structures & Algorithms (DSA) – High Priority You should be able to solve LeetCode Hard problems efficiently. Focus on: ✅ Arrays, Strings, Linked Lists ✅ Trees (Binary, BST, Trie) ✅ Graphs (BFS, DFS, Dijkstra’s) ✅ Dynamic Programming ✅ Backtracking ✅ Bit Manipulation ✅ Heaps & Priority Queues ✅ Two Pointers, Sliding Window, Prefix Sum 🔥 Recommended Resources: LeetCode (Top 150 FAANG problems) Codeforces (Div2 & Div1 contests) NeetCode, Striver’s SDE Sheet Cracking the Coding Interview by Gayle Laakmann McDowell 2. System Design (For Senior Roles) FAANG interviews often test system design for mid/senior positions. You should know: ✅ Scalability (Load Balancing, Sharding, Caching) ✅ Microservices & Distributed Systems ✅ Databases (SQL & NoSQL) ✅ API Design, Rate Limiting, Consistency Models ✅ Message Queues (Kafka, RabbitMQ) ✅ CAP Theorem 🔥 Resources: "Designing Data-Intensive Applications" by Martin Kleppmann System Design Primer (GitHub) Grokking the System Design Interview 3. Object-Oriented Design (OOD) & Design Patterns ✅ SOLID Principles ✅ Factory, Singleton, Observer, Decorator, Strategy Patterns 🔥 Resources: Head First Design Patterns Grokking the Object-Oriented Design Interview 4. Low-Level Programming & Optimization (For Performance-Critical Roles) ✅ Memory Management (Heap vs Stack) ✅ Threading & Concurrency ✅ Cache Optimization ✅ Assembly & Compiler Optimizations 5. Core CS Concepts ✅ Operating Systems (Processes, Threads, Deadlocks, Virtual Memory) ✅ Networking (TCP/IP, HTTP, Load Balancing, CDN) ✅ Databases (Indexes, ACID, Transactions, Query Optimization) 🔥 Resources: Computer Networking: A Top-Down Approach Database System Concepts 6. Behavioral Interviews – Don't Ignore This! FAANG uses STAR (Situation, Task, Action, Result) format for behavioral questions. ✅ Leadership & Ownership ✅ Conflict Resolution ✅ Past Projects & Impact 🔥 Resources: "The Amazon Leadership Principles" "Decode & Conquer" by Lewis Lin 7. Programming Languages & Tech Stack You should be fluent in at least one high-level language, such as: Java, Python, C++, JavaScript, Go (most used in FAANG) Knowledge of React, Node.js, Spring Boot, Django is a plus 8. Mock Interviews & Time Management Start practicing mock interviews with peers or platforms like: ✅ Pramp ✅ Interviewing.io ✅ Leetcode Contest + Codeforces

▎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