DEV Community: Waverley Leung

Big-O Notation from a Non-CS Perspective

Waverley Leung — Tue, 01 Jun 2021 21:30:52 +0000

Hi everyone!

Welcome to the second post in our Data Structures & Algorithm series! Last time we reviewed the crossovers in JavaScript arrays and strings. This time we will cover Big O notation, diving into time and space complexity.

Both of us (Megan and I) graduated from bootcamp, after learning Ruby on Rails, JavaScript, React, etc., we had to spend a lot of our time learning Big-O Notation through many online resources. We hope this will be the place for you if you are looking for a “plain English” explanation of Big-O Notation!

Introduction

In computer science, Big O notation is used to classify the run time or space requirements of an algorithm as their input size grows. For CS students at college, they have to learn different types of big- notation (Big O, Big Theta, Big Omega). But for the sake of software engineering technical interviews, all we care about is the best and worst case scenarios, which Big O provides the tightest description of the run time and space.

This graph demonstrates clearly on how the run time and space changes depending on the input of a Big-O Notation. O(1) and O(log n) have the best run time and space complexity while O(n!), O(n²) and O(2ⁿ) have the worst run time and space complexity.

In this article, we will break down all these notations with provided examples and Leetcode questions at the end of each part.

What does it mean by brute force and optimized solution?

Before we start, we would like to explain what brute force and optimized solution mean, as you might see these keywords later in the article.

The easiest way to understand what brute force solution is whatever solution comes to your head first. On the other hand, for optimized solution, after you have the brute force solution, you would think of an optimized solution to either simplify the code or minimize the time and space complexity if possible.

For instance, your brute force solution has a O(n²) time complexity and with optimized solution, you are able to reduce it to the time complexity of O(n).
Understanding this concept is important since this is something you would discuss with your interviewer on how you would make your solution from brute force to more optimized.

Complexity Comparison

Name	Big O Notations
Constant Time	O(1)
Logarithmic Time	O(log n)
Linear Time	O(n)
Linearithmic Time	O(n log n)
Quadratic Time	O(n²)
Exponential Time	O(2ⁿ)
Factorial Time	O(n!)

Constant Time: O(1)

Often referred to as “constant time”, O(1) has the least complexity. I like to think of this as no matter how large or small the input, you can always expect the same number of steps to execute inside the function.

Example:

function sayHelloToFirstFriend(friends) {
   return `Hello ${friend[0]}`
}

sayHelloToFirstFriend([“spongebob”, “patrick”, “sandy”, “squidward”, “gary”])
// “Hello spongebob”

Typical use cases
Accessing an Array through its Index
Inserting (push) or deleting (pop) from a Stack
Inserting or deleting a node in a Linked List
Insertion or deleting from a Queue
Searching, inserting, or deleting from a Hash Table

Logarithmic Time: O(log n)

Don’t be afraid of the math! When you see a logarithm it’s asking you, “What power must we raise this base to, in order to get this answer?" In other words, we use logarithms to solve for a variable when that variable is an exponent.

In terms of computer science this translates to: “How many times must we divide n in half in order to get back down to 1?” Therefore, solutions with O(log n) essentially divide the problem in half, determine which half it needs to continue, divide that section in half, repeating this same idea until it finds what it needs or ruling out the set. As a result, while these solutions do grow more than constant time, it nonetheless grows slowly compared to other time complexities.

Typical use cases
Binary Search
Certain Divide and Conquer Algorithms based on Linear functionality
Calculating Fibonacci Numbers

Note: Notice that for all of these use cases the input is sorted and searching for something!

Linear Time: O(n)

Probably the most familiar is O(n), or “linear time”. This is because as the size of the input grows, the time the number of operations takes to execute also grows. In other words, if an array has 10 items a for loop will be executed 10 times whereas if the array has 10,000 items the same for loop would execute 10,000 times as well.

Example 1:

const binarySearch = (list, target) => {
  let start = 0
  let end = list.length - 1

  while (start <= end) {
    const middle = Math.floor((start + end) / 2)
    const guess = list[middle]

    if (guess === target) {
      return middle
    }

    if (guess > item) {
      // search the right side of the list
      end = middle - 1
    } else {
      // search the left side of the list
      start = middle + 1
    }
  }
  return null // if target is not found
}

Example 2:

function sayHelloToFriends(friends) {
   for (let i = 0; i < friends.length; i++) {
      console.log(`Hello ${friends[i]}`)
   }
}

sayHelloToFriends([“spongebob”, “patrick”, “sandy”, “squidward”, “gary”])
// “Hello spongebob”
// “Hello patrick”
// “Hello sandy”
// “Hello squidward”
// “Hello gary”

Typical use cases
Traversing an Array or Linked List
Linear Search
Deletion of a specific element in a Linked List (Not sorted)
Comparing two strings
Checking for Palindrome
Anytime using a `for` loop or iterating

Linearithmic Time: O(n log n)

Building off of typical solutions for O(log n), the extra “n” comes from the extra time cost of sorting. Therefore, a lot of sorting algorithms have the complexity of O(n log n). On the other hand, while it does take more time than O(log n), it’s also important to remember that logarithms grow very slowly. As a result, its path is similar to that of linear time. To explain a bit more of the role n plays, let’s take a look at merge sort.

Starting the same as O(log n), in merge sort you start by dividing the array in half. Next you sort the two halves and then merge the two sorted halves into one sorted whole. However, in order to sort the two halves you repeat the same idea of dividing them, sorting them, merging the sorted halves until you’ve sorted everything.

