JavaScript Arrays

Introducing Arrays

Arrays are one of the most fundamental data structures. If you have ever programmed before, you’ve most likely used an array.

1 var array1 = [1,2,3,4];

For any data structure, developers are interested in time and space complexity associated with the four fundamental operations: access, insertion, deletion, and search. (For a review of Big-O notations, please refer to Chapter 1.)

Insertion

Insertion means adding a new element inside a data structure. JavaScript implements array insertion with the .push(element) method . This method adds a new element at the end of the array.

1 var array1 = [1,2,3,4];

2 array1.push(5); //array1 = [1,2,3,4,5]

3 array1.push(7); //array1 = [1,2,3,4,5,7]

4 array1.push(2); //array1 = [1,2,3,4,5,7,2]

The time complexity of this operation is O(1) in theory. It should be noted that, practically, this depends on the JavaScript engine that runs the code. This applies to all natively supported JavaScript objects.

Deletion

JavaScript implements array deletion with the .pop() method . This method removes the last-added element of the array. This also returns the removed element.

1 var array1 = [1,2,3,4];

2 array1.pop(); //returns 4, array1 = [1,2,3]

3 array1.pop(); //returns 3, array1 = [1,2]

The time complexity of .pop is O(1) similarly to .push.

Another way to remove an element from an array is with the .shift() method . This method will remove the first element and return it.

1 array1 = [1,2,3,4];

2 array1.shift(); //returns 1, array1 = [2,3,4]

3 array1.shift(); //returns 2, array1 = [3,4]

Access

Accessing an array at a specified index only takes O(1) because this process uses that index to get the value directly from the address in memory. It is done by specifying the index (remember that indexing starts at 0).

1 var array1 = [1,2,3,4];

2 array1[0]; //returns 1

3 array1[1]; //returns 2

Iteration

Iteration is the process of accessing each of the items contained within a data structure. There are multiple ways to iterate through an array in JavaScript. They all have a time complexity of O(n) since the iteration is visiting n number of elements.

for (Variables; Condition; Modification)

for is the most common method of iteration. It is most often used in this form:

1 for ( var i=0, len=array1.length; i<len; i++ ) {

2 console.log(array1[i]);

3 }

The previous code simply means initialize the variable i, check whether the condition is false before executing the body (i<len), and then modify (i++) until the condition is false. Similarly, you can use a while loop. However, the counter will have to be set outside.

1 var counter=0;

2 while(counter<array1.length){

3 // insert code here

4 counter++;

5 }

You can implement an infinite loop using a while loop, as shown here:

1 while(true){

2 if (breakCondition) {

3 break;

4 }

5 }

Similarly, a for loop can implement an infinite loop by not setting a condition, as shown here:

1 for ( ; ;) {

2 if (breakCondition) {

3 break

4 }

5 }

for ( in )

Another way to iterate a JavaScript array is to call the indices one by one. The variable specified before in is the index of the array, as follows:

1 var array1 = ['all','cows','are','big'];

2

3 for (var index in array1) {

4 console.log(index);

5 }

This prints the following: 0,1,2,3.

To print the content, use this:

1 for (var index in array1) {

2 console.log(array1[index]);

3 }

This printsall, cows, are, and big.

for ( of )

The variable specified before of is the element (the value) of the array, as follows:

1 for (var element of array1) {

2 console.log(element);

3 }

This prints out all, cows, are, and big.

forEach( )

The big difference between forEach and other methods of iteration is that forEach cannot break out of the iteration or skip certain elements in the array. forEach is more expressive and explicit by going through each element.

1 var array1 = ['all','cows','are','big'];

2

3 array1.forEach( function (element, index){

4 console.log(element);

5 });

6

7 array1.forEach( function (element, index){

8 console.log(array1[index]);

9 });

Both print all, cows, are, and big.

Helper Functions

The following sections discuss other commonly used helper functions for processing. In addition, working with arrays will be covered.

.slice(begin,end)

