Forem: Dumb Down Demistifying Dev

Pigeonhole Sort

Dumb Down Demistifying Dev — Tue, 07 Jun 2022 07:01:19 +0000

What do we understand about Pigeonhole Sort?

Very very very simple and straightforward sorting algorithm
One of the most effecient sorting algorithm with JS implementation to be as fast as 1 digit millisecond
Is NOT a comparison sort
ONLY Interger values from negative to positive
Stable algorithm
Handles sorting by placing integer value by index of new Array
The new Array's index holds an Array of the copied integer value when interated over
In JS can be done in ONE loop
Returns a new Array
Time complexity
- Best is O(n+k)
- Average is O(n+k)
- Worst is O(n+k)
Space complexity
- O(n+k)
Note: n – Size of array, k - Range of value

function PigeonHoleSort(arr) {
  const min = Math.min(...arr);
  const pigeonhole = [];

  arr.forEach(num => {
    if (pigeonhole[num - min]) pigeonhole[num - min].push(num);
    else pigeonhole[num - min] = [num];
  });
  return pigeonhole.flat();
}

Find The Average Pair

Dumb Down Demistifying Dev — Fri, 13 May 2022 09:48:26 +0000

Multi-Pointers QUestion 2

Given a sorted array and a target average value, write a function AveragePair to determine if a pair of numbers adds up to the target average value.

Thoughts:

One pointer at the start of the array
One pointer at the end of the array
Since the array is sorted,
- if calculated average pair bigger than the expected value
  - we move left pointer by 1 position to the right
- if calculated average pair smaller than the expected value
  - we move right pointer by 1 position to the left
Practice both iterative and recursive methods

// Recursive method
function averagePair(sortedArr, avgNum){
    const arrLength = sortedArr.length;
    if (arrLength < 1) return false;

    function recurs(sortedArr, left, right) {
        if (left === right) return false;

        const avg = (sortedArr[left] + sortedArr[right]) / 2;
        if (avg === avgNum) return true;
        return (avg < avgNum) 
            ? recurs(sortedArr, left+=1, right)
            : recurs(sortedArr, left, right-=1);
    }

    return recurs(sortedArr, 0, arrLength - 1);
}

// Iterative method
function AveragePair(sortedArr, avgNum){
    const arrLength = sortedArr.length;
    if (arrLength < 1) return false;

    let left = 0;
    let right = arrLength - 1;
    while(right > left) {
        const avg = (sortedArr[left] + sortedArr[right]) / 2;
        if (avg === avgNum) return true;
        if (avg < avgNum) {
            left++;
        } else {
            right--;
        }
    }
    return false;
}

Duplicate Arguments

Dumb Down Demistifying Dev — Fri, 13 May 2022 09:16:34 +0000

Given N number of arguments, write a function CheckArgsDuplicates to determine if its arguments have any duplicate.

Thoughts:

One-liner in JavaScript does exist for such question
Since it is not needed to count the number of duplicates, once it exist in the hash we return true

// Time complexity - O(n)
// Space complexity - O(n)
function CheckArgsDuplicates(...args) {
    const argumentz = [...args];
    const argsLength = argumentz.length;

    let argCounter = {};
    for (let i=0; i<argsLength; i++) {
        if (argCounter[argumentz[i]]) return true;
        argCounter[argumentz[i]] = 1;
    }

    return false;
}

// one-liner solution which should only be used as naive solution
function CheckArgsDuplicates(...args) {
    return Array.from(new Set(args)).length !== args.length;
}

Valid Numeric Anagram

Dumb Down Demistifying Dev — Fri, 13 May 2022 08:45:36 +0000

Given 2 postive integers, write a function to determine if they have the same number of repeated / non-repeated elements.

Thoughts:

Since this question uses numbers instead of string it is possible to employ some JS tricks to get the individual digits
- we could stringify first and get the character in each position
- OR we could use mathematical formula to get the same result
The mathematical method employs the same trick as in Radix Sort
Employ the same mathematical tactic to practice since it is the more difficult solution
Stringify method is simpler but is hard to translate over to other languages as a solution

function getNumOfDigits(num) {
    if (num === 0) return 1;
    return Math.floor(Math.log10(num)) + 1;
}
function getDigitByPos(num, pos) {
    if (num === 0) return 0;
    return Math.floor(num / Math.pow(10, pos)) % 10;
}

