PYTHON_STUDY ARRAY ALGORITHM

problem 1 : Given an integer arrays, find a contiguous subarray which has the largest sum and length should be greater or equal to 
given length k. Return the largest sum, return 0 if there are fewer than k elements in the array.
find a maximum subarray sum whose length has >= k

this problem is analogy to problem find maximum average with length >= k !!!

def maxSubarray4(self, nums, k):
        # write your code here
        result, size = 0-math.inf, len(nums)
        if size < k:
            return 0
            
        #sample code for finding maximum subarray sum with length >= k !!!
        prefix_sum, suffix_sum, min_minus = 0, 0, math.inf
        for i in range(k):
            prefix_sum += nums[i]
        result = max(result, prefix_sum)
        for i in range(k, size):
            prefix_sum += nums[i] #prefix sum
            suffix_sum += nums[i-k] #consecutive subarray sum starting from i-kth
            min_minus = min(suffix_sum, min_minus) #minimum subarray sum starting from i-kth
            last_max = prefix_sum - min(min_minus,0) #min(min_minus,0) is the minimum sum of array from i-kth
            result = max(result, last_max) #last_max is the max subarray sum until ith where i is from k to size !!
        return result
        
problem 2: intersection of arrays:
method 1: hashset
method 2: sort two arrays and perform merge sorted array logic, work even if duplicated elements exist !
method 3: sort the smaller array and perform binary search on sorted smaller array with bigger unsorted array to find all 
shared elements !! this does not work if duplicated element exists !
        
problem 3: find the median of two sorted array using advanced binary search method(二分法) !!
#using binary search to count the number of elements in sorted array that is <= target(inclusive!!!)
def binary_search_count(self, array, st, end, target):
        if end < st:
            return 0
        while st + 1 < end:
            middle = int((st + end) / 2)
            if array[middle] > target:
                end = middle
            else:
                st = middle
        if st < len(array) and array[st] > target:
            return st
        if end < len(array) and array[end] > target:
            return end
        return end + 1
    
    #using advanced binary search idea to 二分solution !!
    def advance_binary_findkth(self, array1, array2, st, end, k):
        while st < end:
            middle = int((st + end) / 2)
            count_sum = self.binary_search_count(array1, 0, len(array1)-1, middle) + 
            self.binary_search_count(array2, 0, len(array2)-1, middle) 
            if count_sum < k: #if less than k, middle is less than our solution median
                st = middle + 1
            else:
                end = middle
        return st
        
    #main function
    sizea, sizeb, st, end = len(A), len(B), math.inf, 0-math.inf
        if sizea + sizeb == 0:
            return 0
        if sizea > 0:
            st, end = min(st, A[0]), max(end, A[-1])
        if sizeb > 0:
            st, end = min(st, B[0]), max(end, B[-1])
        if (sizea+sizeb) % 2:
            return self.advance_binary_findkth(A, B, st, end, int((sizea+sizeb)/2)+1)
        else:
            return (self.advance_binary_findkth(A, B, st, end, int((sizea+sizeb)/2)+1) + 
            self.advance_binary_findkth(A, B, st, end, int((sizea+sizeb)/2))) / 2

problem: find reverse pairs using binary index tree !!!
idea: instead of using index of input array, we use the rank number as index of the binary index tree ! convert absolute number
into relative rank number is called discretization !! for nums[j], our goal is to find #members from 0..j-1 that is bigger than
nums[j], and do this in a loop and sum up result as our solution !

def low_bits(self, i):
        return i & (0 - i)
    
    def add(self, array, size, idx, val):
        idx += 1
        while idx < size:
            array[idx] += val
            idx += self.low_bits(idx)
        return
    
    def range_sum(self, array, idx):
        idx, result = idx + 1, 0
        while idx > 0:
            result += array[idx]
            idx -= self.low_bits(idx)
        return result
    
    #get relative rank number list
    def sort_index(self, array):
        results = [0 for i in range(len(array))]
        index_list = sorted(range(len(array)), key = (lambda k:array[k])) #return sorted index list from smallest to biggest
        for idx in range(len(array)):
            results[index_list[idx]] = idx 
        return results
    
    def reversePairs(self, A):
        # write your code here
        result, array, size = 0, [0 for i in range(len(A)+1)], len(A)+1
        if len(A) < 2:
            return result
        rank_list = self.sort_index(A)
        for idx in range(size-1):
            result += idx - self.range_sum(array, rank_list[idx]) #overall number of members - numbers smaller or equal than target
            self.add(array, size, rank_list[idx], 1)
        return result