# Range Sum of BST

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Example 1:

Input:

 root = [10,5,15,3,7,null,18], low = 7, high = 15


Output:

 32


Explanation:

 Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.


Example 2:

Input:

 root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10


Output:

 23


Explanation:

 Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.


Constraints:

• The number of nodes in the tree is in the range [1, 2 * 104].
• 1 <= Node.val <= 105
• 1 <= low <= high <= 105
• All Node.val are unique.

This problem was taken from https://leetcode.com/problems/range-sum-of-bst/

[tabby title=”Solution”]

## DFS Solution

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} low
* @param {number} high
* @return {number}
*/
var rangeSumBST = function(root, low, high) {
if(!root) {
return;
}
console.log(root.val);
var queue = [root];
var visited = {};
var result = 0.0;

function dfsTraverse(root, low, high) {

var childNodes = [root?.left, root?.right];

for(const childNode of childNodes) {
if(childNode) {
var val = childNode.val;
console.log(val);
dfsTraverse(childNode, low, high);
}
}

}

dfsTraverse(root, low, high);
return result;
};

function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}

const treeNode = new TreeNode(
10,
new TreeNode(
5,
new TreeNode(3),
new TreeNode(7)
),
new TreeNode(
15,
null,
new TreeNode(18)
)
)

rangeSumBST(treeNode, 7, 15);

## BFS solution

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} low
* @param {number} high
* @return {number}
*/
var rangeSumBST = function(root, low, high) {
if(!root) {
return 0;
}
var queue = [root];
var visited = {};
var result = 0.0;
if(root.val >= low && root.val <= high) {
result = root.val;
}

var leftPointer = 0;
while(leftPointer <= queue.length) {
var curentNode = queue[leftPointer];
leftPointer ++;
var childNodes = [curentNode?.left, curentNode?.right];

for(const childNode of childNodes) {
if(childNode) {
console.log(childNode.val)
if(childNode.val >= low && childNode.val <= high) {
result += childNode.val;
}
queue.push(childNode);
}
}

}
return result;

};

[tabbyending]

# The graph

The graph represent connections between airports. Nodes (vertices)  represent airports, and  edges represent flights.

# BFS search (Breadth First Search)

Breadth-first Search (BFS) starts by pushing all of the direct children to a queue (first-in, first-out). It then visits each item in queue and adds the next layer of children to the back of the queue. Since one node could be visited multiple times causing infinite loop, we have to keep track of all visited nodes.

## Using JavaScript Map

// DATA
const airports = 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' ');

const routes = [
['PHX', 'LAX'],
['PHX', 'JFK'],
['JFK', 'OKC'],
['JFK', 'HEL'],
['JFK', 'LOS'],
['MEX', 'LAX'],
['MEX', 'BKK'],
['MEX', 'LIM'],
['MEX', 'EZE'],
['LIM', 'BKK'],
];

// The graph

}

}

// Create the Graph

function bfs(start, searchItem) {

const visited = new Set();
const queue = [start];

while (queue.length > 0) {

const airport = queue.shift(); // mutates the queue

for (const destination of destinations) {
if (destination === searchItem)  {
console.log(BFS found a route to, searchItem)
}

if (!visited.has(destination)) {
queue.push(destination);
}
}
}

}

bfs('PHX', 'BKK');

## Using JavaScript object

// Data
var airports = {
'PHX': ['LAX', 'JFK'],
'BKK': ['MEX', 'LIM'],
'OKC': ['JFK'],
'JFK': ['LAX', 'PHX', 'OKC', 'HEL', 'LOS', 'EZE'],
'LAX': ['PHX', 'JFK', 'MEX'],
'MEX': ['LAX', 'EZE', 'BKK', 'LIM'],
'EZE': ['JFK', 'MEX'],
'HEL': ['JFK'],
'LOS': ['JFK'],
'LAP': [],
'LIM': ['MEX', 'BKK']
};

function bfs(start, endDest) {
var queue = [start];
var visited = {};

while(queue.length > 0) {
var curentNodeVal = queue.shift();
var childNodes = airports[curentNodeVal];
for(const childNode of childNodes) {
if(childNode === endDest) {
console.log("BFS found a route to :", endDest);
}

if(!visited[childNode]) {
console.log(childNode);
visited[childNode] = true;
queue.push( childNode);
}
}
}
}

bfs('PHX', 'BKK');

# DFS (Depth First Search)

Depth-first Search (DFS) will go as far into the graph as possible until it reaches a node without any children, at which point it backtracks and continues the process. The algorithm can be implemented with a recursive function that keeps track of previously visited nodes. If a node has not been visited, we call the function recursively.

## Using JavaScript Map

// DATA
const airports = 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' ');