This helper function returns a portion of an existing array without modifying the array. .slice() takes two parameters: the beginning index and the ending index of the array.

1 var array1 = [1,2,3,4];

2 array1.slice(1,2); //returns [2], array1 = [1,2,3,4]

3 array1.slice(2,4); //returns [3,4], array1 = [1,2,3,4]

If only the beginning index is passed, the ending will be assumed to be the maximum index.

1 array1.slice(1); //returns [2,3,4], array1 = [1,2,3,4]

2 array1.slice(1,4); //returns [2,3,4], array1 = [1,2,3,4]

If nothing is passed, this function simply returns a copy of the array. It should be noted that array1.slice() === array1 evaluates to false. This is because although the contents of the arrays are the same, the memory addresses at which those arrays reside are different.

1 array1.slice(); //returns [1,2,3,4], array1 = [1,2,3,4]

This is useful for copying an array in JavaScript. Remember that arrays in JavaScript are reference-based, meaning that if you assign a new variable to an array, changes to that variable apply to the original array.

1 var array1 = [1,2,3,4],

2 array2 = array1;

3

4 array1 // [1,2,3,4]

5 array2 // [1,2,3,4]

6

7 array2[0] = 5;

8

9 array1 // [5,2,3,4]

10 array2 // [5,2,3,4]

The changing element of array2 changed the original array by accident because it is a reference to the original array. To create a new array, you can use .from().

1 var array1 = [1,2,3,4];

2 var array2 = Array.from(array1);

3

4 array1 // [1,2,3,4]

5 array2 // [1,2,3,4]

6

7 array2[0] = 5;

8

9 array1 // [1,2,3,4]

10 array2 // [5,2,3,4]

.from() takes O(n), where n is the size of the array. This is intuitive because copying the array requires copying all n elements of the array.

.splice(begin,size,element1,element2…)

This helper function returns and changes the contents of an array by removing existing elements and/or adding new elements.

.splice() takes three parameters: the beginning index, the size of things to be removed, and the new elements to add. New elements are added at the position specified by the first parameter. It returns the removed elements.

1 var array1 = [1,2,3,4];

2 array1.splice(); //returns [], array1 = [1,2,3,4]

3 array1.splice(1,2); //returns [2,3], array1 = [1,4]

This example demonstrates removal. [2,3] was returned because it selected two items starting from an index of 1.

1 var array1 = [1,2,3,4];

2 array1.splice(); //returns [], array1 = [1,2,3,4]

3 array1.splice(1,2,5,6,7); //returns [2,3],array1 = [1,5,6,7,4]

Anything (any object type) can be added to the array. This is the beauty (and odd part) of JavaScript.

1 var array1 = [1,2,3,4];

2 array1.splice(1,2,[5,6,7]); //returns [2,3], array1 = [1,[5,6,7],4]

3 array1 = [1,2,3,4];

4 array1.splice(1,2,{'ss':1}); //returns [2,3], array1 = [1,{'ss':1},4]

.splice() is, worst case, O(n). Similarly to copying, if the range specified is the whole array, each n item has to be removed.

.concat()

This adds new elements to the array at the end of the array and returns the array.

1 var array1 = [1,2,3,4];

2 array1.concat(); //returns [1,2,3,4], array1 = [1,2,3,4]

3 array1.concat([2,3,4]); //returns [1,2,3,4,2,3,4],array1 = [1,2,3,4]

.length Property

The .length property returns the size of the array. Changing this property to a lower size can delete elements from the array.

1 var array1 = [1,2,3,4];

2 console.log(array1.length); //prints 4

3 array1.length = 3; // array1 = [1,2,3]

Spread Operator

The spread operator, denoted by three periods (...), is used to expand arguments where zero arguments are expected.

1 function addFourNums(a, b, c, d) {

2 return a + b + c + d;

3 }

4 var numbers = [1, 2, 3, 4];

5 console.log(addFourNums(...numbers)); // 10

Both the Math.max and Math.min functions take an unlimited number of parameters, so you can use the spread operator for the following operations.

