DSA 32: Quick Algorithms - Exercises [Part 3]

Chapter 13 Exercises, J.Wengrow Vol 1
data structures
algorithms
Author

Tony Phung

Published

February 15, 2025

1. Greatest Product of 3

Instructions:

  • Use sorting to implement the function in a way that it computes at \(O(N \log N)\) speed

Input:

  • Array of positive numbers

Output:

  • Greatest Product of Any Three Numbers

1.1 Greatest Product of 3: Tony’s Solution - partition

def partition(arr, l, r):
    p=r
    pivot=arr[p]
    r-=1
    # print(f"l{l},r{r},p{pivot}: {arr}")
    while True:
        while arr[l]<pivot:
            
            # print(f"[l{arr[l]}<p{pivot}]: l{l},r{r},p{pivot}: {arr}")
            l+=1
        while arr[r]>pivot:
            # print(f"[r{arr[r]}>p{pivot}]: l{l},r{r},p{pivot}: {arr}")
            r-=1
        if l>=r:
            # print(f"[l{l}>r{r}]: l{l},r{r},p{pivot}: {arr}")
            break
        else:
            arr[l],arr[r]=arr[r],arr[l]
            # print(f"[l{l}<r{r}]: l{l},r{r},p{pivot}: {arr}")
            l+=1
    arr[l],arr[p]=arr[p],arr[l]            
    # print(f"l{l},r{r},p{pivot}: {arr}")
    return l

1.2 Greatest Product of 3: Tony’s Solution - sort & top_3_prod

def quicksort(arr, l, r):
    if r-l<=0:
        return
    p=partition(arr,l,r)
    quicksort(arr,l,p-1)
    quicksort(arr,p+1,r)
    
def top_3_prod(arr):
    quicksort(arr, 0, len(arr)-1)
    # print(arr)
    return arr[-1]*arr[-2]*arr[-3]

arr = [int(char) for char in "052163"]
print(top_3_prod(arr))
print(6*5*3)
    
90
90

2. Find Missing Integer

Instructions:

  • Use sorting to implement the function in a way that it computes at \(O(N \log N)\) speed

Input:

  • Array of integers from 0 to array’s length

Output:

  • The missing interger

2.1 Find Missing Integer: Tony’s Solution - No Duplicates

def find_missing_integer_v1(arr):
    print(f"input_array: {arr}")
    quicksort(arr,0,len(arr)-1) # 052163 becomes 012356
    print(f"sorted_array: {arr}")
    for i in range(len(arr)-1):
        # print(arr[i])
        if arr[i]+1 != arr[i+1]:
            print(f"missing_integer: {arr[i]+1}")
            return arr[i]+1

2.1.1 Find Missing Integer: Tony’s Solution - TEST 1

# WORKS FOR INTEGERS APPEARING ONLY ONCE
arr = [int(char) for char in "052163"]
print(find_missing_integer_v1(arr)) # 4
input_array: [0, 5, 2, 1, 6, 3]
sorted_array: [0, 1, 2, 3, 5, 6]
missing_integer: 4
4

2.1.2 Find Missing Integer: Tony’s Solution - TEST 2

Note: Solution v1 does not always work with duplicate values in the input array

# FAILS AT
arr = [int(char) for char in "01592428356"]
print(find_missing_integer_v1(arr)) # 4
input_array: [0, 1, 5, 9, 2, 4, 2, 8, 3, 5, 6]
sorted_array: [0, 1, 2, 2, 3, 4, 5, 5, 6, 8, 9]
missing_integer: 3
3

2.2 Find Missing Integer: Tony’s Solution - Duplicates Allowed

Updated v2 works with duplicate values in input array

def find_missing_integer_v2(arr):
    print(f"input_array: {arr}")
    quicksort(arr,0,len(arr)-1) # 01592428356" becomes 01223455689
    print(f"sorted_array: {arr}")
    for i in range(len(arr)-1):
        if arr[i+1]-arr[i] > 1:
            print(f"missing_integer: {arr[i]+1}")
            return arr[i]+1
        