const routes = [
['PHX', 'LAX'],
['PHX', 'JFK'],
['JFK', 'OKC'],
['JFK', 'HEL'],
['JFK', 'LOS'],
['MEX', 'LAX'],
['MEX', 'BKK'],
['MEX', 'LIM'],
['MEX', 'EZE'],
['LIM', 'BKK'],
];

// The graph

}

}

// Create the Graph

function dfs(start, visited = new Set()) {

console.log(start)

for (const destination of destinations) {

if (destination === 'BKK') {
console.log(DFS found Bangkok)
return;
}

if (!visited.has(destination)) {
dfs(destination, visited);
}

}

}

dfs('PHX');

## Using JavaScript object

// Data
var airports = {
'PHX': ['LAX', 'JFK'],
'BKK': ['MEX', 'LIM'],
'OKC': ['JFK'],
'JFK': ['LAX', 'PHX', 'OKC', 'HEL', 'LOS', 'EZE'],
'LAX': ['PHX', 'JFK', 'MEX'],
'MEX': ['LAX', 'EZE', 'BKK', 'LIM'],
'EZE': ['JFK', 'MEX'],
'HEL': ['JFK'],
'LOS': ['JFK'],
'LAP': [],
'LIM': ['MEX', 'BKK']
};

function dfs(start, endDest, visited = {}) {

visited[start] = true;
console.log(start);

const destinations = airports[start];

for(const destination of  destinations) {
if (destination === endDest) {
console.log(DFS found route to, endDest);
}

if(!visited[destination]) {
dfs(destination, endDest, visited);
}

}
}

dfs('PHX', 'BKK');

# Moving Average from Data Stream

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Implement the MovingAverage class:

• MovingAverage(int size) Initializes the object with the size of the window size.
• double next(int val) Returns the moving average of the last size values of the stream.

Example 1:

Input

