#leet_code_Q15 #Q_209 #Medium #Sliding_window
209. Minimum Size Subarray Sum
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.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:

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

Constraints:

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

out of topic
You are in a room with three light switches. Each switch controls one of three light bulbs in an adjacent room, but you do not know which switch controls which bulb. You can only go into the room once to check the state of the bulbs. How can you determine which switch controls which bulb?

Solution:

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        minm = len(nums) + 1
        left = 0
        tot = 0
        
        for i in range(len(nums)):
            tot += nums[i]
            while tot >= target:
                minm = min(minm, i - left + 1)
                tot -= nums[left]
                left += 1
        
        if minm > len(nums):
            return 0
        return minm

Explanation:
Initialize Variables:

minm is initialized to a value greater than the length of nums to ensure any valid subarray length found will be smaller.
left is the starting index of the current subarray.
tot is the sum of the current subarray.
Iterate Through nums:

Add each element to tot as we iterate through the array with index i.
Adjust left Pointer:

If tot is greater than or equal to target, adjust the left pointer to find the minimal subarray length.
Continuously subtract the value at nums[left] from tot and increment left until tot is less than target.
During this process, update minm with the length of the current valid subarray if it's smaller than the previously recorded minm.
Return Result:

If no valid subarray is found, minm will remain greater than len(nums) and the function will return 0.
Otherwise, it returns the minimal length of the subarray.
This approach ensures an efficient solution with a time complexity of O(n), where n is the length of the input array nums. The sliding window technique optimally finds the minimal subarray length in a single pass through the array.

The behavior difference between mutable objects (like lists) and immutable objects (like integers) in Python explains why changing the value of a variable affects another variable when dealing with arrays (lists) but not when dealing with integers.

Mutable vs. Immutable Objects
Mutable objects: These can be changed in place. Examples include lists, dictionaries, and sets.
Immutable objects: These cannot be changed in place. Examples include integers, strings, and tuples.
Immutable Example (Integers)
When you assign an integer to another variable, Python creates a new reference to the integer object. Since integers are immutable, changing the value of one variable does not affect the other.

a = 10
b = a  # b now references the same integer object as a
b = 20  # b now references a new integer object
print(a)  # output: 10
print(b)  # output: 20

In this example, when b is assigned the value 20, it does not change the value of a because integers are immutable. Assigning 20 to b makes b reference a new integer object.

Mutable Example (Lists)
When you assign a list to another variable, both variables reference the same list object. Since lists are mutable, changes made through one variable are reflected in the other.

a = [1, 2, 3]
b = a  # b now references the same list as a
b[0] = 99  # modify the first element of the list referenced by b
print(a)  # output: [99, 2, 3]
print(b)  # output: [99, 2, 3]

In this example, both a and b reference the same list object. Changing the list through b affects the list referenced by a because lists are mutable.

Why This Happens
Immutable objects: Variables referencing immutable objects (like integers) create a new reference when reassigned.
Mutable objects: Variables referencing mutable objects (like lists) point to the same object unless explicitly copied.

ከመሞት ባተርፋት
ሀገሬን ጫኑልኝ ይዣት እጠፋለሁ ልባችሁ ሲረጋ
ቀልባችሁ ሲሰክን፣ እምልሳታለሁ።

Prefix Sum Array – Implementation and Applications in Competitive Programming

Given an array arr[] of size N, find the prefix sum of the array. A prefix sum array is another array prefixSum[] of the same size, such that the value of prefixSum[i] is arr[0] + arr[1] + arr[2] . . . arr[i].

Examples:
Input: arr[] = {10, 20, 10, 5, 15}
Output: prefixSum[] = {10, 30, 40, 45, 60}
Explanation: While traversing the array, update the element by adding it with its previous element.
prefixSum[0] = 10,
prefixSum[1] = prefixSum[0] + arr[1] = 30,
prefixSum[2] = prefixSum[1] + arr[2] = 40 and so on.

write your answer in the group or send it with the bot i will review it.

Answer:

def prefix_sum(arr):
    prefix_sum_arr = [0] * len(arr)
    prefix_sum_arr[0] = arr[0]
    for i in range(1, len(arr)):
        prefix_sum_arr[i] = prefix_sum_arr[i - 1] + arr[i]
    return prefix_sum_arr

arr = [10, 20, 10, 5, 15]
result = prefix_sum(arr)
print(result)  # Output: [10, 30, 40, 45, 60]

#leet_codeQ16 #Q_209 #Easy #Prefix_sum
1991. Find the Middle Index in Array

Hint
Given a 0-indexed integer array nums, find the leftmost middleIndex (i.e., the smallest amongst all the possible ones).

A middleIndex is an index where nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1].

If middleIndex == 0, the left side sum is considered to be 0. Similarly, if middleIndex == nums.length - 1, the right side sum is considered to be 0.

Return the leftmost middleIndex that satisfies the condition, or -1 if there is no such index.



Example 1:

Input: nums = [2,3,-1,8,4]
Output: 3
Explanation: The sum of the numbers before index 3 is: 2 + 3 + -1 = 4
The sum of the numbers after index 3 is: 4 = 4
Example 2:

Input: nums = [1,-1,4]
Output: 2
Explanation: The sum of the numbers before index 2 is: 1 + -1 = 0
The sum of the numbers after index 2 is: 0
Example 3:

Input: nums = [2,5]
Output: -1
Explanation: There is no valid middleIndex.


Constraints:

1 <= nums.length <= 100
-1000 <= nums[i] <= 1000

Mean of range in array
#Q17 Geeks for Geeks
Given an array of n integers and q queries. Write a program to find floor value of mean in range l to r for each query in a new line.
Queries are given by an array queries[] of size 2*q. Here queries[2*i] denote l and queries[2*i+1] denote r for i-th query (0<= i <q).

Example 1:

Input : Arr[] = {1, 2, 3, 4, 5}, Q = 3
queries[] = {0, 2, 1, 3, 0, 4}
Output : 2 3 3
Explanation:
Here we can see that the array of
integers is [1, 2, 3, 4, 5].
Query 1: L = 0 and R = 2
Sum = 6
Integer Count = 3
So, Mean is 2
Query 2: L = 1 and R = 3
Sum = 9
Integer Count = 3
So, Mean is 3
Query 3: L = 0 and R = 4
Sum = 15
Integer Count = 5
So, the Mean is 3.
So, In the end, the function will
return the array [2, 3, 3] as an answer.

Example 2:

Input : Arr[] = {6, 7, 8, 10}, Q = 2
queries[] = {0, 3, 1, 2}
Output : 7 7