let unsorted_array = [-10, 7, 29, 30, 5, -10, -70];

computeProduct(unsorted_array); // 21000

function sortIntegers(a, b) {
  return a - b;
}

// greatest product is either (min1 * min2 * max1 || max1 * max2 * max3)
function computeProduct(unsorted) {
  let sorted_array = unsorted.sort(sortIntegers),
    product1 = 1,
    product2 = 1,
    array_n_element = sorted_array.length - 1; // Get the product of three largest integers in sorted array

  for (let x = array_n_element; x > array_n_element - 3; x--) {
    product1 = product1 * sorted_array[x];
  }
  product2 = sorted_array[0] * sorted_array[1] * sorted_array[array_n_element];

  if (product1 > product2) return product1;

  return product2;
}

// The output of the function should be 8
let array_of_integers = [2, 5, 1, 4, 9, 6, 3, 7];
let upper_bound = 9;
let lower_bound = 1;

findMissingNumber(array_of_integers, upper_bound, lower_bound); //8

function findMissingNumber(array_of_integers, upper_bound, lower_bound) {
  // Iterate through array to find the sum of the numbers
  let sum_of_integers = 0;
  for (let i = 0; i < array_of_integers.length; i++) {
    sum_of_integers += array_of_integers[i];
  } // 以高斯求和公式计算理论上的数组和 // Formula: [(N * (N + 1)) / 2]

  -[(M * (M - 1)) / 2]; // N is the upper bound and M is the lower bound
  upper_limit_sum = (upper_bound * (upper_bound + 1)) / 2;
  lower_limit_sum = (lower_bound * (lower_bound - 1)) / 2;

  theoretical_sum = upper_limit_sum - lower_limit_sum; //

  return theoretical_sum - sum_of_integers;
}

// ES6 Implementation
let array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];

Array.from(new Set(array)); // [1, 2, 3, 5, 9, 8]

// ES5 Implementation
let array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];

uniqueArray(array); // [1, 2, 3, 5, 9, 8]

function uniqueArray(array) {
  let hashmap = {};
  let unique = [];
  for (let i = 0; i < array.length; i++) {
    // If key returns null (unique), it is evaluated as false.
    if (!hashmap.hasOwnProperty([array[i]])) {
      hashmap[array[i]] = 1;
      unique.push(array[i]);
    }
  }
  return unique;
}

let array = [7, 8, 4, 9, 9, 15, 3, 1, 10];
// [7, 8, 4, 9, 9, 15, 3, 1, 10] would return `11` based on the difference between `4` and `15`
// Notice: It is not `14` from the difference between `15` and `1` because 15 comes before 1.

findLargestDifference(array);

function findLargestDifference(array) {
  // 如果数组仅有一个元素，则直接返回 -1

  if (array.length <= 1) return -1; // current_min 指向当前的最小值

  let current_min = array[0];
  let current_max_difference = 0; // 遍历整个数组以求取当前最大差值，如果发现某个最大差值，则将新的值覆盖 current_max_difference // 同时也会追踪当前数组中的最小值，从而保证 `largest value in future` - `smallest value before it`

  for (let i = 1; i < array.length; i++) {
    if (
      array[i] > current_min &&
      array[i] - current_min > current_max_difference
    ) {
      current_max_difference = array[i] - current_min;
    } else if (array[i] <= current_min) {
      current_min = array[i];
    }
  } // If negative or 0, there is no largest difference

  if (current_max_difference <= 0) return -1;

  return current_max_difference;
}

let firstArray = [2, 2, 4, 1];
let secondArray = [0, 0, 0, 2];
let thirdArray = [-2, -2, -3, 2];

productExceptSelf(firstArray); // [8, 8, 4, 16]
productExceptSelf(secondArray); // [0, 0, 0, 0]
productExceptSelf(thirdArray); // [12, 12, 8, -12]

function productExceptSelf(numArray) {
  let product = 1;
  let size = numArray.length;
  let output = []; // From first array: [1, 2, 4, 16] // The last number in this case is already in the right spot (allows for us) // to just multiply by 1 in the next step. // This step essentially gets the product to the left of the index at index + 1

  for (let x = 0; x < size; x++) {
    output.push(product);
    product = product * numArray[x];
  } // From the back, we multiply the current output element (which represents the product // on the left of the index, and multiplies it by the product on the right of the element)

  let product = 1;
  for (let i = size - 1; i > -1; i--) {
    output[i] = output[i] * product;
    product = product * numArray[i];
  }

  return output;
}

let firstArray = [2, 2, 4, 1];
let secondArray = [1, 2, 0, 2];

intersection(firstArray, secondArray); // [2, 1]