["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]


Output

[null, 1.0, 5.5, 4.66667, 6.0]



Explanation

MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3


Constraints:

• 1 <= size <= 1000
• -105 <= val <= 105
• At most 104 calls will be made to next.

[tabby title=”Solution”]

/**
* @param {number} size
*/
var MovingAverage = function(size) {
this.n = size;
this.queue = [];
this.average = 0.0;
};

/**
* @param {number} val
* @return {number}
*/
MovingAverage.prototype.next = function(val) {
var removedVal;
if(this.queue.length >= this.n) {
removedVal = this.queue.shift();
this.average = this.average - removedVal;
}

this.queue.push(val);

this.average += val;
console.log(this.average / this.queue.length);
return this.average / this.queue.length;
};

var movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

[tabbyending]

# Heaps or priority queues in Java Script

Still work in progress …

# Part II sort and heapify

We start swapping values and heapify each time starting from 0 to the length of i

function heapSort(arr) {

function maxHeapify(arr, i, N) {
var leftChild = i * 2 + 1;
var rightChild = i * 2 + 2;
var largest = i;

if(leftChild < N && arr[leftChild] > arr[largest]) {
largest = leftChild;
}

if(rightChild < N && arr[rightChild] > arr[largest]) {
largest = rightChild;
}

if(largest != i) {
var temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
maxHeapify(arr, largest, N);
}
}

// CREATE A HEAP
for(var i = parseInt(arr.length / 2 - 1); i >= 0; i--) {
maxHeapify(arr, i, arr.length);
}

console.log("heap represented in array: ", arr);

// SORT THE ARRAY
for(var i =  arr.length - 1; i >= 0; i --) {
var temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

maxHeapify(arr, 0, i);
}
}

const arr = [4, 6, 3, 2, 9, 1];
heapSort(arr);

console.log("sorted array:", arr);

# Implement pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

Example 1:

Input:

 x = 2.00000, n = 10


Output:

 1024.00000


Example 2:

Input:

 x = 2.10000, n = 3


Output:

 9.26100


Example 3:

Input:

 x = 2.00000, n = -2


Output:

 0.25000


Explanation:

 2

-2

 = 1/2

2

 = 1/4 = 0.25


Constraints:

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

This problem was taken from https://leetcode.com/problems/powx-n/

[tabby title=”Solution”]

# Brute force solution:

Straight forward, but we have to consider negative ranges.

/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function(x, n) {

if(n === 0) {
return 1;
}

var N = n;
var X = x;
var result = 1;

if(n < 0) {
X = 1 / x;
N = -n;
}

for(var i = 0; i < N; i ++) {
result = result * X;
}
return result;
};

# Approach 2: Fast Power Algorithm Recursive

• divide n so you immediately cut the computation time in half to logarithmic one.

/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function(x, n) {

function fastPow(x, n) {
if(n < 1) {
return 1;
}
var half = fastPow(x, Math.floor(n / 2));

if(n % 2 == 0) {
return half * half;
}
else {
return half * half * x;
}
}

var X = x;
var N = n;
if(n < 0) {
X = 1 / x;
N = -n;
}
return fastPow(X, N);

};

[tabbyending]

# regular JavaScript functions vs array functions

### Does not have its own bindings to this or super, and should not be used as methods.

var obj1 = {
a: 123,
b: function() {
return this.a;
}
}

var obj2 = {
a: 123,
b: () => {
return this.a;
}
}

console.log("obj1: ", obj1.b());
console.log("obj2: ", obj2.b());

==========================================
result
==========================================

obj1:  123
obj2:  undefined

### Using call/apply and bind

var obj1 = {
a: 111,
b: (a,b) => {
return ${this.a}${a} ${b}; }, c: function(a,b) { return ${this.a} ${a}${b};
}
}

var obj2 = {
a: 123
}

console.log("obj1: ", obj1.b.apply(obj2, ['one', 'two']));
console.log("obj1: ", obj1.b.bind(obj2)());

console.log("obj1: ", obj1.c.apply(obj2, ['one', 'two']));
console.log("obj1: ", obj1.c.bind(obj2, 'one', 'two')());

=====================================================
result
=====================================================
obj1:  undefined one two
obj1:  undefined undefined undefined
obj1:  123 one two
obj1:  123 one two

# JavaScript call, bind and apply simple

According MDN all three methods are very similar, and at the end they produce very similar result.

• they all accept this object as first parameter.
• then apply accepts and array of arguments vs bind and call accept a sequence of arguments.

# Function.prototype.apply()

The apply() method calls a function with a given this value, and arguments provided as an array

# Function.prototype.bind()

The bind() method creates a new function that, when called, has its this keyword set to the provided value, with a given sequence of arguments preceding any provided when the new function is called

const module = {
getX: function(one, two) {
return ${this.x}${one} \${two};
}
};

const obj = {x: '123'};

console.log( "call: ",module.getX.call(obj, 'ONE', 'TWO') );

console.log( "apply: ",module.getX.apply(obj, ['ONE', 'TWO']) );

var newFunc = module.getX.bind( obj, 'ONE', 'TWO');
console.log("bind: ", newFunc());



result should be the same.

call:  123 ONE TWO
apply:  123 ONE TWO
bind:  123 ONE TWO

# Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input:

 strs = ["flower","flow","flight"]


Output:

 "fl"


Example 2:

Input:

 strs = ["dog","racecar","car"]


Output:

 ""


Explanation:

 There is no common prefix among the input strings.


Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lower-case English letters.

This problem was taken from Leetcode Longest Common Prefix

[tabby title=”Solution”]

Let’s examine this example:

 strs = ["flower","flow","flight"]


the longest common substring is:

 "fl"

Solution 1: Horizontal scanning

We could assume that the whole word could be the common one so we set prefix = ‘flower’
Then we would compare with the rest words and keep removing last character until prefix becomes empty (meaning no common substring was found) or until we have the common substring.

 prefix flower flow flight flower flower flower flower flowe flowe flowe flowe flow flow flow flow flo flo flo flo fl fl fl fl

/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
var prefix = strs[0];
for(var i = 1; i < strs.length; i ++ ) {
while(strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length - 1);
if(prefix == "")
return '';
}
}
return prefix;
};

what we just did:
– set up prefix to be the whole 1st word strs[0]
– compare prefix with the second word (strs[1]) and if there is no match, remove the last symbol and keep going until it finds match.

Complexity Analysis

• Time complexity : O(S) , where S is the sum of all characters in all strings.In the worst case all n strings are the same. The algorithm compares the string S1 with the other strings [S_2 \ldots S_n] There are S character comparisons, where S is the sum of all characters in the input array.
• Space complexity : O(1). We only used constant extra space.

Solution 2: Vertical scanning

Similar but optimized for cases like the one above where we have very short common substring, and we don’t want to scan the whole word.

 prefix flower flow flight f f f f fl fl fl fl flo flo flo flo

/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
var prefix;
for(var i = 0; i < strs[0].length; i ++ ) {
var c = strs[0][i];
for(var j = 0; j < strs.length; j++) {
if(strs[j][i] != c) {
return strs[0].substring(0, i);
}
}
}
return strs[0];
};

what we just did:
– Iterate through the words like they are in column.
– compare each character (starting with the first one) between all words. When we find a mismatch, remove the last (mismatched) character and return truncates strs[0]

[tabbyending]

# Roman to Integer

Roman numerals are represented by seven different symbols: IVXLCD and M.

Symbol                Value

I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two one’s added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input:

 s = "III"


Output:

 3


Example 2:

Input:

 s = "IV"


Output:

 4


