<jupyter_start><jupyter_text>Python Foundations  X5: Advanced Algorithms**Instructor**: <NAME>**Contact**: <EMAIL>---This notebook covers common algorithms throughout computer programming---  Sliding Window  Q1Given an array, find the average of all subarrays of ‘K’ contiguous elements in it.<jupyter_code>data = [1, 3, 2, 6, -1, 4, 1, 8, 2]
k=5
def soln1(data):
    means = []
    for idx in range(len(data)-k+1):
        means.append(sum(data[idx:idx+k])/k)
    return means
soln1(data)
%%timeit
soln1(data)<jupyter_output>1.37 µs ± 23 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)<jupyter_text>time complexity: \\(O(n*k)\\)<jupyter_code>def soln2(data):
    means = []
    winsum = sum(data[:k])
    means.append(winsum/k)
    for idx in range(1, len(data)-k+1):
        winsum -= data[idx-1]
        winsum += data[idx+k-1]
        means.append(winsum/k)
    return means
soln2(data)
%%timeit
soln2(data)<jupyter_output>1.06 µs ± 30.7 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)<jupyter_text>time complexity: \\(O(n)\\)  Q2Given an array of positive numbers and a positive number ‘S,’ find the length of the smallest contiguous subarray whose sum is greater than or equal to ‘S’. Return 0 if no such subarray exists.<jupyter_code>data = [2, 1, 5, 2, 3, 2]
S = 7
def scs(data, S):
    start = 0
    bestlen = len(data)
    for idx in range(len(data)):
        winsum = sum(data[start:idx])
        winlen = idx-start

        while sum(data[start+1:idx]) >= S:
            start += 1
            winlen -= 1
            winsum = sum(data[start:idx])

        if winsum >= S and winlen < bestlen:
            bestlen = winlen
    return bestlen
data = [2, 1, 5, 2, 3, 2]
S = 7
scs(data, S)
data = [3, 4, 1, 1, 6]
S=8
scs(data, S)<jupyter_output><empty_output><jupyter_text>time complexity: \\(O(n)\\) space complexity: \\(O(1)\\)  Q3Given a string, find the length of the longest substring in it with no more than K distinct characters.<jupyter_code># should return 5
string="araaci"
k=2

# should return 6
string="cbbebi" 
k=10
def substr(string, k, verbose=False):
    maxlen = 1
    idx = 0
    edx = 1
    curlen = 1
    if len(string) < 2:
        # need atleas 2 char
        pass

    sub = string[0]
    while edx < len(String):
        estreak = False
        while (edx < len(String)) and (estreak == False):
            
            # we could use hasing here instead of this fn call
            if sub.count(string[edx]) == k: # if we add we break our rule
                estreak = True    
            else:
                sub += string[edx]
                curlen += 1
                if curlen > maxlen:
                    maxlen = curlen
                if verbose:
                    print(sub, curlen, edx, maxlen, sub.count(string[edx]))
                edx += 1            
        sub = sub[1:]
        curlen -= 1
        idx += 1
    return maxlen    
substr(string, k, True)
string="cbbebi" 
k=10
substr(string, k, False)
%%timeit
substr(string, k, False)<jupyter_output>2.19 µs ± 120 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)<jupyter_text>time complexity: \\(O(n)\\) space complexity: \\(O(n)\\)  Two PointersUseful on linked lists, sorted lists  Q1 Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.<jupyter_code>data = [1, 2, 3, 4, 6]
target = 6
# Output: [1, 3]
def find_pair(data, target):
    pt1 = 0
    pt2 = len(data)-1
    while True:
        if data[pt1] + data[pt2] < target:
            pt1 += 1
        elif data[pt1] + data[pt2] > target:
            pt2 -= 1
        if (pt2 > len(data)) or data[pt1] + data[pt2] == target:
            break
    return pt1, pt2
find_pair(data, target)
%%timeit
find_pair(data, target)<jupyter_output>672 ns ± 57.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
{'fraction_non_alphanumeric': 0.12819190095434616, 'fraction_numerical': 0.03868970853752902, 'mean_word_length': 2.4563279857397506, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '404054', 'license': 'MIT', 'n_tokens_mistral': 1469, 'n_tokens_neox': 1351, 'n_words': 451, 'path': 'notebooks/extras/X5_Advanced_Algorithms.ipynb', 'repo_name': 'wesleybeckner/python_foundations', 'size': '3901'}