To find the maximum in an array, use this:

1 var array1 = [1,2,3,4,5];

2 Math.max(array1); // 5

To find the minimum in an array, use this:

1 var array2 = [3,2,-123,2132,12];

2 Math.min(array2); // -123

Exercises

All the code for the exercises can be found on GitHub.¹

Find Two Array Elements in an Array That Add Up to a Number

Problem: Given the array arr, find and return two indices of the array that add up to weight or return -1 if there is no combination that adds up to weight.

For example, in an array like [1,2,3,4,5], what numbers add up to 9?

The answers are 4 and 5, of course.

The simple solution is to try every combination by having two for loops, as shown here:

1 function findSum(arr, weight) {

2 for (var i=0,arrLength=arr.length; i<arrLength; i++){

3 for (var j=i+1; j<arrLength; j++) {

4 if (arr[i]+arr[j]==weight){

5 return [i,j];

6 }

7 }

8 }

9 return -1;

10 }

This solution iterates through an array looking to see whether a matching pair exists.

Two for loops over n elements of the array yields a high time complexity. However, no extra memory was created. Similar to how time complexity describes the time required relative to input size, n, to finish the algorithm, the space complexity describes the additional memory needed for implementation. The space complexity, O(1), is constant.

Time Complexity: O(n²)

Space Complexity: O(1)

Let’s think about how to do this in linear time of O(n).

What if any previously seen array elements were stored and could be checked easily?

Here’s the input:

1 var arr = [1,2,3,4,5];

2 var weight = 9;

Here, 4 and 5 are the combination, and their indices are [3,4]. How could it be determined that a solution exists when 5 is visited?

If the current value is at 5 and the weight is 9, the remaining required weight is just 4 (9-5=4). Since 4 is shown before 5 in the array, this solution can work in O(n). Finally, to store the seen elements, use a JavaScript object as a hash table. The implementation and use of a hash table will be discussed in later chapters. Storing into and retrieving a JavaScript object property is O(1) in time.

1 function findSumBetter(arr, weight) {

2 var hashtable = {};

3

4 for (var i=0, arrLength=arr.length; i<arrLength; i++) {

5 var currentElement = arr[i],

6 difference = weight - currentElement;

7

8 // check the right one already exists

9 if (hashtable[currentElement] != undefined) {

10 return [i, hashtable[weight-currentElement]];

11 } else {

12 // store index

13 hashtable[difference] = i;

14 }

15 }

16 return -1;

17 }

Time Complexity: O(n)

Space Complexity: O(n)

Storing into a hash table and looking an item up from a hash table is only O(1). Space complexity has increased to O(n) to store the visited array indices inside the hash table.

Implement the Array.Slice() Function from Scratch

Let’s review what the .slice() function does.

.slice() takes two parameters: the beginning index and the last ending index of the array. It returns a portion of an existing array without modifying the array function arraySlice (array, beginIndex, endIndex).

1 function arraySlice(array, beginIndex, endIndex) {

2 // If no parameters passed, return the array

3 if (! beginIndex && ! endIndex) {

4 return array;

5 }

6

7 // If only beginning index is found, set endIndex to size

8 endIndex = array.length;

9

10 var partArray = [];

11

12 // If both begin and end index specified return the part of the array

13 for (var i = beginIndex; i < endIndex; i++ ) {

14 partArray.push(array[i]);

15 }

16

17 return partArray;

18 }

19 arraySlice([1 , 2 , 3 , 4 ], 1 , 2 ); // [2]

20 arraySlice([1 , 2 , 3 , 4 ], 2 , 4 ); // [3,4]

Time Complexity: O(n)

Space Complexity : O(n)

The time complexity is O(n) because all n items in the array must be accessed. Space complexity is also O(n) to hold all n items when copying the array.

Find the Median of Two Sorted Arrays of the Same Size

Recall that median in an even number of a set is the average of the two middle numbers. If the array is sorted, this is simple.

Here’s an example:

[1,2,3,4] has the median of (2+3)/2 = 2.5.

1 function medianOfArray(array) {

2 var length = array.length;

3 // Odd

4 if (length % 2 == 1) {

5 return array[Math.floor(length/2)];

6 } else {

7 // Even

8 return (array[length/2]+array[length/2 - 1])/2;

9 }

10 }

Now, you can iterate through both of the arrays and compare which is bigger to track the median. If the two arrays are the same size, the total size will be an even number.

This is because both two even numbers and two odd numbers add up to an even number. Please refer to Chapter 8 for more background.

Since both of the arrays are sorted, this function can be recursively called. Each time, it checks which median is greater.

If the second array’s median is greater, the first array is cut in half, and only the higher half is passed recursively.

If the first array’s median is greater, the second array is cut in half, and only the higher half is passed in as the first array for the next function call because the array2 parameter in the function must always be bigger than the array1 parameter. Finally, the size of the array represented as pos is required to check whether the size of the array is even or odd.

Here’s another example:

array1 = [1,2,3] and array2 = [4, 5, 6]

Here, the median of array1 is 2, and the median of array2 is 5. So, the median must be present within [2,3] and [4,5]. Since there are only four elements left, the median can be computed as follows:

max(arr1[0], arr2[0]) + min(arr1[1], arr2[1]) / 2;

1 function medianOfArray(array) {

2 var length = array.length;

3 // Odd

4 if (length % 2 == 1 ) {

5 return array[Math .floor(length / 2 )];

6 } else {

7 // Even

8 return (array[length / 2 ] + array[length / 2 - 1 ]) / 2 ;

9 }

10 }

11 // arr2 is the bigger array

12 function medianOfTwoSortedArray(arr1, arr2, pos) {

13 if (pos <= 0 ) {

14 return -1 ;

15 }

16 if (pos == 1 ) {

17 return (arr1[0] + arr2[0]) / 2 ;

18 }

19 if (pos == 2 ) {

20 return (Math .max(arr1[0], arr2[0]) + Math .min(arr1[1], arr2[1])) / 2 ;

21 }

22

23 var median1 = medianOfArray(arr1),

24 median2 = medianOfArray(arr2);

25

26 if (median1 == median2) {

27 return median1;

28 }

29

30 var evenOffset = pos % 2 == 0 ? 1 : 0 ,

31 offsetMinus = Math .floor(pos / 2 ) - evenOffset,

32 offsetPlus = Math .floor(pos / 2 ) + evenOffset;

33

34

35 if (median1 < median2) {

36 return medianOfTwoSortedArray(arr1.slice(offsetMinus), arr2.slice(offsetMinus), offsetPlus);

37 } else {

38 return medianOfTwoSortedArray(arr2.slice(offsetMinus), arr1.slice(offsetMinus), offsetPlus);

39 }

40 }

41

42 medianOfTwoSortedArray([1 , 2 , 3 ], [4 , 5 , 6 ], 3 ); // 3.5

43 medianOfTwoSortedArray([11 , 23 , 24 ], [32 , 33 , 450 ], 3 ); // 28

44 medianOfTwoSortedArray([1 , 2 , 3 ], [2 , 3 , 5 ], 3 ); // 2.5

Time Complexity: O(log₂(n))

By cutting the array size by half each time, logarithmic time complexity is achieved.

Find Common Elements in K-Sorted Arrays

1 var arr1 = [1, 5, 5, 10];

2 var arr2 = [3, 4, 5, 5, 10];

3 var arr3 = [5, 5, 10, 20];

4 var output = [5 ,10];

In this example with three arrays, k=3.

To do this, simply iterate over each array and count instances of every element. However, do not track repeated ones (5 and 5.5 should be counted once in one array iteration). To do this, check whether the last element is the same before incrementing. This will work only if it is sorted.

After all three arrays have been iterated, iterate through the hash table’s properties. If the value matches 3, it means that the number showed up in all three arrays. This can be generalized to k number of arrays by putting the k-loop check into another for loop.