Example 3:

Input:

 s = "IX"


Output:

 9


Example 4:

Input:

 s = "LVIII"


Output:

 58


Explanation:

 L = 50, V= 5, III = 3.


Example 5:

Input:

 s = "MCMXCIV"


Output:

 1994


Explanation:

 M = 1000, CM = 900, XC = 90 and IV = 4.


Constraints:

• 1 <= s.length <= 15
• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
• It is guaranteed that s is a valid roman numeral in the range [1, 3999].

This problem was taken from Leetcode Roman To Integer

[tabby title=”Solution”]

Solution 1: Left to right pass

/**
* @param {string} s
* @return {number}
*/
var romanToInt = function(s) {
var len = s.length;
var i = 0;
var map = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
var sum = 0;
while(i < len) {
var currentVal = map[ s[i] ];
var nextVal = map[ s[i + 1] ];
if( currentVal < nextVal) {
sum += nextVal - currentVal;
i ++;
}
else {
sum += currentVal;
}
i ++;
}
return sum;
};

Solution 2: Left to right (or right to left) pass improved

/**
* @param {string} s
* @return {number}
*/
var romanToInt = function(s) {
var len = s.length;
var i = 0;
var map = {
'I': 1,
'IV': 4,
'V': 5,
'IX': 9,
'X': 10,
'XL': 40,
'L': 50,
'XC': 90,
'C': 100,
'CD': 400,
'D': 500,
'CM': 900,
'M': 1000
}
var sum = 0;
while(i < len) {
var currentVal = map[ s[i] ];
var nextVal = map[ s[i + 1] ];
if( currentVal < nextVal) {
var sumbol = s[i] + s[i+1];
sum += map[sumbol];
i ++;
}
else {
sum += currentVal;
}
i ++;
}
return sum;
};

Solution3: Right to left pass

In the “subtraction” cases, such as XC, we’ve been updating our running sum as follows:

sum += value(C) - value(X)


However, notice that this is mathematically equivalent to the following:

sum += value(C)
sum -= value(X)


Utilizing this means that we can process one symbol each time we go around the main loop. We still need to determine whether or not our current symbol should be added or subtracted by looking at the neighbour though.

This way we could start from the most right symbol an initialize the sym with it, since every most right symbol will always be added to the sum.

/**
* @param {string} s
* @return {number}
*/
var romanToInt = function(s) {
var len = s.length;
var i = len - 1;
var map = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
var sum = map[ s[i] ];
i --;
while(i > -1) {
var currentVal = map[ s[i] ];
var prevVal = map[ s[i + 1] ];
if( currentVal < prevVal) {
sum -= currentVal;
}
else {
sum += currentVal;
}
i --;
}
return sum;
};

[tabbyending]

# Container With Most Water

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai)n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Example 1:

Input:

 height = [1,8,6,2,5,4,8,3,7]


Output:

 49


Explanation:

 The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.


Example 2:

Input:

 height = [1,1]


Output:

 1


Example 3:

Input:

 height = [4,3,2,1,4]


Output:

 16


Example 4:

Input:

 height = [1,2,1]


Output:

 2

This problem was taken from Leetcode Container With Most Water

[tabby title=”Solution”]

A better than brute force solution is to use a variation of “sliding doors” algorithm.

Let’s consider this case: [1,3,4,3]. The area with most water will be the one with highest height and length.

To find it we set up two pointers: one at position 0, and one at the end of the array. The amount of water that could be collected here is min(leftPointerValue, rightPointerValue) * length,
where length is rightPointer – leftPointer. Which is 4.

Now it’s clear that if rightPointerValue > leftPointerValue there is no point of keep moving rightPointer because we won’t get any bigger amount of water since it will always be limited by the leftPointerValue (height) and the length will always be smaller than the previous length.

So in this case we will move the leftPointer forward to evaluate the next case.

Here the amount of the water collected is min(leftPointerValue, rightPointerValue) * length which is min(3, 3) * 3 = 9.

Nex we continue evaluating all cases till leftPointer = rightPointer (length = 0), and we didn’t find bigger amount of water collected, so the answer we found on the second evaluation is the right answer: 9.

/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {

var maxArea = 0;
var pLeft = 0;
var pRight = height.length - 1;
var len = pRight - pLeft;

while(len > 0) {
var pLeftVal = height[pLeft];
var pRightVal = height[pRight];

if(pLeftVal > pRightVal) {
maxArea = Math.max( len * pRightVal, maxArea );
pRight --;
}
else {
maxArea = Math.max( len * pLeftVal, maxArea );
pLeft ++;
}
len --;
}
return maxArea;
};

var height = [1,8,6,2,5,4,8,3,7];
console.log( maxArea(height) );

[tabbyending]