Leetcode with dani

🌟 Day 10 Challenge: Walking Robot Simulation 🤖 🔗 Problem Link: 874. Walking Robot Simulation Hey everyone! 👋 Today, we’re solving an interesting robot movement problem where the robot moves on an infinite grid while avoiding obstacles! 🚀 --- ▎📝 Problem Statement: A robot starts at (0,0) facing north and follows a series of commands: • -2: Turn left 90° • -1: Turn right 90° • 1 ≤ k ≤ 9: Move forward k units • If the robot hits an obstacle, it stops moving in that direction but continues executing the next command. 🛑 Goal: Find the maximum squared Euclidean distance the robot reaches from the origin (0,0). 💡 Key Notes: • North → +Y • East → +X • South → -Y • West → -X --- ▎🔍 Understanding with Examples 📌 Example 1: Input: commands = [4,-1,3], obstacles = [] Output: 25 ✅ The robot moves to (3,4), and the max squared distance is 3² + 4² = 25. 📌 Example 2 (With Obstacles): Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]] Output: 65 ✅ The robot gets blocked at (2,4), then continues moving north to (1,8), reaching a max squared distance of 1² + 8² = 65. --- ▎🏗 Approach to Solve the Problem 1️⃣ Track directions efficiently: • Use dx, dy arrays to manage the direction changes when turning left or right. 2️⃣ Use a set for obstacles for quick lookup (O(1) checks). 3️⃣ Loop through commands and update position accordingly: • If moving forward → Check if the next step is an obstacle. • If turning → Update direction accordingly. --- ▎💻 Code (Python)

from typing import List

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        # Step 1: Define movement directions (North, East, South, West)
        directions = [(0,1), (1,0), (0,-1), (-1,0)]  
        x, y, max_dist, d = 0, 0, 0, 0  # Robot starts at (0,0), facing North
        
        # Step 2: Convert obstacles list into a set for quick lookups
        obstacle_set = set(map(tuple, obstacles))  

        # Step 3: Process each command
        for command in commands:
            if command == -2:  # Turn left
                d = (d - 1) % 4
            elif command == -1:  # Turn right
                d = (d + 1) % 4
            else:  # Move forward k steps
                for _ in range(command):
                    next_x, next_y = x + directions[d][0], y + directions[d][1]
                    
                    # Stop moving if an obstacle is hit
                    if (next_x, next_y) in obstacle_set:
                        break  
                    
                    x, y = next_x, next_y  # Update position
                    max_dist = max(max_dist, x*x + y*y)  # Update max distance
        
        return max_dist  # Return max squared Euclidean distance

--- ▎📝 Explanation of the Code: 1. Tracking Directions: • We use an array directions = [(0,1), (1,0), (0,-1), (-1,0)] to handle North, East, South, and West movements. • Turning left (-2) moves us backwards in the array, while turning right (-1) moves us forward. 2. Efficient Obstacle Lookup: • We store obstacles in a set (O(1) lookup) instead of a list to quickly check if a position is blocked. 3. Processing Commands: • For k steps forward, check if the next step is an obstacle: • ✅ If not blocked, update x, y. • ❌ If blocked, stop moving in that direction. • Keep track of the maximum squared Euclidean distance reached. --- ▎✅ Complexity Analysis: • Time Complexity: O(N + M), where N = len(commands), M = len(obstacles) • Space Complexity: O(M) (for storing obstacles in a set)

I really love this video! Please check it out when you have some free time and let me know what you think. watch the video

https://youtu.be/h6fcK_fRYaI?si=fdF5l_fUWXPiu_kw I really love this video! Please check it out when you have some free time and let me know what you think.

🌟 Day 10 Challenge: Find Pivot Index 🌟 🔗 Problem Link: 724. Find Pivot Index 📝 Problem Statement: Given an array of integers nums, calculate the pivot index of this array. The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right. If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array. Return the leftmost pivot index. If no such index exists, return -1. --- ▎🔍 Approach: Prefix Sum We can use a prefix sum technique to efficiently check for the pivot index. ▎Steps to Solve: 1. Compute prefix sums: We maintain a prefix sum array p, where p[i] stores the sum of elements from index 0 to i-1. 2. Iterate through the array: For each index i, check if the left sum (p[i] - nums[i-1]) equals the right sum (p[-1] - p[i]). 3. Return the first valid index: If we find an index where both sums match, return it. 4. Return -1 if no pivot index is found. --- ▎📝 Code Implementation:

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        # Step 1: Compute prefix sum
        p = [0]  # Prefix sum array initialized with 0
        for i in range(len(nums)):
            p.append(p[-1] + nums[i])  # Store cumulative sum
        
        # Step 2: Iterate through the array and check pivot condition
        for i in range(1, len(p)):
            left_sum = p[i] - nums[i - 1]  # Sum of elements to the left of index i-1
            right_sum = p[-1] - p[i]       # Sum of elements to the right of index i-1
            
            if left_sum == right_sum:
                return i - 1  # Return the pivot index
        
        return -1  # If no pivot index is found