1 function commonElements(kArray) {

2 var hashmap = {},

3 last, answer = [];

4

5 for (var i = 0 , kArrayLength = kArray.length; i < kArrayLength; i++ ) {

6 var currentArray = kArray[i];

7 last = null ;

8 for (var j = 0 , currentArrayLen = currentArray.length;

9 j < currentArrayLen; j++ ) {

10 var currentElement = currentArray[j];

11 if (last != currentElement) {

12 if (! hashmap[currentElement]) {

13 hashmap[currentElement] = 1 ;

14 } else {

15 hashmap[currentElement]++ ;

16 }

17 }

18 last = currentElement;

19 }

20 }

21

22 // Iterate through hashmap

23 for (var prop in hashmap) {

24 if (hashmap[prop] == kArray.length) {

25 answer.push(parseInt (prop));

26 }

27 }

28 return answer;

29 }

30

31 commonElements([[1 ,2 ,3 ],[1 ,2 ,3 ,4 ],[1 ,2 ]]); // [ 1, 2 ]

Time Complexity: O(kn)

Space Complexity: O(n)

Here, n is longest array length, and k is the number of arrays.

JavaScript Functional Array Methods

Some parts of JavaScript can be written just like a functional programming language. Unlike imperative programming, JavaScript does not focus on the state of the program. It does not use loops, only function (method) calls. You can learn more about functional programming in JavaScript from Beginning Functional JavaScript by Anto Aravinth (Apress, 2017).

In this section, only three functional array methods in JavaScript will be explored: map, filter, and reduce. These methods do not change the original array contents.

Map

The map function applies passed function transformation to every element in the array and returns a new array with those transformations applied.

For example, you can multiply every element by 10, as shown here:

1 [1,2,3,4,5,6,7].map(function (value){

2 return value*10;

3 });

4 // [10, 20, 30, 40, 50, 60, 70]

Filter

The filter function returns only those elements of the array that meet a passed condition parameter. Again, this does not change the original array.

For example, this filters elements greater than 100:

1 [100,2003,10,203,333,12].filter(function (value){

2 return value > 100;

3 });

4 // [2003, 203, 333]

Reduce

The reduce function combines all the elements in the array into one value using a passed transformation function parameter.

For example, this adds all the elements:

1 var sum = [0,1,2,3,4].reduce( function (prevVal, currentVal, index, array) {

2 return prevVal + currentVal;

3 });

4 console.log(sum); // prints 10

This function also can take initialValue as its second argument, which initializes the reduce value. For example, providing an initialValue of 1 in the previous example will yield 11, as shown here:

1 var sum = [0,1,2,3,4].reduce( function (prevVal, currentVal, index, array) {

2 return prevVal + currentVal;

3 }, 1);

4 console.log(sum); // prints 11

Multidimensional Arrays

Unlike Java and C++, JavaScript does not have multidimensional arrays (see Figure 5-1).

../images/465726_1_En_5_Chapter/465726_1_En_5_Fig1_HTML.jpg — Figure 5-1
Multidimensional array

Instead, there are “jagged” arrays. A jagged array is an array whose elements are arrays. The elements of a jagged array can be of different dimensions and sizes (see Figure 5-2).

../images/465726_1_En_5_Chapter/465726_1_En_5_Fig2_HTML.jpg — Figure 5-2
Jagged array

Here is a helper function to create a jagged array like the one in Figure 5-3:

1 function Matrix(rows, columns) {

2 var jaggedarray = new Array(rows);

3 for (var i=0; i < columns; i +=1) {

4 jaggedarray[i]=new Array(rows);

5 }

6 return jaggedarray;

7 }

8 console.log(Matrix(3,3));

../images/465726_1_En_5_Chapter/465726_1_En_5_Fig3_HTML.jpg — Figure 5-3
Three-by-three matrix

To access elements in a jagged array, specify a row and a column (see Figure 5-4).

