loading...
Cover image for Learn Data Structure and Algorithm in JavaScript | Part 09

Learn Data Structure and Algorithm in JavaScript | Part 09

edisonnpebojot profile image Edison Pebojot(๐Ÿ‘จโ€๐Ÿ’ป) Updated on ใƒป14 min read


Prerequisite (โœ‹๐Ÿ˜)

If you're reading this article right now, please considered to read our Part 01: Big-O Notation, Part 02: JavaScript Unique Part, Part 03: JavaScript Numbers to Part 08: Recursion

Part Table of Contents Description
01 Big-O Notation By the end of this chapter, you will understand how to analyze an implementation of an algorithm with respect to both time (execution time) and space (memory consumed).
02 JavaScript Unique Parts Big-O is important for analyzing and comparing the efficiencies of algorithms. The analysis of Big-O starts by looking at the code, and, applying the rules, applying the rules is because to simplify the Big-O notation linear or quadratic rule is not enough.
03 JavaScript Numbers This part 3 will focus on JavaScript number operations, number representation, Number objects, common number algorithms, and random number generation.
04 JavaScript Strings This part 4 will focus on strings, JavaScript String object, and the String objectโ€™s built-in functions. You will learn how to access, compare, decompose, and search strings for commonly used real-life purposes. In addition, the chapter will explore string encoding, decoding, encryption, and decryption.
05 JavaScript Arrays As a JavaScript developer, you will use the array often; it is the most commonly used data structure. Arrays in JavaScript come with a lot of built-in methods. By the end of this part, you will understand arrays and choose the right method
06 JavaScript Object This part will focus on what JavaScript objects are, how they are declared, and how their properties can be changed. In addition, this part will cover how JavaScript classes are implemented using prototypal inheritance. Also this part will be short.
07 JavaScript Memory Management A variable takes up some memory. In C, the programmer allocate and deallocate memory manually. In contrast, modern JavaScript engines have garbage collectors that delete unused variables. However, there are pitfalls(unexpected) that developers can fall into(โ—) This part will show these unexpected and present techniques to help the garbage collector minimize the memory problems.
08 Recursion This part 8 introduces the concept of recursion and recursive algorithms(Remember they are different, we will discuss them later(๐Ÿ˜‰)). We will also discuss the definition of recursion and fundamental rules for recursive algorithms.
09 Sets This part focuses on the concepts of sets from both a mathematical definition and on the implementation. Also, Common set operations, as well as their implementations, are covered in great detail (๐Ÿ’ก).
10 Searching and Sorting This part 10 focuses on searching and sorting for arrays. By the end of this part 10, you will understand how to use sorting and searching algorithms for arrays. Also, this article is a bit complicated for beginners, so as much as possible the visual aids is your friend (๐Ÿ‘€). (๐Ÿ˜ƒ)
11 Hash Tables A hash table is a fixed-sized data structure in which the size is defined at the start. This part 11 explains how hash tables work, and the method of generating a unique key. By the end of this part 11, you will understand various hashing techniques and know how to implement a hash table. (๐Ÿ˜ƒ)
12 Stacks and Queues This part 12 covers stacks and queues(pronounce as kyooz (๐Ÿ”ˆ)) not (kwewe) okay? hehehe (๐Ÿ˜…); both are data structures used in the implementation of complex data structures. You'll learn what the stacks and queues are, how they're used, when they're used, and how to implement them (๐Ÿ˜ƒ) Let's go! (๐Ÿ”ฅ๐Ÿ”ฅ๐Ÿ”ฅ)
13 Linked Lists A linked list is a data structure in which each node (or element) points to another node. Unlike arrays, which have a fixed size, a linked list is a dynamic data structure. By the end of this part 13, you will understand how to implement and work with linked lists. And oh! (๐Ÿ˜ฎ) There are two types of linked lists: singly (โžก๏ธ) and doubly (โ†”๏ธ). Letโ€™s examine the singly linked list first.(๐Ÿ˜ƒ) Let's go! (๐Ÿ”ฅ๐Ÿ”ฅ๐Ÿ”ฅ)
14 Caching Caching is the process of storing data into temporary memory so that it can be easily retrieved for later use if it is required again. As an example, a database keeps data cached to avoid re-reading the hard drive, and a web browser caches web images to avoid re-downloading. In this part 14, two caching techniques will discussed: LFU and LRU caching.
15 Trees A general tree data structure is composed of nodes with children nodes. The top node is called the root node. This part 15 will explore different types of trees such as binary trees, binary search trees, and self-balancing binary search trees. First, this part 15 will cover what trees are and how they are structured. Then, it will cover methods of traversing(crossing or taking a zigzag path) the tree data structure in detail. Finally, you will learn about binary search trees and self-balancing binary search trees to understand how to store searchable data. (๐Ÿ˜ƒ)
16 Heaps A heap is an important data structure that returns the highest or lowest element in O(1) time. This part 16 will focus on explaining how heaps are implemented as well as how to work with them. One example is heap sort, which is a sorting algorithm based on heaps.
17 Graphs In this Part 17, you will learn graph basics, including fundamental terminology and graph types. The Part 17 will also cover working with these different graph types and methods of representing graphs in data structures. Finally, algorithms for traversing, searching, and sorting graphs are explored to solve problems such as finding the shortest path between two graph nodes. (๐Ÿ‘)
18 Advance Strings Part 18 will cover more complex string algorithms than covered in the previous section. Now that you have heard of certain other data models or structures, they should be easier to comprehend. Specifically, Part 18 will focus on string searching algorithms. (๐Ÿ˜‰)
19 Dynamic Programming Dynamic programming involves breaking down problems into their subproblems. Solving the subproblems and saving those results into memory to access them whenever a repeated problem needs to be solved, the algorithmic complexity decreases significantly (โฌ‡๏ธ). To explain dynamic programming, letโ€™s re examine the Fibonacci sequence that was discussed in Part 8. Then Part 19 will cover the rules of dynamic programming and walk you through some examples to make the concepts more concrete. (๐Ÿ˜‰)