--- ▎📝 Explanation of the Code: 1. Building Prefix Sum Array: • We initialize p with [0] to store cumulative sums. • Iterate through nums, appending the cumulative sum to p. 2. Finding Pivot Index: • For each i, compute: • Left sum: p[i] - nums[i-1] (sum of elements before index i-1). • Right sum: p[-1] - p[i] (sum of elements after index i-1). • If both sums are equal, return i-1. 3. Edge Case Handling: • If no such index exists, return -1. --- ▎✅ Complexity Analysis: • Time Complexity: O(N) (single pass for prefix sum + single pass for checking pivot index). • Space Complexity: O(N) (extra space for prefix sum array).

🌟 Day 11 Challenge: Find Pivot Index 🌟 🔗 Problem Link: 724. Find Pivot Index 📝 Problem Statement: Given an array of integers nums, calculate the pivot index of this array. The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right. If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array. Return the leftmost pivot index. If no such index exists, return -1. --- ▎🔍 Approach: Prefix Sum We can use a prefix sum technique to efficiently check for the pivot index. ▎Steps to Solve: 1. Compute prefix sums: We maintain a prefix sum array p, where p[i] stores the sum of elements from index 0 to i-1. 2. Iterate through the array: For each index i, check if the left sum (p[i] - nums[i-1]) equals the right sum (p[-1] - p[i]). 3. Return the first valid index: If we find an index where both sums match, return it. 4. Return -1 if no pivot index is found. --- ▎📝 Code Implementation:

from typing import List

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        # Step 1: Compute prefix sum
        p = [0]  # Prefix sum array initialized with 0
        for i in range(len(nums)):
            p.append(p[-1] + nums[i])  # Store cumulative sum
        
        # Step 2: Iterate through the array and check pivot condition
        for i in range(1, len(p)):
            left_sum = p[i] - nums[i - 1]  # Sum of elements to the left of index i-1
            right_sum = p[-1] - p[i]       # Sum of elements to the right of index i-1
            
            if left_sum == right_sum:
                return i - 1  # Return the pivot index
        
        return -1  # If no pivot index is found

---

▎📝 Explanation of the Code:

1. Building Prefix Sum Array:

   • We initialize p with [0] to store cumulative sums.

   • Iterate through nums, appending the cumulative sum to p.

2. Finding Pivot Index:

   • For each i, compute:

     • Left sum: p[i] - nums[i-1] (sum of elements before index i-1).

     • Right sum: p[-1] - p[i] (sum of elements after index i-1).

   • If both sums are equal, return i-1.

3. Edge Case Handling:

   • If no such index exists, return -1.

---

▎✅ Complexity Analysis:

• Time Complexity: O(N) (single pass for prefix sum + single pass for checking pivot index).

• Space Complexity: O(N) (extra space for prefix sum array).

in Short Yaman is training with a barbell that has plates of varying weights and widths. He needs to distribute these plates between the left and right sides of the barbell. The goal is to maximize the total weight lifted while ensuring that the difference in total widths between the two sides falls within a specified range [L, R]. For each test case, determine the maximum weight Yaman can lift under these conditions. If it's not possible to achieve the desired width balance, the result should be 0.

🚀 Challenge for Aspiring Weightlifters! 🏋️‍♂️ Yaman, an aspiring weightlifter, is gearing up for his next tournament and needs your help! He has n barbell plates, each with a specific weight aᵢ and width bᵢ . Yaman's goal is to distribute these plates into two subsets: one for the left side of the barbell and one for the right. His coach has defined a balancing function f(l, r) as follows: f(l, r) = (| ∑(i ∈ l) bᵢ - ∑(i ∈ r) bᵢ )| Yaman has to ensure that the absolute difference in widths between the two sides falls within a specified range during his training. ▎Your Task: For each test case, determine the maximum total weight Yaman can lift while keeping the balancing function's value within the range [L, R]. If it's impossible to achieve this balance, you should return 0 . ▎Input Format: • The first line contains the number of test cases t ( 1 ≤ t ≤ 10⁵ ). • Each test case starts with two integers n (number of plates) and q (number of tests). • The next line lists n integers representing the weights of the plates. • The following line lists n integers representing the widths of the plates. • The next q lines each contain two integers Lᵢ and Rᵢ , specifying the desired range for the balancing function. ▎Output Format: For each test, output the maximum total weight Yaman can lift while maintaining the balancing function's value within the specified range. If it's not possible, output 0 . ▎Example: Input:

1
5 4
5 2 3 2 5
1 4 9 12 20
1 2
7 7
99 100
3 3

Output:

17
12
0
14

Can you help Yaman achieve his training goals? Share your solutions and strategies! 💪 🔗 GotoCodeForce

Not an Ad!

For those who didn't see the video, the speaker challenges the old idea that just knowing how to code will guarantee you a good job. With AI becoming more popular, the tech world is changing fast. Big companies like Google, Salesforce, Meta, and Amazon are now using advanced AI tools to do tasks that used to be done by human coders, and they can do them just as well as mid-level engineers. This shift is not only changing how companies hire but also leading to job cuts in the industry. But the speaker argues that coding isn't going away. Instead, we need to think differently: we should combine our coding skills with new AI tools. He shares a simple five-step plan for developers who want to succeed in this new environment. This plan focuses on having a strong coding foundation, using AI to work more efficiently, understanding how AI works, applying these skills to real projects, and always learning as the field changes. GPT's opinion : I believe that while AI can handle many routine tasks, the creative and problem-solving parts of coding are still really important. In my opinion, coding makes up about 80% of the development process, with AI helping out with the other 20%—making things easier and taking care of repetitive work. Embracing the combination of human creativity and AI technology is essential for success in the tech world moving forward.

post questions for all of you, so please choose a question based on your experience. Make sure to understand the sliding window and prefix sum technique before attempting to solve this question,

nums = [1, 1, 2, 1, 1]
k = 3
solution = Solution()
print(solution.numberOfSubarrays(nums, k))  # Output: Number of nice subarrays

💡 Test Yourself! Feel free to ask for any further modifications or explanations!

🌟 Day 9 Challenge: Count Number of Nice Subarrays 🌟 🔗 Problem Link: Count Number of Nice Subarrays 📝 Problem Statement: Given an array of integers nums and an integer k, a continuous subarray is called nice if it contains exactly k odd numbers. Return the number of nice subarrays. ▎Two Approaches to Solve the Problem ▎Approach 1: Sliding Window Technique This approach uses a sliding window to count the number of subarrays with exactly k odd numbers.

from typing import List

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def atMostK(k):
            count = 0
            left = 0
            for right in range(len(nums)):
                if nums[right] % 2 == 1:
                    k -= 1
                while k < 0:
                    if nums[left] % 2 == 1:
                        k += 1
                    left += 1
                count += right - left + 1
            return count
        
        return atMostK(k) - atMostK(k - 1)

Explanation: 1. Function atMostK(k): This helper function counts the number of subarrays that contain at most k odd numbers. It uses a sliding window where left and right pointers define the current window. 2. Counting Subarrays: For each position of right, if the number is odd, we decrement k. If k becomes negative, we increment left until we have at most k odd numbers again. The number of valid subarrays ending at right is added to the count. 3. Final Calculation: The main function returns the difference between the counts of subarrays with at most k and k-1 odd numbers, which gives us exactly k. ▎Approach 2: Using Indices of Odd Numbers This approach tracks the indices of odd numbers directly and counts the valid subarrays based on these indices.

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        total = 0
        count_odd = 0
        l = 0
        myset = []
        
        for i in range(len(nums)):
            if nums[i] % 2:  # Check if the number is odd
                myset.append(i)  # Store the index of the odd number
                count_odd += 1
            
            if count_odd > k:
                # If we have more than k odd numbers, we need to move the left pointer
                if l:
                    l1 = (myset[l] - (myset[l - 1]))  # Distance between two odd indices
                    r = i - myset[-2]  # Distance from the second last odd index to current
                    total += l1 * r  # Count subarrays formed
                else:
                    r = i - myset[-2]
                    total += (myset[l] + 1) * r  # Count subarrays formed when l is 0
                
                l += 1  # Move the left pointer
                count_odd -= 1  # Decrease the count of odd numbers
            
        # Check for the last segment if count_odd >= k
        if count_odd >= k:
            if l:
                l1 = (myset[l] - (myset[l - 1]))
                r = (len(nums) - myset[-1])
                total += l1 * r
            else:
                r = (len(nums) - myset[-1])
                total += (myset[l] + 1) * r
        
        return total

Explanation: 1. Initialization: Similar to the first approach, we initialize variables to track counts and indices. 2. Iterate through the array: For each element, check if it’s odd and update our list of indices (myset) and counts. 3. Adjusting for excess odds: When the count exceeds k, adjust the left pointer to maintain exactly k odds and calculate valid subarrays based on distances between stored indices. 4. Final Count: After processing, check for any remaining valid segments to add to the total. ChatGPT 4 | Midjourney | Claude | Suno, [13/02/2025 17:30] ▎Complexity Analysis for Both Approaches: • Time Complexity: O(n), where n is the length of the input array. Both approaches iterate through the array a single time. • Space Complexity: O(n) in the worst case for storing indices in Approach 2. ▎Example Usage:

Sure! Here’s the formatted response for the "1588. Sum of All Odd Length Subarrays" problem: --- 🌟 Day 6 Challenge: Sum of All Odd Length Subarrays 🌟 🔗 Problem Link: Sum of All Odd Length Subarrays 📝 Problem Statement: Given an array of positive integers arr, return the sum of all possible odd-length subarrays of arr. A subarray is a contiguous subsequence of the array. ✨ Examples: • Input: arr = [1, 4, 2, 5, 3] → Output: 58 • Input: arr = [1, 2] → Output: 3 🔍 Approach: Counting Contributions Using Prefix Sums 1. Count Subarrays: For each element in the array, determine how many odd-length subarrays include that element. 2. Calculate Ranges: For an element at index i, calculate how many ways it can be included in odd-length subarrays by considering both left and right ranges. 3. Use Remainders: Count the occurrences of each remainder when dividing the prefix sums by 2 to identify odd-length contributions. 💻 Solution Code 1 :

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        left = 0
        p = [0 for i in range(len(arr)+1)]
        p[1] = arr[0]
        for i in range(1,len(arr)):
            p[i+1] = p[i] +arr[i]
        total = 0
        for i in range(1,len(p)):
            l = 0
            while l<i:
                if (i-l)%2:
                    total +=  p[i]-p[l]
                l+=1
        return total

💻 Solution Code 2 optimal:

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        total = 0
        n = len(arr)
        for i, val in enumerate(arr):
            left = i + 1          # ways to choose start position
            right = n - i         # ways to choose end position
            # Count of odd-length subarrays that include arr[i]
            odd_count = ((left + 1) // 2) * ((right + 1) // 2) + (left // 2) * (right // 2)
            total += val * odd_count
        return total

▎Example usage:

solution = Solution()
print(solution.sumOddLengthSubarrays([1, 4, 2, 5, 3]))  # Output: 58
print(solution.sumOddLengthSubarrays([1, 2]))            # Output: 3

📖 Explanation with Example: 1. For each index i, calculate how many odd-length subarrays can be formed that include arr[i]. 2. Use the counts of ways to select starting and ending positions to determine how many of those subarrays are odd-length. 3. Multiply the value of each element by its count of appearances in odd-length subarrays and sum these contributions for the final result. ⏳ Complexity Analysis: • Time Complexity: O(n) (single pass through the array). • Space Complexity: O(1) (no extra space used beyond a few variables). 💡 Test Yourself! Can you implement this solution efficiently? Dive in and share your approach with us! Let's see your coding skills shine! 🌟

🌟 Day 8 Challenge: Sum of All Odd Length Subarrays 🌟 🔗 Problem Link: Sum of All Odd Length Subarrays 📝 Problem Statement: Given an array of positive integers arr, return the sum of all possible odd-length subarrays of arr. A subarray is a contiguous subsequence of the array. ✨ Examples: • Input: arr = [1, 4, 2, 5, 3] → Output: 58 • Input: arr = [1, 2] → Output: 3 🔍 Approach: Counting Contributions Using Prefix Sums 1. Count Subarrays: For each element in the array, determine how many odd-length subarrays include that element. 2. Calculate Ranges: For an element at index i, calculate how many ways it can be included in odd-length subarrays by considering both left and right ranges. 3. Use Remainders: Count the occurrences of each remainder when dividing the prefix sums by 2 to identify odd-length contributions. code: 💻 Solution Code:

from typing import List

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        total = 0
        n = len(arr)
        for i, val in enumerate(arr):
            left = i + 1          # ways to choose start position
            right = n - i         # ways to choose end position
            # Count of odd-length subarrays that include arr[i]
            odd_count = ((left + 1) // 2) * ((right + 1) // 2) + (left // 2) * (right // 2)
            total += val * odd_count
        return total

▎Example usage:

solution = Solution()
print(solution.sumOddLengthSubarrays([1, 4, 2, 5, 3]))  # Output: 58
print(solution.sumOddLengthSubarrays([1, 2]))            # Output: 3

📖 Explanation with Example: 1. For each index i, calculate how many odd-length subarrays can be formed that include arr[i]. 2. Use the counts of ways to select starting and ending positions to determine how many of those subarrays are odd-length. 3. Multiply the value of each element by its count of appearances in odd-length subarrays and sum these contributions for the final result. ⏳ Complexity Analysis: • Time Complexity: O(n) (single pass through the array). • Space Complexity: O(1) (no extra space used beyond a few variables).