function ValidNumericAnagram(numX, numY) {
    if (getNumOfDigits(numX) !== getNumOfDigits(numY)) return false;

    let digitCounter = {};
    let limit = getNumOfDigits(numX);
    for (let i=0; i<limit; i++) {
        const digit = getDigitByPos(numX, i);
        if (digitCounter[digit] === undefined) {
            digitCounter[digit] = 0
        }
        digitCounter[digit]++;
    }

    for (let i=0; i<limit; i++) {
        const digit = getDigitByPos(numY, i);
        if (digitCounter[digit] === undefined) {
            return false;
        }
        digitCounter[digit]--;
    }

    return true;
}

Unique Values Counter

Dumb Down Demistifying Dev — Thu, 12 May 2022 13:44:04 +0000

Implement a function CountUniqueValues, which takes in a sorted Array of positive and negative integers.
It should count and return the number of unique values in the Array.

Thoughts:

This is an easy question.
It should be easily checked against using JavaScript.
It should try to use pointers to track the position of values to be compared against.
No need to mutate the original Array.

function CountUniqueValues(arr) {
    if (arr.length === 0) return 0;

    let uniqueValueIndex = 0;
    let counter = 1;

    for (let i = 1; i < arr.length; i++) {
        if (arr[i] !== arr[uniqueValueIndex]) {
            counter++;
            uniqueValueIndex = i;
        }
    }

    return counter;
}

// sample data
const sorted_array = [-10,-11,1,1,1,2,3,4,5,5,5,6,7,7,7,7,8];
// result
console.warn(CountUniqueValues(sorted_array));
// to be asserted against result
console.warn(Array.from(new Set(sorted_array)).length);

Radix Sort

Dumb Down Demistifying Dev — Thu, 12 May 2022 11:43:48 +0000

What do we understand about Radix Sort ?

Stable Sorting Algorithm
Mutates original Array
Is NOT a comparison sort
sorts by exploiting the way numerics are interpreted
mostly implemented if Array contains only positive numbers
- there can only exist 10 different positive integers (0 - 9)
each loop results in Array<Array<Int>>
- similar concept to Bucket Sort
uses 2 nested for-loops
- First, create 2 helper functions
  - getMaxNumOfDigits()
  - getDigitByPos()
- Next, in main function
  - Outer loop ends at MaxNumOfDigits
    - init new bucket of 10 on each loop (Array of size 10)
  - Inner loop loops thru total number of elements in the Array
    - bucket position would have an Array inside pushed with values of that digit by position
  - flatten the Array of Array and reassign back to original Array
Time and Space Complexities are a complete opposite of Counting Sort
Time complexity
- Best is O(nk)
- Average is O(nk)
- Worst is O(nk)
Space complexity
- O(n+k)

function getMaxNumOfDigits(arr) {
    const max = Math.max(...arr);
    if (max === 0) return 1;
    // suggest to just memorise this if can't think of the math on the spot
    // else just use stringify and get length of string
    return Math.floor(Math.log10(max)) + 1;
}
function getDigitByPos(num, pos) {
    if (num === 0) return 0;
    // e.g.
    // num = 1234, pos = 2
    // floor(1234 / 10^2) % 10
    // floor(1234 / 100) % 10
    // = 12 % 10
    // = 2
    return Math.floor(num / Math.pow(10, pos)) % 10;
}

function RadixSort(arr) {
    const arrLength = arr.length;
    const maxNumOfDigits = getMaxNumOfDigits(arr);

    for(let i = 0; i < maxNumOfDigits; i++) {
        const digitsBucket = new Array(10);

        for (let j = 0; j < arrLength; j++) {
            const digit = getDigitByPos(arr[j], i);
            if (!digitsBucket[digit]) {
                digitsBucket[digit] = [];
            }
            digitsBucket[digit].push(arr[j]);
        }

        arr = digitsBucket.flat();
    }

    return arr;
}

Counting Sort

Dumb Down Demistifying Dev — Thu, 12 May 2022 08:48:40 +0000

What do we understand about Counting Sort?

One of the most effecient sorting algorithm
Has at least 3 loops to be implemented
Should be implemented mathematically
Is NOT a comparison sort
ONLY Interger values from negative to positive
Stable algorithm
Returns a new Array
Time complexity
- Best is O(n+k)
- Average is O(n+k)
- Worst is O(n+k)
Space complexity
- O(k)