Part 09: Sets (๐Ÿ˜ฑ ๐Ÿ”ฅ ๐Ÿ“)

Alt Text

This part focuses on the concepts of sets from both a mathematical definition and on the implementation. Also, Common set operations, as well as their implementations, are covered in great detail (๐Ÿ’ก). By the end of this part, you will understand how to use JavaScriptโ€™s native Set object to set operations. Note, this article is short, think of it as a preparation for the next part. (๐Ÿ˜‰)

Introducing Sets (๐Ÿ“๐Ÿ“)

Alt text

In laymanโ€™s terms, a set is a group of unordered unique (no duplicate) elements. For example, a set of integers may be: โฆƒ1,2,3,4โฆ„\lBrace 1, 2, 3, 4\rBrace . Within this, its subsets are:

โฆƒโฆ„,โฆƒ1โฆ„,โฆƒ2โฆ„,โฆƒ3โฆ„,โฆƒ4โฆ„,โฆƒ1,2โฆ„,โฆƒ1,3โฆ„,โฆƒ1,4โฆƒ,โฆƒ2,3โฆ„,โฆƒ2,4โฆ„,โฆƒ3,4โฆ„,โฆƒ1,2,3โฆ„,โฆƒ1,2,4โฆ„,โฆƒ1,3,4โฆ„,ย andย โฆƒ2,3,4โฆ„\lBrace \rBrace, \lBrace 1\rBrace, \lBrace 2\rBrace, \lBrace 3\rBrace, \lBrace 4\rBrace, \lBrace 1, 2\rBrace, \lBrace 1, 3\rBrace, \lBrace 1, 4\lBrace, \lBrace 2, 3\rBrace, \lBrace 2, 4\rBrace, \lBrace 3, 4\rBrace, \lBrace 1, 2, 3\rBrace, \lBrace 1, 2, 4\rBrace, \lBrace 1, 3, 4\rBrace, \space and \space \lBrace 2, 3, 4\rBrace

This is also similar from here(but this is not complete), we just assume this is what it looks like:

Alt Text

Set is natively supported in JavaScript as follows:

Example:

var exampleSet = new Set();

The native Set object has only one property: which is size property. This property is the number of elements within the set:

Example:

var exampleSet = new Set();
exampleSet.size

Execution:

var exampleSet = new Set(); exampleSet.size // Prints '0' because our set is empty /* Change 'new Set()' to 'new Set([1, 2, 3, 4])' and run again. See what happen? */

Set Operation (โž•โŒ...)

Alt Text

Rememeber: The set is a powerful data structure for performing checks(or checking for unique elements). This section will cover the following key operations: insertion, deletion, and contains.

Insertion (โžก๏ธ๐Ÿ“โฌ…๏ธ)

Set has one primary function: to check for uniqueness. Set can add items, but duplicates are not allowed. Here is an example:

Example:

var exampleSet = new Set();
console.log(exampleSet.add(1)); // exampleSet: Set {1}
console.log(exampleSet.add(1)); // exampleSet: Set {1}
console.log(exampleSet.add(2)); // exampleSet: Set {1, 2}

Execution:

var exampleSet = new Set(); console.log(exampleSet.add(1)); // exampleSet: Set {1} console.log(exampleSet.add(1)); // exampleSet: Set {1} console.log(exampleSet.add(2)); // exampleSet: Set {1, 2} // Notice that duplicate is not allowed in Sets