Example:

function merge(left, right) {
    let arr = []
    // Break out of loop if any one of the array gets empty
    while (left.length && right.length) {
        // Pick the smaller among the smallest element of left and right sub arrays 
        if (left[0] < right[0]) {
            arr.push(left.shift())  
        } else {
            arr.push(right.shift()) 
        }
    }

    // Concatenating the leftover elements
    // (in case we didn't go through the entire left or right array)
    return [ ...arr, ...left, ...right ]
}

function mergeSort(array) {
  const half = array.length / 2

  // Base case or terminating case
  if(array.length < 2){
    return array 
  }

  const left = array.splice(0, half)
  return merge(mergeSort(left),mergeSort(array))
}

Typical use cases
Merge Sort
Heap Sort
Quick Sort
Certain Divide and Conquer Algorithms based on optimizing O(n²) algorithms

Quadratic Time: O(n²)

A function with quadratic time complexity has a growth rate of n². Meaning? If the input size is 2, then the function has to do 4 times. If the input size is 3, then the function has to be done 9 times. If the input size is 1000, then the function has to do 1,000,000 (1 million) times.
In other words, O(n²) is going to run really slow, especially since the input size is really large.

Most of the time, we would describe an algorithm that has quadratic time when we have to iterate an object at least twice, examples like nested for loops.

Find duplicates and bubble sort are two of the quadratic algorithms examples that you would run into. Bubble sort (as well as insertion sort and selection sort) is like the naive version of merge sort and quick sort. It is slow, but it is always the first concept you would first learn when learning sorting algorithms. It builds a great foundation for the rest of the more complicated sorting algorithms.

What bubble sort does is repeatedly swapping adjacent elements if they are in the wrong order. Let's say we are sorting an unordered array of numbers from smallest to largest. Bubble sort would examine the numbers if they are in the right order by swapping them one by one .

Example of Bubble Sort:

function bubbleSort(arr, n) {
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap (arr, j, j+1);
      }
    }
  }
}

// swap helper method
function swap (arr, first, second) {
  let temp = arr[first];
  arr[first] = arr[second];
  arr[second] = temp;
}

Comparing to Merge Sort, which the array would be cut in half , Bubble Sort would go through each element of the array one by one until everything is sorted in the right place (and then it will go through again one more time even though it is already sorted.)

Typical use cases
Bubble Sort
Insertion Sort
Selection Sort
Find Duplicates (Brute Force)
Find All Possible Ordered Pairs in An Array

Exponential Time: O(2ⁿ)

Base-2 Exponential running time means the calculations will go double with each input size grows.
2² => 4
2³ => 8
2⁴ => 16
...
2¹⁰ => 1,267,650,600,228,229,401,496,703,205,376

As you can see whenever n is increased by 1, the result is doubled. Essentially, the number starts very low and to the end, the number will be very large.

In most cases, please avoid the use of exponential time since the run time is going to get slower. Not that it's the worst one, but obviously it's not great.

Fibonacci Example

function fib(n) {
  if (n <= 1) {
    return n
  }
  return fib(n - 1) + fib (n - 2)
}

Typical use cases
Power Set: Finding all the subsets on a set
Fibonacci Number

Factorial Time: O(n!)

If you understood how factorial works, this is how it's like:
5! = 5 x 4 x 3 x 2 x 1, in other words,
n! = n x (n - 1) x (n - 2) x (n - 3)... x 1

As the input size increases, the run time gets bigger and bigger and BIGGER! I personally have not encountered a factorial problem, therefore I would attach an example below with the link as reference.

Typical use cases
Permutations

Conclusion

We hope this article gives you a better understanding of Big-O Notation! This concept is important since often during interviews, you will need to analyze the Big-O Notation of your solution. Furthermore, knowing this can help you understand which solution has better or worse runtime as you come up with approaches. If you are still having trouble understanding, we have provided more resources down below for you to reference!

Resources

Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities 👀 (Stack Overflow)
Big-O Cheat Sheet
What is Big O Notation Explained: Space and Time Complexity (FreeCodeCamp)
Big-O notation (Wikipedia)
8 time complexities that every programmer should know (With Videos and Examples)
Comparing different solutions for Two Sum (Stanford)

Everything JavaScript Arrays & Array Methods!

Waverley Leung — Fri, 23 Apr 2021 20:49:19 +0000

Introduction
What are arrays?
How do we create arrays?
Methods
- Basic Methods: pop, push, shift, unshift, splice, slice
- Advanced Methods: reduce, sort, concat, filter, join, map, find, forEach
- Fun Methods: toString, includes, fill, indexOf, findIndex
Conclusion
Resources

Introduction

One data structure that many other complex ones build off of is the humble array. Therefore, it’s important to have a strong foundational understanding and knowledge of arrays before diving into other data structures. In this post we will cover what arrays are, how to create them, and 20 methods ranging from ones you will commonly use, some that are a bit more complex (mainly because of callback functions), and some fun ones to know as well.

Before you go, if you’re interested in learning more data structures and want another resource for algorithms, check out the series Megan Lo and I are collaborating on! The series will focus on data structures and algorithms, and our first post covers the crossover of Strings and Arrays. If you need a refresher on Strings, check out her post here, otherwise visit our collab and stay tuned for more!

Without further ado, let’s dive into the wonderful world of arrays!