function CountingSort(arr) {
    let max = arr[0];
    let min = arr[0];
    arr.forEach(val => {
        if (val > max) max = val;
        if (val < min) min = val;
    });

    //! to account for negative numbers, we use max and min.
    //! e.g. 10 - (-4) = 14 Array size.
    //! we need a +1 position to the right for counting of left & right values
    let counter_size = max - min + 1;
    let counter = new Array(counter_size).fill(0);
    //! the index of counter Array indicates the value of the number in arr Array
    //! count the number of times the number repeats and store in index of counter Array
    arr.forEach((_, i) => counter[arr[i] - min]++);

    //! to get the starting position of the number from arr Array,
    //! count the previous value with current value of counter Array
    for (let i = 1; i < counter.length; i++) {
        counter[i] += counter[i - 1];
    }

    let results = new Array(arr.length);
    //! skip the last element as it is not used in the result
    for (let i = results.length - 1; i >= 0; i--) {
        //! decrement the counter before assigning value to results Array of the index position
        //! assign results Array with original Array value at position i
        results[--counter[arr[i] - min]] = arr[i];
    }

    return results;
}

Quick Sort

Dumb Down Demistifying Dev — Thu, 12 May 2022 07:52:57 +0000

What do we understand about Quick Sort?

Usually implemented recursively
Mutates the original Array
Similar mental model to reversing a Binary Tree
Similar to Merge Sort
It is a Divide & Conquer algorithm
It comprises of 2 functions
- Main function recursively splits the Array into left and right halves
- Left and right half is determined via Array index
2nd helper function does the swap and returns the new pivot index
- by convention, last value is the pivot value to be compared with
- if current loop index's value is less than pivot value
- increment
- smaller to the left of the pivot
- bigger to the right of the pivot
- lastly, return the pivot point
Best video explanation I found online:
- NeetCode - LEETCODE 912 (JAVASCRIPT) | SORT AN ARRAY (QUICK SORT)
Time Complexity:
- Best : O(nlogn)
- Average: O(nlogn)
- Worst : O(n^2)
Space Complexity:
- O(logn)

// 27, 18, 6, 21, 26, 24
// |
// i
// |
// pivotIndex
//                    |
//                    pivotValue

