▎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

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

Just a motivation 😄

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

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

let me share one conversation with GPT
if i want to apply to FAANG what should i expect 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

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

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

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

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

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

A big thank you to everyone at this channel and  Alpha ,for a great session! I really enjoyed it.

For Ethiopians only

Here is our very first leetcode Tree problem (BFS). Answer will be posted at 6:00 PM

102. Binary Tree Level Order Traversal

Difficulty: Medium

▎Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level).

▎Examples

Example 1:

• Input: root = [3,9,20,null,null,15,7]

• Output: [[3],[9,20],[15,7]]

Example 2:

• Input: root = [1]

• Output: [[1]]

Example 3:

• Input: root = []

• Output: []

▎Constraints

• The number of nodes in the tree is in the range [0, 2000].

• -1000 <= Node.val <= 1000

When u create a CV take this as model