P.S. Since this is a very long post, feel free to skip around as you like 😉

What are arrays?

According to MDN, JavaScript arrays are “list-like objects whose prototype has methods to perform traversal and mutation operations”. In other words, arrays organize their items sequentially and have built-in methods that allow you to easily lookup and add/remove information based on its position. Array positions, also known as indexes, start at zero.

Fun fact: Unlike non-scripting languages like Java, C, or C++, JavaScript (as a scripted language) does not have static arrays where you need to specify in advance how many elements you plan to store because they have a fixed size. Instead, JavaScript arrays are dynamic, meaning the size of it will grow or shrink as needed.

Fun Fact: Arrays are a special type of object! That said, the array’s object properties are kept separate from its elements and the methods you would use on the array’s elements cannot be used on its object properties. To set or access the array’s object property collection, you need to use bracket or dot notation.

console.log(typeof new Array()) // “object”
console.log(typeof [1, 2, 3]) // “object”

Things to keep in mind:

Arrays have fast lookups of O(1) time because you can simply retrieve an element based on its given index, no matter how large the size of the array is.
It is time expensive O(n) to insert or delete from an array because it requires the other elements to “scoot” over to make room or fill the gap.

How do we create arrays?

Essentially there are two ways to create an array:

With the array literal

let literalEmptyArray = []
let literalFilledArray = [1, 2, 3]

With the new constructor

let constructorEmptyArray = new Array()
let constructorFilledArray = new Array(1, 2, 3)

That said, a third way to create an array is the of method! Essentially the of method creates a new Array instance from the passed in number of arguments, regardless of number or type of the arguments. The difference between the of method and Array constructor is what they do with the arguments; Array.of(7) creates an array with a single element, 7, whereas Array(7) creates an empty array with a length property of 7 (Note: this implies an array of 7 empty slots, not slots with actual undefined values)

Array.of(1);         // [1]
Array.of(1, 2, 3);   // [1, 2, 3]
Array.of(undefined); // [undefined]

Methods

Before going into some of the numerous (I roughly estimate more than 35) methods that arrays have, let’s first review what it means for something to be destructive vs non-destructive.

Destructive: The action mutates the original array, meaning that once you perform the action on the original array, you will not be able to have the original’s information again. Rather, the original has become updated.
Non-destructive: The action does not mutate the original array, meaning that once you perform the action on the original array, you will have the original’s information. Therefore, you will be able to have both the original and updated information.

Understanding and being aware of when a method is destructive vs non-destructive is important when you will ultimately need to decide which method to use. Now, let’s take a look at some basic, advanced, and fun methods!

Basic Methods

The methods we will be covering are: pop, push, shift, unshift, splice, and slice. To demonstrate each method, the base array we will be referring to is:

let iceCream = [“vanilla”, “chocolate”, “strawberry”, “green tea”]

The 4 most common use cases for methods on an array is to destructively add or remove an element from the beginning or end of it.

In case you can't see the image below, here's a summary of the methods:

push: Add an item to the end of an Array
pop: Remove an item from the end of an Array
unshift: Add an item to the beginning of an Array
shift: Remove an item from the beginning of an Array

Other common cases are copying or removing a section of the array. While they have similar names, these methods are splice and slice and it's important to remember whether or not you want the action to be destructive or non-destructive.

`splice`: Remove an item by index position (destructive)

When using splice, you must pass in what index you want to start removing items from (inclusive). You can optionally include a second argument index to say where you want to stop removing items from (inclusive), however if you don’t the method will automatically remove to the end. Additionally, starting from the third argument, any that you include will be elements added to the array, beginning from start (first argument). If you do not specify any elements, splice will only remove elements from the array. That said, if no arguments at all are passed in, the return value will be an empty array.

// general
Array.splice(startIndex)

// including the optional parameters
Array.splice(startIndex, endIndex, newElement)

Don't forget the original array for the following example!

`slice`: Copy an Array (non-destructive)

If you simply want to make a copy of an array you do not need to pass in any arguments. That said, you do have the option to include the starting index (inclusive) and ending index (non-inclusive) to copy from. This method is often used over splice because it avoids the “side-effect” of mutating the original array.

If you do not pass in any arguments, by default the entire original array will be copied. If either index is negative, it extracts starting from the end or last element (Array.length - index). On the other hand, if the arguments you pass in are larger than the actual array (for example, an array with 5 elements but passing in arguments to start at 10 and end at 50) the return value will be an empty array.

// general
Array.slice()

// including the optional parameters
Array.slice(startIndex, endIndex)

Don't forget the original array for the following example!

Advanced Methods

The methods we will be covering in this section are: reduce, sort, concat, flat, filter, join, map, find, and forEach. Before continuing on, it’s important to know that many of the methods have the same parameters; in this case filter, map, find, and forEach. Instead of repeating it each time, I’ll leave the explanation of the parameters up here for you to refer to!

There are three arguments you can pass into the callback function, two of them being optional. The one argument you must pass in is the current value, which represents the current element being processed. The other two arguments are the index of the current element and array the method was called upon. Besides the callback function, you can also use the thisArg parameter, which is the value to use as this when executing the callback. However, if the callback uses an arrow function the thisArg can be omitted because all arrow functions lexically bind the this value.

`reduce`: Reduce to a single value (destructive)