function getPivotPoint(arr, start, end) {
    // by convention we always pick the last element as pivot
    let pivotValue = arr[end];
    // pivot index should at the end hold the larger value compared to pivot
    let pivotIndex = start;

    for (let i = start; i < end; i++) {
        // as loing as values on the left of the pivot is smaller in value,
        // we swap the index with the latest updated pivot index
        if (arr[i] < pivotValue) {
            if (i !== pivotIndex) {
                [arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
            }
            pivotIndex++;
        }
    }

    // swap the latest updated pivot index with the pivot value itself
    // everything on the right is now larger value than the pivot value
    [arr[end], arr[pivotIndex]] = [arr[pivotIndex], arr[end]];

    // return new pivot point
    return pivotIndex;
}
function QuickSort(arr, start = 0, end = arr.length - 1) {
    // base case
    if (end > start) {
        const pivot = getPivotPoint(arr, start, end);
        QuickSort(arr, start, pivot - 1);   // do the pivot swap on the left
        QuickSort(arr, pivot + 1, end);     // do the pivot swap on the right
    }
    return arr;
}

Selection Sort

Dumb Down Demistifying Dev — Thu, 12 May 2022 05:09:29 +0000

What do we understand about Selection Sort?

Pretty simple once we understand the concept.
Mutates original Array rather than returning a new Array
Similar to Bubble Sort
Both use 2 for-loops and also does the same standard swapping logic
- Outer loop holds the index pointer of the "smallest" comparison value
- Inner loop searches for a smaller value than the current "smallest" pointer value
Get new smallest value's index
Swap in the outer loop by index of new smallest value with current "smallest" pointer value.
Time Complexity:
- Best : O(n^2)
- Average: O(n^2)
- Worst : O(n^2)
Space Complexity:
- O(1)

    function SelectionSort(arr) {
        const arrayLength = arr.length;

        for (let i = 0; i < arrayLength - 1; i++) {
            let smallestIndexPointer = i;
            for (let j = i + 1; j < arrayLength; j++) {
                if (arr[j] < arr[smallestIndexPointer]>) {
                    smallestIndexPointer = j;
                }
            }
            if (smallestIndexPointer !== i) {
                [arr[i], arr[smallestIndexPointer]] = [arr[smallestIndexPointer], arr[i]];
            }
        }

        return arr;
    }

Insertion Sort

Dumb Down Demistifying Dev — Wed, 11 May 2022 10:21:53 +0000

What do we understand about Insertion Sort?

It uses 2 loops (outer for-loop & inner while-loop) and 2 pointers
1st pointer starts from 1 item after the 2nd pointer
2nd pointer starts from 1 item before 1st pointer
2nd loop loops decrementally till 0
as long as current value is more than left side value we copy the left side over to current
insertion happens after the 2nd loop is finished
Mutation is performed on the original Array
Time complexity
- Best -> O(n)
- Average -> O(n^2)
- Worst -> O(n^2)
Space complexity
- O(1)

    function InsertionSort(arr) {
        for (let i = 1; i < arr.length ; i++) {
            let currentValue = arr[i];
            let oneIndexBefore = i - 1;
            while (oneIndexBefore >= 0 && arr[oneIndexBefore] > currentValue) {
                arr[oneIndexBefore + 1] = arr[oneIndexBefore];
                oneIndexBefore--;
            }
            arr[oneIndexBefore + 1] = currentValue;
        }
        return arr;
    }

Merge Sort

Dumb Down Demistifying Dev — Wed, 11 May 2022 08:51:03 +0000

What do we understand about Merge Sort?

This is a Divide & Conquer algorithm
It usually comprises of 2 functions
- main function recursively splits the Array into 2 halfs before merger
- 2nd function is the actual merge function where it compares the left Array values with the right Array values
  - there should be a counter that acts as the pointer for the 2 half Arrays
  - returns a new Array instead of mutating the original Array
Good resource to continue reading up on:
- https://stackoverflow.com/questions/60288089/javascript-merge-sort-and-recursion
Time Complexity:
- Height of the tree refers to the recursion part of the function - O(logn)
- Merge helper function - O(n)
- MergeSort worst - O(nlogn)
Space Complexity:
- O(n)

    function merge (left, right) {
        let x = 0;
        let y = 0;
        let output = [];

        //! we check both the left and right pointers
        //! if they have reached the end of their respective Arrays
        while (x < left.length && y < right.length) {
            //! COMPARE
            if (left[x] < right[y]) {
                output.push(left[x]);
                x++;        // next value to check if it is also smaller
            } else {
                output.push(right[y]);
                y++;        // bigger values comes in here
            }
        }

        // left side leftovers from first loop
        while (x < left.length) {
            output.push(left[x]);
            x++;
        }

        // right side leftovers from first loop
        while (y < right.length) {
            output.push(right[y]);
            y++;
        }

        return output;
    }

    function MergeSort(arr, start = 0, end = arr.length) {
        const arrayLength = arr.length;
        if (arrayLength < 2) return arr;

        const midindex = Math.floor(arrayLength / 2);
        const left = MergeSort(arr.slice(start, mid));
        const right = MergeSort(arr.slice(mid + 1, end));

        return merge(left, right);
    }

Bubble Sort

Dumb Down Demistifying Dev — Wed, 11 May 2022 06:14:58 +0000

What do we understand about Bubble Sort?

It uses 2 for-loops
- outer loop loops DECREMENTALLY
- inner loop loops INCREMENTALLY
  - it is also the loop that does the swapping
The check for swap is simple
- it does the comparison in the inner loop
- it compares the current to 1 position next to the current
- bigger goes to the right, smaller or equals we skip
Time complexity
- O(n^2)
Space complexity
- O(1)

    function BubbleSort(arr) {
        for (let i = arr.length; i >= 0; i--) {
            //! condition to check if we still proceed with the inner loop
            let alreadySorted = true;

            //! NOTE:
            //! Since the previous loops already pushed the largest number to the right of the loop
            //! the inner loop does not need to loop all the way to the end again.
            for (let j = 0; i < i - 1; j++) {

                //! compare left to right
                if (arr[j] > arr[j + 1]) {
                    //! if nothing comes thru the if condition
                    //! means everything behind are already sorted
                    //! stop looping and break from the outer loop
                    alreadySorted = false;

                    //! SWAP
                    // this is the es6 syntax for swapping
                    // other languages may have the same
                    // I know Golang has something similar
                    [arr[j], arr[j+1]] = [arr[j+1], arr[ij];
                }
            }

            if (alreadySorted) {
                break;
            }
        }

        //* return the result after all the loops have been done.
        return arr;
    }

NOTE: There is a way of writing the swap logic in a more universal way for most other languages to implement as well.

// a more universal swap logic
const temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;