# WORKS FOR DUPLICATE INTEGERS
arr = [int(char) for char in "01592428356"]
print(find_missing_integer_v2(arr)) # 7
input_array: [0, 1, 5, 9, 2, 4, 2, 8, 3, 5, 6]
sorted_array: [0, 1, 2, 2, 3, 4, 5, 5, 6, 8, 9]
missing_integer: 7
7

3. Find Greatest Number

Instructions:

  • Write three functions of different time-complexlities:
    • \(O(N^2)\)
    • \(O(N \log N)\)
    • \(O(N)\)

Input:

  • Array

Output:

  • Greatest Number of Array

3.1 Find Greatest Number: Tony’s Solution - \(O(N^2)\)

def max_int_nsqrd(arr):
    step=0
    for i in range(len(arr)):
        curr_max = arr[i]
        for j in range(len(arr)):
            step+=1
            if arr[j]>curr_max:
                curr_max = arr[j]
            print(f"[Step {step}]: {curr_max} ({curr_max}vs{arr[j]})")
    return curr_max
arr = [int(char) for char in "0132"]
print(max_int_nsqrd(arr))
print(f"Expected Steps: {len(arr)**2}")
[Step 1]: 0 (0vs0)
[Step 2]: 1 (1vs1)
[Step 3]: 3 (3vs3)
[Step 4]: 3 (3vs2)
[Step 5]: 1 (1vs0)
[Step 6]: 1 (1vs1)
[Step 7]: 3 (3vs3)
[Step 8]: 3 (3vs2)
[Step 9]: 3 (3vs0)
[Step 10]: 3 (3vs1)
[Step 11]: 3 (3vs3)
[Step 12]: 3 (3vs2)
[Step 13]: 2 (2vs0)
[Step 14]: 2 (2vs1)
[Step 15]: 3 (3vs3)
[Step 16]: 3 (3vs2)
3
Expected Steps: 16

3.2 Find Greatest Number: Tony’s Solution - \(O(N\log N)\)

Expected Steps \(Nlog N\):

  • quicksort:
    • \(N\log N\) steps
  • read(-1):
    • \(1\) steps
  • total_steps:
    • = \((N\log N)\) steps + \((1)\) steps
    • = \((N\log N+1)\) steps
    • = \(N\log N\) time-complexity
def max_int_nlogn(arr):
    if len(arr)==1:
        return arr[0]
    print(f"unsorted_array: {arr}")
    quicksort(arr,0,len(arr)-1) # 01592428356 becomes 01223455689
    print(f"sorted_array: {arr}")
    return arr[-1]
arr = [int(char) for char in "01592428356"]
print(max_int_nlogn(arr))
unsorted_array: [0, 1, 5, 9, 2, 4, 2, 8, 3, 5, 6]
sorted_array: [0, 1, 2, 2, 3, 4, 5, 5, 6, 8, 9]
9

3.3 Find Greatest Number: Tony’s Solution - \(O(N)\)

def max_int_n(arr):
    steps=0
    max_val = arr[0]
    for i in range(1,len(arr)):
        steps+=1
        if max_val<arr[i]:
            max_val=arr[i]
        print(f"[Step {steps}]: {max_val} ({max_val}vs{arr[i]})")
    return max_val
arr = [int(char) for char in "01592428356"]
print(max_int_n(arr))
[Step 1]: 1 (1vs1)
[Step 2]: 5 (5vs5)
[Step 3]: 9 (9vs9)
[Step 4]: 9 (9vs2)
[Step 5]: 9 (9vs4)
[Step 6]: 9 (9vs2)
[Step 7]: 9 (9vs8)
[Step 8]: 9 (9vs3)
[Step 9]: 9 (9vs5)
[Step 10]: 9 (9vs6)
9