Essentially, the reduce method takes in a callback function that executes the callback on each element of the array, resulting in single output value. The callback (reducer) function you provide must at the very least include two parameters: the accumulator and current value. The accumulator accumulates callback's return values; in other words, it is the accumulated value previously returned in the last invocation of the callback On the hand, the current value is the value currently being processed in the array.

Optionally, the reduce method can take in a second argument that will represent the initialValue. This value is what the accumulator will start as if it is passed in. Additionally, the callback can take in other parameters for the index and array, which represent the index of the current element being processed and the array the reduce method was called on.

Array.reduce((accumulator, currentValue, index, array) => {
   // do something
   return accumulator + currentValue
})

`sort`: Sorts the elements (destructive)

When calling this method on the array it will sort it in place and return the sorted version. By default the elements will be sorted in ascending order by converting the elements to strings and then comparing their Unicode code points. It’s important to know how they are sorted because in a numeric sort, 9 comes before 80, but because numbers are converted to strings, "80" comes before "9" in the Unicode order. Something important to note, all undefined elements are sorted to the end of the array.

Optionally, and if you want to be more specific on how to sort (i.e. for integers), you can pass in a callback (compare) function that compares two arguments; the first and second element, often referred to as a and b, to each other. Under the hood, if the callback function returns:

less than 0, it means that the current order is correct; the first element will remain before the second element (a will still come before b)
0, it means that the elements are equal to each other; the order will remain the same with respect to each other, but sorted with respect to all different elements.
greater than 0, it means that the current order is incorrect; the second element will be before the first element (b before a)

Array.sort()

// including the optional parameters
Array.sort((a, b) => a - b)

`concat`: Merge arrays (non-destructive)

This method is used to merge two or more arrays, returning a new array without mutating the originals. To be more specific, the new array has all of the elements of the array it is called on, followed in order by, for each argument, the elements of the argument or the argument itself. However, if an argument is a nested array it will not take the nested array out, rather it will only remove it from the array it is in (one-level deep)

Fun Fact: concat copies the object references of the original into the new array so that both the original and new array refer to the same object! Therefore, if a referenced object is modified, the changes are visible to both the new and original arrays.

Array1.concat(Array2)

`flat`: Creates a new array with the sub-array elements concatenated into it (non-destructive)

Building off of the concat method, the flat method creates a new array with all sub-array elements concatenated into it recursively up to the specified depth. For a single level array, this accomplishes that same thing as the reduce method calling upon the concat method on its accumulator. On the other hand, to enable deep level flatten without the flat method, you can use recursion with reduce and concat.

While not required, you can optionally pass in an argument that specifies how deep a nested array structure should be flattened. By default this argument is 1, for a single level array.

Array.flat()

// including the optional parameters
Array.flat(2)

`filter`: Returns all the elements that pass the test function provided (non-destructive)

This method creates a new array with all the elements that pass a callback (test) function. As it tests each element of the array it is called on, it returns a value that coerces to true to keep the element, or to false otherwise. When the value is false, it essentially skips over the element and does not include it in the array. If nothing passes the test, an empty array is returned. For more information on the parameters for this function, skip back to the beginning of the Advanced Methods section!

Array.filter(element => {
   // do something
   element > 6
})

`join`: Join all the elements from an array to a string (non-destructive)

join creates and returns a string by concatenating, or joining, all of the elements of the array it was called on. By default the elements are separated by commas, however you can specify what you want to join/separate the elements by. On the other hand, if there is only one element in the array, the single item will be returned as a string without separators, and if there are no elements, an empty string is returned.

As mentioned, including an argument for the separator parameter is optional if you want the elements to be joined with a comma. Passing in an empty string as the argument will result in the elements joined without any characters/separators. Otherwise, the parameter is what you want to separate each pair of adjacent elements of the array for the returned string. If necessary, the separator is converted to a string.

Array.join()

`map`: Creates a new array with the results of a callback function (non-destructive)

map takes in a callback function that is called once for every element of the array it is called on. Each time the callback is executed, it returns the value into the new array, which is returned at the end. That said, if you do not use the returned (new) array and/or do not return a value from the callback, using the map method is considered anti-pattern. Instead you should use the forEach method or a for loop. For more information on the parameters for this function, skip back to the beginning of the Advanced Methods section!

Array.filter(element => {
   // do something
   element * 2
})

`find`: Return the value of the first element that satisfies the provided function (non-destructive)

The find method only returns the first value of the element that satisfies the callback (test) function. If no element passes the test, the find method will return undefined. That said, if you want to return the index of the element instead of its value, you can use the findIndex method instead. For more information on the parameters for this function, skip back to the beginning of the Advanced Methods section!

Array.find(element => {
   // do something
   element > 6
})

`forEach`: Loop over an Array (non-destructive)

Similar to a for loop, forEach executes a callback function once for each element in the array. While the forEach method will not mutate the array it was called on, it is possible for the callback function to mutate it. That said, the forEach method expects a synchronous function, always returns undefined, and is not chainable. Therefore, the typical use case is to execute side effects at the end of a chain. For more information on the parameters for this function, skip back to the beginning of the Advanced Methods section!

Array.forEach(element => console.log(element))

Fun Methods

Now, time for some “fun” methods! The methods we will cover here are: toString, includes, fill, indexOf, and findIndex.

`toString`: Returns a string representing the array and its elements (non-destructive)

Like its name, the toString method turns the array’s elements it was called on to a string. To be more specific, this method joins the array and returns one string containing each array element separated by commas.