function intersection(firstArray, secondArray) {
  // The logic here is to create a hashmap with the elements of the firstArray as the keys.
  // After that, you can use the hashmap's O(1) look up time to check if the element exists in the hash
  // If it does exist, add that element to the new array.

  let hashmap = {};
  let intersectionArray = [];

  firstArray.forEach(function (element) {
    hashmap[element] = 1;
  }); // Since we only want to push unique elements in our case... we can implement a counter to keep track of what we already added

  secondArray.forEach(function (element) {
    if (hashmap[element] === 1) {
      intersectionArray.push(element);
      hashmap[element]++;
    }
  });

  return intersectionArray; // Time complexity O(n), Space complexity O(n)
}

let string = "Welcome to this Javascript Guide!";

// Output becomes !ediuG tpircsavaJ siht ot emocleW
let reverseEntireSentence = reverseBySeparator(string, "");

// Output becomes emocleW ot siht tpircsavaJ !ediuG
let reverseEachWord = reverseBySeparator(reverseEntireSentence, " ");

function reverseBySeparator(string, separator) {
  return string.split(separator).reverse().join(separator);
}

let firstWord = "Mary";
let secondWord = "Army";

isAnagram(firstWord, secondWord); // true

function isAnagram(first, second) {
  // For case insensitivity, change both words to lowercase.
  let a = first.toLowerCase();
  let b = second.toLowerCase(); // Sort the strings, and join the resulting array to a string. Compare the results

  a = a.split("").sort().join("");
  b = b.split("").sort().join("");

  return a === b;
}

isPalindrome("racecar"); // true
isPalindrome("race Car"); // true

function isPalindrome(word) {
  // Replace all non-letter chars with "" and change to lowercase
  let lettersOnly = word.toLowerCase().replace(/\s/g, ""); // Compare the string with the reversed version of the string

  return lettersOnly === lettersOnly.split("").reverse().join("");
}

let inputStack = []; // First stack
let outputStack = []; // Second stack

// For enqueue, just push the item into the first stack
function enqueue(stackInput, item) {
  return stackInput.push(item);
}

function dequeue(stackInput, stackOutput) {
  // Reverse the stack such that the first element of the output stack is the
  // last element of the input stack. After that, pop the top of the output to
  // get the first element that was ever pushed into the input stack
  if (stackOutput.length <= 0) {
    while (stackInput.length > 0) {
      let elementToOutput = stackInput.pop();
      stackOutput.push(elementToOutput);
    }
  }

  return stackOutput.pop();
}

let expression = "{{}}{}{}";
let expressionFalse = "{}{{}";

isBalanced(expression); // true
isBalanced(expressionFalse); // false
isBalanced(""); // true

function isBalanced(expression) {
  let checkString = expression;
  let stack = []; // If empty, parentheses are technically balanced

  if (checkString.length <= 0) return true;

  for (let i = 0; i < checkString.length; i++) {
    if (checkString[i] === "{") {
      stack.push(checkString[i]);
    } else if (checkString[i] === "}") {
      // Pop on an empty array is undefined
      if (stack.length > 0) {
        stack.pop();
      } else {
        return false;
      }
    }
  } // If the array is not empty, it is not balanced

  if (stack.pop()) return false;
  return true;
}

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

decimalToBinary(3); // 11
decimalToBinary(8); // 1000
decimalToBinary(1000); // 1111101000

function decimalToBinary(digit) {
  if (digit >= 1) {
    // If digit is not divisible by 2 then recursively return proceeding
    // binary of the digit minus 1, 1 is added for the leftover 1 digit
    if (digit % 2) {
      return decimalToBinary((digit - 1) / 2) + 1;
    } else {
      // Recursively return proceeding binary digits
      return decimalToBinary(digit / 2) + 0;
    }
  } else {
    // Exit condition
    return "";
  }
}

function recursiveBinarySearch(array, value, leftPosition, rightPosition) {
  // Value DNE
  if (leftPosition > rightPosition) return -1;

  let middlePivot = Math.floor((leftPosition + rightPosition) / 2);
  if (array[middlePivot] === value) {
    return middlePivot;
  } else if (array[middlePivot] > value) {
    return recursiveBinarySearch(array, value, leftPosition, middlePivot - 1);
  } else {
    return recursiveBinarySearch(array, value, middlePivot + 1, rightPosition);
  }
}

isPowerOfTwo(4); // true
isPowerOfTwo(64); // true
isPowerOfTwo(1); // true
isPowerOfTwo(0); // false
isPowerOfTwo(-1); // false

// For the non-zero case:
function isPowerOfTwo(number) {
  // `&` uses the bitwise n.
  // In the case of number = 4; the expression would be identical to:
  // `return (4 & 3 === 0)`
  // In bitwise, 4 is 100, and 3 is 011. Using &, if two values at the same
  // spot is 1, then result is 1, else 0. In this case, it would return 000,
  // and thus, 4 satisfies are expression.
  // In turn, if the expression is `return (5 & 4 === 0)`, it would be false
  // since it returns 101 & 100 = 100 (NOT === 0)

  return number & (number - 1 === 0);
}

// For zero-case:
function isPowerOfTwoZeroCase(number) {
  return number !== 0 && (number & (number - 1)) === 0;
}