../images/465726_1_En_5_Chapter/465726_1_En_5_Fig4_HTML.jpg — Figure 5-4
Three-by-three matrix of numbers

1 var matrix3by3 = [[1,2,3],[4,5,6],[7,8,9]];

2 matrix3by3[0]; // [1,2,3]

3 matrix3by3[1]; // [4,5,6]

4 matrix3by3[1]; // [7,8,9]

5

6 matrix3by3[0][0]; // 1

7 matrix3by3[0][1]; // 2

8 matrix3by3[0][2]; // 3

9

10 matrix3by3[1][0]; // 4

11 matrix3by3[1][1]; // 5

12 matrix3by3[1][2]; // 6

13

14 matrix3by3[2][0]; // 7

15 matrix3by3[2][1]; // 8

16 matrix3by3[2][2]; // 9

Exercises

All the code for the exercises can be found on GitHub.²

Spiral Print

Let’s create an example problem with a matrix. Given a matrix, print the elements in a spiral order, like in Figure 5-5.

../images/465726_1_En_5_Chapter/465726_1_En_5_Fig5_HTML.jpg — Figure 5-5
Spiral print

This looks like a daunting task at first. However, the problem can be broken down to five main components.

Printing from left to right
Printing from top to bottom
Printing from right to left
Printing from bottom to top
Keeping a limit on these four operations

In other words, keep four key variables that indicate the following:

Top row
Bottom row
Left column
Right column

Each time one of the four print functions is successfully executed, simply increment one of the four variables. For example, after printing the top row, increment it by 1.

1 var M = [

2 [1, 2, 3, 4, 5],

3 [6, 7, 8, 9, 10],

4 [11, 12, 13, 14, 15],

5 [16, 17, 18, 19, 20]

6 ];

7 function spiralPrint(M) {

8 var topRow = 0,

9 leftCol = 0,

10 btmRow = M.length - 1,

11 rightCol = M[0].length - 1;

12

13 while (topRow < btmRow && leftCol < rightCol) {

14 for (var col = 0; col <= rightCol; col++) {

15 console.log(M[topRow][col]);

16 }

17 topRow++;

18 for (var row = topRow; row <= btmRow; row++) {

19 console.log(M[row][rightCol]);

20 }

21 rightCol--;

22 if (topRow <= btmRow) {

23 for (var col = rightCol; col >= 0; col--) {

24 console.log(M[btmRow][col]);

25 }

26 btmRow--;

27 }

28 if (leftCol <= rightCol) {

29 for (var row = btmRow; row > topRow; row--) {

30 console.log(M[row][leftCol]);

31 }

32 leftCol++;

33 }

34 }

35 }

36 spiralPrint(M);

Time Complexity: O(mn)

Space Complexity: O(1)

Here, m is the number of rows, and n is the number of columns . Each item in the matrix is visited only once.

Tic-Tac-Toe Check

Given a matrix representing a tic-tac-toe board , determine whether someone won, whether it was a tie, or whether the game has not ended yet.³

Here are some examples.

Here, X won:

OX-

-XO

OX

Here it is as a matrix: [['O', 'X', '-'], ['-' ,'X', 'O'], ['O', 'X', '-']].

Here, O won:

O-X

-O-

-XO

Here it is as a matrix: [['O','-','X'], ['-','O','-'], ['-','X','O']].

To do this, check all three rows using a for loop , check all columns using a for loop , and check diagonals.

1 function checkRow ( rowArr, letter ) {

2 for ( var i=0; i < 3; i++) {

3 if (rowArr[i]!=letter) {

4 return false;

5 }

6 }

7 return true;

8 }

9

10 function checkColumn ( gameBoardMatrix, columnIndex, letter ) {

11 for ( var i=0; i < 3; i++) {

12 if (gameBoardMatrix[i][columnIndex]!=letter) {

13 return false;

14 }

15 }

16 return true;

17 }

18