Notice that adding the duplicate element does not work for a set. As discussed in the introduction, insertion into a set occurs in constant time. Time Complexity: O(1).

Deletion (โŒ๐Ÿ“โŒ)

Set can also delete items from the set. Set.delete method returns a boolean type (true or false). Remember: If the element exists in Set and was deleted, it returns true, otherwise false. Here is an example:

Example:

var exampleSet = new Set();
console.log(exampleSet.add(1)); // exampleSet: Set {1}
console.log(exampleSet.delete(1)); // true
console.log(exampleSet.add(2)); // exampleSet: Set {2}

Execution:

var exampleSet = new Set(); console.log(exampleSet.add(1)); // exampleSet: Set {1} console.log(exampleSet.delete(1)); // true console.log(exampleSet.add(2)); // exampleSet: Set {2} // Notice that it returns 'true'. Why?

Remember: This is useful to delete items in constant time. Time Complexity: O(1).

Contains (๐Ÿ”Ž๐Ÿ“๐Ÿ”)

Set.has method does a O(1) lookup to check whether the element exists within the set. Here is an example:

Example:

var exampleSet = new Set();
console.log(exampleSet.add(1)); // exampleSet: Set {1}
console.log(exampleSet.has(1)); // true
console.log(exampleSet.has(2)); // false
console.log(exampleSet.add(2)); // exampleSet: Set {1, 2}
console.log(exampleSet.has(2)); // true

Execution:

var exampleSet = new Set(); console.log(exampleSet.add(1)); // exampleSet: Set {1} console.log(exampleSet.has(1)); // true console.log(exampleSet.has(2)); // false console.log(exampleSet.add(2)); // exampleSet: Set {1, 2} console.log(exampleSet.has(2)); // true // Notice that it returns 'true' and 'false'. Why?

Remember: This is useful to look for items in constant time. Time Complexity: O(1).

Other Utility Functions (๐Ÿ”ง๐Ÿ“)

Alt Text

In addition to the native supported set functions(or method), other essential operations(which is not native) are available; they are explored in this section. Let's go! (๐Ÿ”ฅ๐Ÿ”ฅ๐Ÿ”ฅ)

Intersection (โžก๏ธโŒโฌ…๏ธ)

First, the intersection. This function returns a set with common elements between two sets. Here is an example:

Example:

function intersectSets(setA, setB) {
    var intersection = new Set();
    for (var elem of setB) {
        if (setA.has(elem)) {
            intersection.add(elem);
        }
    }
    return intersection;
}
var setA = new Set([1, 2, 3, 4]),
    setB = new Set([2, 3]);
intersectSets(setA, setB); // Set {2, 3}

Execution:

function intersectSets(setA, setB) { var intersection = new Set(); for (var elem of setB) { if (setA.has(elem)) { intersection.add(elem); } } return intersection; } var setA = new Set([1, 2, 3, 4]), setB = new Set([2, 3]); intersectSets(setA, setB); // Set {2, 3} // Notice that it return '{2, 3}'. Why?

isSuperSet (๐Ÿ”Ž๐Ÿ“๐Ÿ”)

Second, is "SuperSet" or isSuperSet. This function checks whether a set is a superset(See on Wikipedia) of another. Here is an example:

Example:

function isSuperset(setA, subset) {
    for (var elem of subset) {
        if (!setA.has(elem)) {
            return false;
        }
    }
    return true;
}

var setA = new Set([1, 2, 3, 4]),
    setB = new Set([2, 3]),
    setC = new Set([5]);
console.log(isSuperset(setA, setB)); // true
console.log(isSuperset(setA, setC)); // false

Execution:

function isSuperset(setA, subset) { for (var elem of subset) { if (!setA.has(elem)) { return false; } } return true; } var setA = new Set([1, 2, 3, 4]), setB = new Set([2, 3]), setC = new Set([5]); console.log(isSuperset(setA, setB)); // true // It's 'true' because setA has all elements that setB does console.log(isSuperset(setA, setC)); // false // It's 'false' because setA does not contain 5 which setC contains

Union (๐Ÿ…ฐ๏ธ๐Ÿ…ฑ๏ธ๐Ÿ†Ž)

Third, the union. It combines the elements from both sets. This function returns a new set with both elements without duplicates. Here is an example:

Example:

function unionSet(setA, setB) {
    var union = new Set(setA);
    for (var elem of setB) {
        union.add(elem);
    }
    return union;
}
var setA = new Set([1, 2, 3, 4]),
    setB = new Set([2, 3]),
    setC = new Set([5]);
unionSet(setA, setB); // Set {1, 2, 3, 4}
unionSet(setA, setC); // Set {1, 2, 3, 4, 5}

Execution:

function unionSet(setA, setB) { var union = new Set(setA); for (var elem of setB) { union.add(elem); } return union; } var setA = new Set([1, 2, 3, 4]), setB = new Set([2, 3]), setC = new Set([5]); unionSet(setA, setB); // Set {1, 2, 3, 4} unionSet(setA, setC); // Set {1, 2, 3, 4, 5}

Difference (๐Ÿ“โž–๐Ÿ“)

Finally and the last, the difference(which is in Mathematics is 'minus/substract'). This function implements the difference operation by making use of the native delete method. Here's an example:

Example:

function differenceSet(setA, setB) {
    var difference = new Set(setA);
    for (var elem of setB) {
        difference.delete(elem);
    }
    return difference;
}
var setA = new Set([1, 2, 3, 4]),
    setB = new Set([2, 3]);
differenceSet(setA, setB); // Set {1, 4}

Execution:

function differenceSet(setA, setB) { var difference = new Set(setA); for (var elem of setB) { difference.delete(elem); } return difference; } var setA = new Set([1, 2, 3, 4]), setB = new Set([2, 3]); differenceSet(setA, setB); // Set {1, 4} // Notice that it returns '{1, 4}'. Why?

Summary (๐Ÿ“š)

Alt text

A set is a fundamental data structure to represent unique elements. The Set object supports insertion, deletion, and contains, which all have a time complexity of O(1). Other fundamental set operations such as intersection, difference, union, and superset are implemented. These will enable you to implement algorithms with fast uniqueness checks in future parts. So be ready. Anyway, the table below summarizes the set operations:

Operation Function(Method) Name Description
Insertion Set.add() Native JavaScript. Adds the element to the set if itโ€™s not already in the set.
Deletion Set.delete() Native JavaScript. Deletes the element from the set if itโ€™s in the set.
Contains Set.has() Native JavaScript. Checks whether an element exists within in the set.
Intersection (AโˆฉB) intersectSets() Returns a set with common elements of set A and set B
Union (AโˆชB) unionSet() Returns a set with all elements of set A and set B.
Difference (A-B) differenceSet() Returns a set with all elements.
Table 9-1. Set Summary

Challenge (๐Ÿ˜ค๐Ÿ”ฅ๐Ÿ‘Š)

Alt text

These exercises on Sets cover varying problems to help solidify your knowledge gained from this part. Don't forget to post your answer in the comment(with explanation): (๐Ÿ˜ƒ)


USING SETS TO CHECK FOR DUPLICATES IN AN ARRAY

Problem: Check whether there are any duplicates in an array of integers using sets. By converting the array into a set, the size of the set can be compared with the length of the array to check for duplicates easily. See the example output:

Example:

checkDuplicates([1, 2, 3, 4, 5]); // Must print 'false'
checkDuplicates([1, 1, 2, 3, 4, 5]); // Must print 'true'

Time Complexity: O(n)O(n)
Space Complexity: O(n)O(n)

Answer: (Remember to put your answer in the comment)


RETURNING ALL UNIQUE VALUES FROM SEPARATE ARRAYS

Problem: Given two integer arrays with some of the same values, return one array that has all the unique elements from both of the original arrays. Using sets, unique elements can be stored easily. By concatenating two arrays and converting them to a set, only unique items are stored. Converting the set to an array results in an array with unique items only. See the example output:

Example:

uniqueList([1, 1, 2, 2], [2, 3, 4, 5]); // [1,2,3,4,5]
uniqueList([1, 2], [3, 4, 5]); // [1,2,3,4,5]
uniqueList([], [2, 2, 3, 4, 5]); // [2,3,4,5]

Time Complexity: O(n+m)O(n + m )
Space Complexity: O(n+m)O(n + m )

Answer: (Remember to put your answer in the comment)


Up Next๐Ÿ‘‰ Part 10: Searching and Sorting Algorithm (๐Ÿ”ฅ๐Ÿ”ฅ) (July 24-25, 2020)


Take a look! (๐Ÿ‘€๐Ÿ‘ˆ๐Ÿ˜…)

Take a look or a look at Part 10 to refresh your mind. As the next section, there's a bit of depth to the algorithm. First of all, we're going to dive into principle.

Part 10: Searching and Sorting Algorithm

Searching refers to iterating over the data structureโ€™s elements to retrieve some data. Sorting refers to putting the data structureโ€™s elements in order. The searching and sorting algorithms are different.

Linear Search

A linear search works by going through each element of the array one index after another

Binary Search

Binary search is a searching algorithm that works on sorted data. binary searches check the middle value to see whether the desired value is greater or smaller than it. If the desired value is smaller, this algorithm can search the smaller parts, or it can search the bigger parts if the desired value is bigger.

(To be continued) (๐Ÿ”š)

Alt Text

Discussion

markdown guide