Fun fact: JavaScript calls the toString method automatically when an array is to be represented as a text value or when an array is referred to in a string concatenation.

Array.toString()

`includes`: Returns a boolean if a value exists in an array (non-destructive)

includes determines whether an array includes a certain value among its entries, returning true or false as appropriate. It does this by checking each element for equality with the value rather than using a testing callback function. That said, if you need to find if any element satisfies a provided testing callback function, you can use the some method.

The argument you must pass in is the value you want the method to search for; keep in mind when comparing strings and characters, includes is case-sensitive. The optional second argument is the index to start searching for the value and by default is zero. That said, if the index passed in is greater than or equal to the length of the array, false is returned and the array will not be searched. On the other hand, if the index is negative the method uses the absolute value of it as the number of elements from the end of the array at which to start the search

Array.includes(searchValue)

`fill`: Fills all the elements of an array with a static value (destructive)

The fill method changes all elements in an array to a static value, from a start index to an end index. It then returns the modified array with the filled values.

There are three parameters however only the first one is required. The first argument you must pass in is the value to fill the array with. It’s important to know that all of the elements in the array will be this exact value. The other two optional parameters are for the start index, default is zero, and the end index, default is array.length.

Array.fill(staticValue)

indexOf & findIndex: Find the index of an item in the Array (non-destructive)

Similar to each other in that both return the first index that satisfies a condition. However, while findIndex is based on the element that satisfies a testing callback function, indexOf checks each element for equality with the value. Additionally, -1 is returned by indexOf if the element you are searching for is not present, whereas -1 is returned by findIndex if nothing satisfies the callback. That said, if you need to find if any element satisfies the provided testing function, you can use the some method.

findIndex has the same parameters detailed in the beginning of the Advanced Methods section. On the other hand, indexOf takes in an argument for the element to search for and optionally the index to start searching for. If you include the second argument of the index to start searching and the index is greater than or equal to the array's length, -1 is returned, which means the array will not be searched.

Note:

Array.indexOf(searchValue)
Array.indexOf(searchValue, startIndex)

Array.findIndex(element => {
   // do something
   element === "cat"
})

Conclusion

Congratulations! I declare you “master of JavaScript arrays and (most) array methods”!

But seriously though, this was a lot of information and I hope you’ll be able to refer to it in the future! Here are some key takeaways, as well as a reminder of what methods we covered:

Arrays organize their items sequentially and have built-in methods that allow you to easily lookup and add/remove information based on its position.
JavaScript arrays are special type of object and unlike non-scripting languages, are dynamic
To create arrays you can use the array literal, new constructor, or of method
Additionally, you can copy, concatenate arrays, and convert a string into an array by using the spread operator
Basic methods about adding, removing, or copying an array: pop, push, shift, unshift, splice, slice
Advanced methods to merge: reduce, concat, flat, join
Advanced methods do something based on a callback: sort, filter, map, find, forEach
Fun methods that have to do with the value or index: includes, indexOf, findIndex
Fun methods to know: toString, fill

If you made it to the end thank you so much for reading, I hope you found it useful! I recommend checking out my friend Megan's When to Use these String Methods in JavaScript, for a similar post on String methods. And don't forget about my collaboration post with Megan that covers the crossovers between Strings and Arrays!

Resources

From String to Array to String

Waverley Leung — Fri, 23 Apr 2021 20:27:00 +0000

About Writers

Hello everyone!

This is Waverley and Megan! We are both tech enthusiasts and graduated from Flatiron School recently. Both of us enjoy writing blogs to help other programmers learn and we learn from writing as well (win-win!). This will be our first time writing blogs on dev.to and collaborating on a series with each other, and we are so excited to create content for you all! Feedback is appreciated as we continue to navigate this process 🙏

When we first decided to collaborate we came up with a lot of topics to write about. However, as we are both currently in our job search and as bootcamp graduates, we wanted to work on something that will help us now and others in the future. Ultimately, we decided to have this series focus on data structures and algorithms, something we both feel is important to know but not exactly the easiest to understand.

Also, check out our Medium blogs for more of our work:

Intro

Today, we are going to talk about converting array to string, and vice versa. This is one of the commonly seen strategies that is used when solving string-and-array-related coding questions.

Before we get started, if you are interested in knowing array methods, here's All About JavaScript Arrays & Array Methods! by Waverley; and for string methods, here's When to Use these String Methods in JavaScript by Megan.

Intro
From Array to String
- toString()
- join()
From String to Array
- split()
- Array.from()
- Object.assign([], string)
Bonus
- Spread Operator
Conclusion

From Array to String

Something that we often need to do is convert an array to a string. Thankfully JavaScript has two built-in methods to accomplish this: toString() and join().

`toString()`: Returns a string representing the array and its elements (non-destructive)

Like its name, the toString() method turns the array’s elements it was called on to a string. To be more specific, this method joins the array and returns one string containing each array element separated by commas.

Fun fact: JavaScript calls the toString method automatically when an array is to be represented as a text value or when an array is referred to in a string concatenation.

const array1 = [1, 2, 'a', '1a'];
console.log(array1.toString());
// "1,2,a,1a"

`join()`: Join all the elements from an array to a string (non-destructive)

join() creates and returns a string by concatenating, or joining, all of the elements of the array it was called on. By default the elements are separated by commas, however you can specify what you want to join/separate the elements by. On the other hand, if there is only one element in the array, the single item will be returned as a string without separators, and if there are no elements, an empty string is returned.