19 function ticTacToeWinner ( gameBoardMatrix, letter) {

20

21 // Check rows

22 var rowWin = checkRow(gameBoardMatrix[0], letter)

23 || checkRow(gameBoardMatrix[1], letter)

24 || checkRow(gameBoardMatrix[2], letter);

25

26 var colWin = checkColumn(gameBoardMatrix, 0, letter)

27 || checkColumn(gameBoardMatrix, 1, letter)

28 || checkColumn(gameBoardMatrix, 2, letter);

29

30 var diagonalWinLeftToRight = (gameBoardMatrix[0][0]==letter && gameBoardMatrix[1][1]==letter && gameBoardMatrix[2][2]==letter);

31 var diagonalWinRightToLeft = (gameBoardMatrix[0][2]==letter && gameBoardMatr ix[1][1]==letter && gameBoardMatrix[2][0]==letter);

32

33 return rowWin || colWin || diagonalWinLeftToRight || diagonalWinRightToLeft;

34 }

35

36 var board = [['O','-','X'],['-','O','-'],['-','X','O']];

37 ticTacToeWinner(board, 'X'); // false

38 ticTacToeWinner(board, 'O'); // true

Path Finding

In Figure 5-6, given the location x, find the exit e.

../images/465726_1_En_5_Chapter/465726_1_En_5_Fig6_HTML.jpg — Figure 5-6
Finding a path

\n is the set of characters used to break a line in JavaScript, like in many standard programming languages. Combining it with backticks, you can create line breaks during the variable-to-string assignment.

1 var board =

2 `%e%%%%%%%%%\n

3 %...%.%...%\n

4 %.%.%.%.%%%\n

5 %.%.......%\n

6 %.%%%%.%%.%\n

7 %.%.....%.%\n

8 %%%%%%%%%x%`;

var rows = board.split("\n")

Then use .map over the array to divide by certain characters into each column.

function generateColumnArr (arr) {

return arr.split("");

}

var mazeMatrix = rows.map(generateColumnArr);

This will generate the proper matrix where each row is an array of the characters and the board is the array of those rows.

Now, first find the entrance, e, and exit, x. This function will return the row position, i, and the column position, j, of the character to be searched for:

1 function findChar(char , mazeMatrix) {

2 var row = mazeMatrix.length,

3 column = mazeMatrix[0 ].length;

4

5 for (var i = 0 ; i < row; i++ ) {

6 for (var j = 0 ; j < column; j++ ) {

7 if (mazeMatrix[i][j] == char ) {

8 return [i, j];

9 }

10 }

11 }

12 }

Of course, there also needs to be a function to print the matrix nicely as a string, as shown here:

1 function printMatrix(matrix) {

2 var mazePrintStr = "" ,

3 row = matrix.length,

4 column = matrix[0 ].length;

5

6 for (var i = 0 ; i < row; i++ ) {

7

8 for (var j = 0 ; j < column; j++ ) {

9 mazePrintStr += mazeMatrix[i][j];

10 }

11

12 mazePrintStr += "\n" ;

13

14 }

15 console.log(mazePrintStr);

16 }

Finally, define a function called path . This recursively checks up, right, down, and left.

Up: path(x+1,y)

Right: path(x,y+1)

Down: path(x-1,y)

Left: path(x,y-1)

