check this in ur free time

🌟 Day 7 Challenge 1: Subarray Sums Divisible by K 🌟

🔗 Problem Link: Subarray Sums Divisible by K

📝 Problem Statement:
Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k. A subarray is a contiguous part of an array.

✨ Examples:

• Input: nums = [4, 5, 0, -2, -3, 1], k = 5 → Output: 7

• Input: nums = [5], k = 9 → Output: 0

🔍 Approach: Prefix Sum with Remainder Counting

1. Use a prefix sum to keep track of the cumulative sum of elements as you iterate through the array.

2. Calculate the remainder of the prefix sum when divided by k. If two prefix sums have the same remainder, the subarray between those indices has a sum divisible by k.

3. Utilize a hash map (or dictionary) to count occurrences of each remainder, allowing you to efficiently determine how many valid subarrays end at each position.

💻 Solution Code:

from collections import defaultdict

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        prefix_counts = defaultdict(int)
        prefix_counts[0] = 1  # Initialize with prefix sum 0 having remainder 0
        current_sum = 0
        result = 0
        
        for num in nums:
            current_sum += num
            mod = current_sum % k
            result += prefix_counts[mod]
            prefix_counts[mod] += 1
        
        return result

▎Example usage:

solution = Solution()
print(solution.subarraysDivByK([4, 5, 0, -2, -3, 1], 5)) # Output: 7
print(solution.subarraysDivByK([5], 9)) # Output: 0

📖 Explanation with Example:

1. As you iterate through the array, maintain a running total (current_sum) and calculate its remainder when divided by k.

2. For each element, check how many times this remainder has been seen before using the hash map. Each occurrence corresponds to a valid subarray.

3. Update the hash map with the current remainder count for future subarray calculations.

⏳ Complexity Analysis:

• Time Complexity: O(n) (single pass through the array).

• Space Complexity: O(k) (to store counts of remainders).

💡 Test Yourself!
Can you solve this problem efficiently?

🌟 Day 7 Challenge: Minimum Size Subarray Sum 🌟

🔗 Problem Link: Minimum Size Subarray Sum

📝 Problem Statement:
Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

✨ Examples:

• Input: target = 7, nums = [2,3,1,2,4,3] → Output: 2
Explanation: The subarray [4,3] has the minimal length.

• Input: target = 4, nums = [1,4,4] → Output: 1

• Input: target = 11, nums = [1,1,1,1,1,1,1,1] → Output: 0

🔍 Approach 1: O(n) Sliding Window

This method uses two pointers to form a window and expands or shrinks it based on the current sum:

1. Initialize: Set two pointers (left, right), a running sum (curr_sum), and a variable (min_len) initialized to infinity.


2. Expand: Move the right pointer to add elements to curr_sum.

3. Shrink: Once curr_sum meets or exceeds the target, update min_len and shrink the window from the left until the sum is less than the target.

4. Return: If a valid subarray is found, return its length; otherwise, return 0.

💻 Solution Code:

def minSubArrayLen(target, nums):
    n = len(nums)
    left = 0
    curr_sum = 0
    min_len = float('inf')
    
    for right in range(n):
        curr_sum += nums[right]
        while curr_sum >= target:
            min_len = min(min_len, right - left + 1)
            curr_sum -= nums[left]
            left += 1
    
    return min_len if min_len != float('inf') else 0

# Testing the sliding window approach:
print(minSubArrayLen(7, [2, 3, 1, 2, 4, 3]))  # Expected Output: 2
print(minSubArrayLen(4, [1, 4, 4]))           # Expected Output: 1
print(minSubArrayLen(11, [1, 1, 1, 1, 1, 1, 1, 1]))  # Expected Output: 0

🔍 Approach 2: O(n log n) Prefix Sum with Binary Search

This method involves creating a prefix sum array and using binary search to find the smallest index where the difference in prefix sums is at least the target.

1. Prefix Sum Array: Create an array such that prefix[i+1] = prefix[i] + nums[i] with prefix[0] = 0.

2. Binary Search: For each index i, compute the required bound (prefix[i] + target) and use binary search to find the smallest index j where prefix[j] is at least that bound.

3. Update Answer: Calculate the subarray length as j - i and update the minimal length.

4. Return: Return the minimum length found, or 0 if no valid subarray exists.

💻 Solution Code:

def minSubArrayLenBinarySearch(target, nums):
    n = len(nums)
    # Build prefix sum array
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    
    min_len = float('inf')
    # Iterate over prefix sum array
    for i in range(n):
        bound = prefix[i] + target
        # Find the minimal j such that prefix[j] >= bound
        j = bisect.bisect_left(prefix, bound)
        if j <= n:
            min_len = min(min_len, j - i)
    
    return min_len if min_len != float('inf') else 0

# Testing the O(n log n) approach:
print(minSubArrayLenBinarySearch(7, [2, 3, 1, 2, 4, 3]))  # Expected Output: 2
print(minSubArrayLenBinarySearch(4, [1, 4, 4]))           # Expected Output: 1
print(minSubArrayLenBinarySearch(11, [1, 1, 1, 1, 1, 1, 1, 1]))  # Expected Output: 0

📖 Explanation with Example:

• In the Sliding Window approach, we continuously expand our window by moving the right pointer and check if we can shrink it from the left side once we reach or exceed the target sum.


• In the Prefix Sum with Binary Search approach, we precompute cumulative sums and use binary search to efficiently find valid subarrays.

⏳ Complexity Analysis:

• Sliding Window:

• Time Complexity: O(n) (single pass through the array).

• Space Complexity: O(1) (only a few variables used).

• Prefix Sum with Binary Search:

• Time Complexity: O(n log n) (due to binary search).

🌟 Day 8 Challenge 1: Sum of All Odd Length Subarrays 🌟 Difficulty :Easy

🔗 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 9 Challenge: Count Number of Nice Subarrays 🌟

🔗 Problem Link: Count Number of Nice Subarrays Difficulty: Medium

📝 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.

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.


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

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!

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,

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.

Not an Ad!

🚀 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

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.

🌟 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:

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

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

🌟 Day 11 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)

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 added new books check it