Otherwise, the parameter is what you want to separate each pair of adjacent elements of the array for the returned string. If necessary, the separator is converted to a string.

let joinArray = ['Wind', 'Water', 'Fire'];
joinArray.join();      // 'Wind,Water,Fire' b/c no separator so joined with commas and no spaces
joinArray.join(“, “);  // 'Wind, Water, Fire' b/c separator is comma and space
joinArray.join(“ + “); // 'Wind + Water + Fire' b/c separator is space, plus sign, space
joinArray.join(“”);    // 'WindWaterFire' b/c separator is an empty string

Back to the Table of Contents

From String to Array

`split()`

As mentioned above, we can join string from array. We can also split string to array. Here, we are going to utilize the join() example to see the alternative results from above.

let splitToArray = 'Wind, Water, Fire';
splitToArray.split('') 
/* [
     'W', 'i', 'n', 'd', ',',
     ' ', 'W', 'a', 't', 'e',
     'r', ',', ' ', 'F', 'i',
     'r', 'e'
   ], no separators
*/
splitToArray.split(' ') 
// [ 'Wind,', 'Water,', 'Fire' ], split by the whitespaces
splitToArray.split(',') 
// [ 'Wind', ' Water', ' Fire' ], split by commas
// As you can see there're still whitespaces in front of each element
// To solve this, we can do the following:
splitToArray.split(', ')
// [ 'Wind', 'Water', 'Fire' ], split by commas and one additional whitespace

This method is probably the most common way to split a string to an array and join afterwards.

Most of the time, when we want to apply array methods to a given string, this is a go-to method to do so. For instance, if we want to reverse a string:

let example = 'JavaScript';

function reverse(str) {
  return str.split('').reverse().join('');
}

// In comparison to:
function reverse(str) {
  let reversed = '' // having to create a new string takes space
  for (let char of string) {
    reversed = char + reversed
  }
  return reversed;
}

Unless your interviewer specifies reverse() method is not allowed to be used, using the split() and join() method would help create a more readable, cleaner code. Also, since reverse() is not a string method, this is where we can utilize our array method in this case.

Palindrome is also another common question which you can make use of the split() and join()

`Array.from(string)`

There are two ways you can use Array.from(). Either you want to modify and create a new shallow-copied array OR drumroll please 🥁🥁🥁 converting string to array.

// To modify an array (Not the focus of this section)
Array.from([1, 2, 3, 4, 5], x => x * 2)
// [ 2, 4, 6, 8, 10 ]

// Convert string to array
Array.from('JavaScript')
['J', 'a', 'v', 'a', 'S', 'c', 'i', 'p', 't']

Remember, these are just some suggestive ways of converting string to array.
According to this article, using the same reversed example we have above, the runtime of using String.prototype.split() is way faster than using Array.from().
But you know, at least we know Array.from() is one of the possible ways to convert string to array!

`Object.assign([], string)`

You probably heard of Object.keys(), Object.entries() which would return a new array. What about Object.assign()?
Similar deal!
According to MDN, the definition of Object.assign()

The Object.assign() method copies all enumerable own properties from one or more source objects to a target object. It returns the target object.

Object.assign() takes two arguments: target and source. In our case, our target is an empty array [] and our source is the given string (which is an enumerable/ can be iterated object).

const str = "foo";
Object.assign([], str) // ['f', 'o', 'o']

Yay! It works... on the surface... If you move this to TypeScript...

✋🏻PAUSE✋🏻
For those who are not familiar with TypeScript, don't worry. Here's a quick breakdown. You don't have to fully understand TypeScript. All you have to know is that TypeScript is a superset of JavaScript. Most of the time, variables are assigned to a primitive data type in advance.

// In JS
const num = 1;

// In TS
const num : number = 1;

Cool thing about using TypeScript is that you would also see the variable type by hovering over the variable.

(Screenshot Credit: CodeCademy -- Learn TypeScript course)

Capiche? Hopefully you got the gist of it. Back to the topic...

If you move this to TypeScript, the type of this new copied array does not return as an array of string. 😱
If we look at other methods we mentioned above:

const str = 'foo';

const split = str.split('');
const from = Array.from(str);

Feel free to copy and paste the code to the playground and hover over split and from.
They both return split: string[] and from: string[]. (string[] means array of strings.)

However, when you hover over const obj = Object.assign([], str). It returns...

obj : never[] & "foo", a.k.a. it is never an array but a string.

Isn't that interesting? 😮 (thanks to our resource)

Although we have 3 ways to convert strings to array, including the spread operator (will be explained in the Bonus Section below), it seems like split() is the best way to do so!

Back to the Table of Contents

Bonus

Spread Operator

While the spread operator (...) is not specific to arrays, it is something helpful to know and use!

From MDN, the spread operator:

allows an iterable such as an array expression or string to be expanded in places where zero or more arguments (for function calls) or elements (for array literals) are expected, or an object expression to be expanded in places where zero or more key-value pairs (for object literals) are expected.

In other words, essentially the spread operator takes each of the elements inside of the passed in object or array and adds it to the array it is being added to.

As a result, it is often used when all elements from an object or array need to be included in another list of some kind; typical use cases include copying arrays or concatenating an array to the end of an existing array. However, specifically for copying an array, the spread operator goes one level deep. Meaning that if you spread an array into another array, the array it was spread into will not be nested.