function mazePathFinder(mazeMatrix) {

var row = mazeMatrix.length,

column = mazeMatrix[0].length,

startPos = findChar('e', mazeMatrix),

endPos = findChar('x', mazeMatrix);

path(startPos[0], startPos[1]);

function path(x, y) {

if (x > row - 1 || y > column - 1 || x < 0 || y < 0) {

return false;

}

// Found

if (x == endPos[0] && y == endPos[1]) {

return true;

}

if (mazeMatrix[x][y] == '%' || mazeMatrix[x][y] == '+') {

return false;

}

// Mark the current spot

mazeMatrix[x][y] = '+';

printMatrix(mazeMatrix);

if (path(x, y - 1) || path(x + 1, y) || path(x, y + 1) || path(x - 1, y)) {

return true;

}

mazeMatrix[x][y] = '.';

return false;

}

Figure 5-7 shows the console output.

../images/465726_1_En_5_Chapter/465726_1_En_5_Fig7_HTML.jpg — Figure 5-7
Console output

Time Complexity: O(mn)

Space Complexity: O(1)

Here, m is the row length , and n is the column length. Each element is visited only once.

Matrix Rotation

Rotate a matrix to the left by 90 degrees .

For example, the following:

101

001

111

rotates to this:

111

001

101

Figure 5-8 shows the rotation.

../images/465726_1_En_5_Chapter/465726_1_En_5_Fig8_HTML.jpg — Figure 5-8
Matrix counterclockwise rotation

As shown in Figure 5-8, when rotated 90 degrees left, the following happens:

1.
The third column of the matrix becomes the first row of the result.
2.
The second column of the matrix becomes the second row of the result.
3.
The first column of the matrix becomes the third row of the result.

The following rotation turns the third column of the original:

1 var matrix = [[1,0,1],[0,0,1],[1,1,1]];

2

3

4 function rotateMatrix90Left (mat){

5 var N = mat.length;

6

7 // Consider all squares one by one

8 for (var x = 0; x < N / 2; x++) {

9 // Consider elements in group of 4 in

10 // current square

11 for (var y = x; y < N-x-1; y++) {

12 // store current cell in temp variable

13 var temp = mat[x][y];

14

15 // move values from right to top

16 mat[x][y] = mat[y][N-1-x];

17

18 // move values from bottom to right

19 mat[y][N-1-x] = mat[N-1-x][N-1-y];

20

21 // move values from left to bottom

22 mat[N-1-x][N-1-y] = mat[N-1-y][x];

23

24 // assign temp to left

25 mat[N-1-y][x] = temp;

26 }

27 }

28 }

29 rotateMatrix90Left(matrix);

30 console.log(matrix); // [[1,1,1],[0,0,1],[1,0,1]]

Time Complexity: O(mn)

Space Complexity: O(1)

Here, m is the row length, and n is the column length . Each element is visited only once. The space complexity is O(1) because the original array is modified instead of creating a new array.

Summary

Various natively implemented array functions were covered in this chapter and are summarized in Table 5-1.

Table 5-1

Array Function Summary

Function	Usage
push(element)	Adds an element to the end of the array
pop()	Removes the last element of the array
shift()	Removes the first element of the array
slice(beginIndex, endIndex)	Returns a part of the array from beginIndex to endIndex
splice(beginIndex, endIndex)	Returns a part of the array from beginIndex to endIndex and modifies the original array by removing those elements
concat(arr)	Adds new elements (from arr) into the array at the end of array

In addition to the standard while and for loop mechanisms, an iteration of array elements can use the alternative loop mechanisms shown in Table 5-2.

Table 5-2

Iteration Summary

Function	Usage
for (var prop in arr)	Iterates by the index of the array element
for (var elem of arr)	Iterates by the value of the array element
arr.forEach(fnc)	Applies the fnc value on each element

Finally, recall that JavaScript utilizes jagged arrays, an array of arrays, to get multidimensional array behavior. With two-dimensional arrays, two-dimensional surfaces such as a tic-tac-toe board and maze can easily be represented.

5. JavaScript Arrays

Introducing Arrays

Insertion

Deletion

Access

Iteration

for (Variables; Condition; Modification)

for ( in )

for ( of )

forEach( )

Helper Functions

.slice(begin,end)

.splice(begin,size,element1,element2…)

.concat()

.length Property

Spread Operator

Exercises

Find Two Array Elements in an Array That Add Up to a Number

Implement the Array.Slice() Function from Scratch

Find the Median of Two Sorted Arrays of the Same Size

Find Common Elements in K-Sorted Arrays

JavaScript Functional Array Methods

Map

Filter

Reduce

Multidimensional Arrays

Exercises

Spiral Print

Tic-Tac-Toe Check

Path Finding

Matrix Rotation

Summary