Furthermore, it’s important to know that you cannot spread objects into an array or an array into an object. This is because objects alone are not iterable. However, when used in an array or with iterating functions (such as map or reduce), they become iterable.

Under the hood, when the merging occurs 2 objects together with the spread operator, it is assumed that another iterating function is used. On the other hand, if you spread a string into an array, it will create an array with each char in the string.

// general example
let elements = [1, 2, 3]
let newElement = 4

let constructorArray = new Array(newElement, ...elements)
// [4, 1, 2, 3]

let literalArray = [new element, ...elements]
// [4, 1, 2, 3]

// copying an array- showing how the spread operator does not nest
let a = [[1], [2], [3]]
let b = [...a]

console.log(a) // [[1], [2], [3]]
console.log(b) // [[1], [2], [3]]

b.shift().shift()

console.log(a) // [[], [2], [3]]
console.log(b) // [[2], [3]]

// cannot spread an object into an array
let obj = {'key1': 'value1'}
let array = [...obj]; // TypeError: obj is not iterable

// spreading a string into an array
let test = [..."hello", ...“world”]
console.log(test) // ["h", "e", "l", "l", "o", "w", "o", "r", "l", "d"]

Before You Go...

Let's conclude what we have discussed!

From Array to String, we have...

toString()
join()

From String to Array, we have...

split()
Assign.from()
Object.assign([], string)

Last but not least, spread operator (...) can be used to convert array to string, and vice versa.

Hope you enjoy our first collab article and please give us feedback if you have!

Back to the Table of Contents

Resources:

String <=> Array
- 4 Ways to Convert String to Character Array in JavaScript
- How to convert an Array to a String in JavaScript
Array
- All About JavaScript Arrays & Array Methods! (by Waverley)
String
- When to Use these String Methods in JavaScript (by Megan)
MDN

Nevertheless, Waverley Coded

Waverley Leung — Tue, 30 Mar 2021 16:40:45 +0000

A year ago this month I decided to transition into tech. My journey so far has been wonderful and eye-opening, and I’ve met so many amazing and inspiring people who I otherwise never would have crossed paths with. Thinking about the Waverley of March 2019 who decided to take the plunge and the Waverley of today, I can’t help but reflect on how much I’ve grown in this time and be grateful to all of the people who have supported me.

In honor of this anniversary and to thank everyone who have come before me and who will come after, I leave this piece of Waverley of March 2021 here 💞

Two important lessons:

“Plus Est En Vous”

A huge reason why I didn’t make the transition to tech earlier was because I listened to what other people said and limited myself to their expectations. I wasn’t afraid of exceeding their expectations (which in hindsight isn’t a reliable goal), but I was afraid of exceeding expectations that they didn’t want me to exceed. Constantly being told I’m “too intelligent”, “thinking too much”, “not pushing myself enough”, among other things. As a result, anything that would make me “more intelligent” I ignored, instead pushing myself to work harder to be seen more as what they wanted. Every time I doubted or questioned what I was doing, I would think about what they said I should want and be. I internalized them, thinking they were what I wanted and what was needed of me. Reality is, I put myself in a box. Therefore, this past year taught me to live based on my expectations of myself and grow by challenging those expectations, not live based on expectations other people put on me. To have faith and believe in myself.

Collaboration = Communication

Ultimately I’ve learned that the difference between working with others and true collaboration is that one can’t happen without communication. While there are details in between, when I think of collaboration I think of a positive, supportive environment where teammates are constantly learning (from each other and through the work itself), communicating with empathy, open to discussion, and are excited to work. That means when you don’t know or understand something, say so. But, that also means that there needs to be space for you to say it comfortably and not feel ashamed for it. For the person who hears the “I don’t know” to empathize and try to help in whatever capacity they can. On the other hand, when you see someone on your team struggling but aren’t saying anything, it means to offer your help anyway or send them a resource. If someone is dealing with everyday life issues, it means so much to know that your team has your back and remind you that you’re not just a worker.

Especially during COVID where we’re all working from home and meeting virtually, it means being able to be able to communicate this not only verbally but written as well. Remember that it’s not just what you’re saying, but how you’re saying it. Even though with words on a screen you can’t hear how the words are being said, being thoughtful with your word choice, emojis, gifs, and reactions. If despite all that your words are still misinterpreted by the other party, you can still communicate that it wasn’t your intention, elaborate, and say what you mean again. Other times, you might say something that only later on, you realize is wrong. Have the courage and humility to apologize, and take the next step to do your best to educate yourself and learn from the experience.

I could go on more, but in my opinion that’s why collaboration can’t happen without good, effective communication. If you can’t hear/talk to your teammates, how can you really collaborate?

Two things I want to work on:

Setting boundaries

This ties into advocating for myself and reminding myself to remember what I really want. Now that I’m not limiting myself based on other people, I’m embracing the freedom that brings. There’s so much I want to learn and so many wonderful opportunities out there to experience. However, even though there’s so much that I want to do, I also need to remember what my dream is and have that ground me. That starts with setting boundaries on how much I let everything take up space time-wise, emotionally and mentally. Reminding myself to be honest that I can’t do everything, to be grateful for the opportunities that come my way but I don’t always have to say “yes” to them, and to communicate my boundaries to the people they affect. I’m still working on this, so I can’t give much insight or advice, but I hope that by next year I’ll have something new to share.

Cultivating and deepening positive, supportive relationships with people who push me to be my best self

Growing up I was often the “shy quiet” kid. I was happy making other people smile or laugh, but I didn’t need to be surrounded by people. Often you’d find me lost in my own little world. But when I’d come back to earth, I’d be alone. I didn’t expect anyone to wait for me, and all I would have to do is see the person the next day or call/text them and everything would be fine. But honestly, after a while it became harder and harder to do because life goes on.

I like to believe the people I’m with are always looking out for my best interest, but that’s sadly not always the case. I’ve had a lot of relationships with people who kept me in the same place. When I was upset they would comfort me, which I appreciated. But sometimes I was wrong, and when I would be right I wouldn’t take any further action. Not realizing this pattern for years I kept making the same decisions, the same mistakes and the cycle would repeat. These experiences made me realize that I want to be in relationships that push me to be my best self, and I want to reciprocate and do this for others as well.

Even though I have never met my cohort from Flatiron School or my team from The Collab Lab in person, knowing that I have a community to turn to means a lot. To know that I have people I can turn to for advice, to celebrate wins, to share worries, and are willing to tell me the honest hard truth when I need it, is the world to me. I always appreciate when they reach out to check in on me when I’ve been in my little world for too long. On the flip side, contributing to these communities is such an amazing feeling as well; realizing that by sharing my thoughts and knowledge I can help people. While I continue to navigate what my introverted tendencies mean for me to socialize and relationships in general, I hope that in the next year I will contribute to more communities, make new friends, and stay in touch with those dear to me.

Someone told me right after I graduated college that your twenties are when you finally start to learn about yourself after going through years of school, education, and basically being told what to do your whole life. I replied with a polite smile and agreed, but I naively thought that didn’t apply to me. I mean, what does it even mean to “learn about yourself”? I’ve been myself my whole life, how could I possibly not know who I am? In the months leading to my graduation, I already figured out my plan and knew what I wanted. I knew who I was.

How wrong my fresh out of college self was; it took a career transition less than two years after I graduated to realize it. I’m grateful for this new journey in more ways than one, and I’m excited for what’s ahead and to learn more about who I am. Thank you for reading this, for those who have supported me, and for everyone who comes after; I hope that this piece of my story helps you wherever you are in your journey.

Special shoutout to The Code Benders, The Collab Lab, and the larger Flatiron School community. Super special shoutout to Sylwia Vargas for encouraging me to share my story!

Cover image: Photo by Gia Oris on Unsplash

DEV Community: Waverley Leung

Big-O Notation from a Non-CS Perspective

Introduction

What does it mean by brute force and optimized solution?

Complexity Comparison

Constant Time: O(1)

Logarithmic Time: O(log n)

Linear Time: O(n)

Linearithmic Time: O(n log n)

Quadratic Time: O(n2)

Exponential Time: O(2n)

Factorial Time: O(n!)

Conclusion

Resources

Everything JavaScript Arrays & Array Methods!

Table of Contents

Introduction

What are arrays?

How do we create arrays?

Methods

Basic Methods

splice: Remove an item by index position (destructive)

slice: Copy an Array (non-destructive)

Advanced Methods

reduce: Reduce to a single value (destructive)

sort: Sorts the elements (destructive)

concat: Merge arrays (non-destructive)

flat: Creates a new array with the sub-array elements concatenated into it (non-destructive)

filter: Returns all the elements that pass the test function provided (non-destructive)

join: Join all the elements from an array to a string (non-destructive)

map: Creates a new array with the results of a callback function (non-destructive)

find: Return the value of the first element that satisfies the provided function (non-destructive)

forEach: Loop over an Array (non-destructive)

Fun Methods

toString: Returns a string representing the array and its elements (non-destructive)

includes: Returns a boolean if a value exists in an array (non-destructive)

fill: Fills all the elements of an array with a static value (destructive)

indexOf & findIndex: Find the index of an item in the Array (non-destructive)

Conclusion

Resources

From String to Array to String

About Writers

Intro

Table of Contents

From Array to String

toString(): Returns a string representing the array and its elements (non-destructive)

join(): Join all the elements from an array to a string (non-destructive)

From String to Array

split()

Array.from(string)

Object.assign([], string)

Bonus

Spread Operator

Before You Go...

From Array to String, we have...

From String to Array, we have...

Resources:

Nevertheless, Waverley Coded

Two important lessons:

Two things I want to work on:

Quadratic Time: O(n²)

Exponential Time: O(2ⁿ)

`splice`: Remove an item by index position (destructive)

`slice`: Copy an Array (non-destructive)

`reduce`: Reduce to a single value (destructive)

`sort`: Sorts the elements (destructive)

`concat`: Merge arrays (non-destructive)

`flat`: Creates a new array with the sub-array elements concatenated into it (non-destructive)

`filter`: Returns all the elements that pass the test function provided (non-destructive)

`join`: Join all the elements from an array to a string (non-destructive)

`map`: Creates a new array with the results of a callback function (non-destructive)

`find`: Return the value of the first element that satisfies the provided function (non-destructive)

`forEach`: Loop over an Array (non-destructive)

`toString`: Returns a string representing the array and its elements (non-destructive)

`includes`: Returns a boolean if a value exists in an array (non-destructive)

`fill`: Fills all the elements of an array with a static value (destructive)

`toString()`: Returns a string representing the array and its elements (non-destructive)

`join()`: Join all the elements from an array to a string (non-destructive)

`split()`

`Array.from(string)`

`Object.assign([], string)`