wataruoguchi

// https://www.geeksforgeeks.org/inplace-rotate-square-matrix-by-90-degrees/
// https://practice.geeksforgeeks.org/problems/rotate-by-90-degree/0
function rotateMatrixAntiClockwise(matrix) {
  let x;
  let y;
  let length = matrix.length;
  // Consider all squares.
  // If the matrix is 3x3, you need to rotate one square.
  // If it's 4x4, or 5x5, it's gonna be two.
  // If it's 6x6, or 7x7, it's gonna be three.

wataruoguchi

// https://practice.geeksforgeeks.org/problems/stock-span-problem/0
function stockSpan(arr) {
  let idx;
  let len = arr.length;
  let resArr = new Array(arr.length);
  // It's always 1 because nothing is before this.
  resArr[0] = 1;
  for (idx = 1; idx < len; idx++) {
    resArr[idx] = 1;
    // Traverse left while the next element on left is smaller

wataruoguchi

// Overlapping Subproblems and Optimization

// https://www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/
// Example: Fibonacci Numbers, there are many subproblems which are solved again and again.
function fib(num) {
  if (num <= 1) {
    return num;
  }
  return fib(num - 1) + fib(num - 2);
}

wataruoguchi

// https://www.geeksforgeeks.org/given-a-string-print-all-possible-palindromic-partition/
function findAllPalindromes(str) {
  function isPalindrome(str, min, max) {
    while (min < max) {
      if (str[min] !== str[max]) return false;
      min++;
      max--;
    }
    return true;
  }

wataruoguchi

//Given a 2D array containing only 0s and 1s, where each row is sorted.
// Find the row with the maximum number of 1s.
function getTheRowThatHasMost1s(arr) {
  const arrWithCount = arr.map((row) => {
    return {row:row, count: row.filter((num) => num === 1).length};
  });
  return arrWithCount.reduce((acc, row) => {
    if (acc.count < row.count) {
      acc = row;
    }

wataruoguchi

// https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
// https://practice.geeksforgeeks.org/problems/kadanes-algorithm/0
function maxSubArraySum(arr, len) {
  let maxSoFar = Math.min(...arr);
  let maxEndingHere = 0;
  let idx;
  for (idx = 0; idx < len; idx++) {
    maxEndingHere = maxEndingHere + arr[idx];
    if (maxSoFar < maxEndingHere) {
      maxSoFar = maxEndingHere;

wataruoguchi

// https://practice.geeksforgeeks.org/problems/largest-number-formed-from-an-array/0
function generateLargestNumber(arr) {
  const resStr = arr.sort((a,b) => {
    const ab = `${a}${b}`;
    const ba = `${b}${a}`;
    return ab === ba ? 0 : ab > ba ? -1 : 1;
  }).reduce((acc, num) => {
    return `${acc}${num}`;
  }, '');
  return parseInt(resStr, 10);

wataruoguchi

// https://practice.geeksforgeeks.org/problems/find-the-smallest-and-second-smallest-element-in-an-array/0
function findTwoSmallest(arr) {
  // 1<=n<=100
  let smallests = [101, 101];  // 1st smallest, 2nd smallest
  const res = arr.reduce((acc, num) => {
    if (num < acc[1] && num !== acc[0]) {
      if (num < acc[0]) {
        acc[1] = acc[0];
        acc[0] = num;
      } else {

wataruoguchi

// https://practice.geeksforgeeks.org/problems/missing-number-in-array/0
function findMissingNum(arr) {
  const res = arr.sort((a,b) => a - b).filter((num, idx) => {
    return num !== idx + 1
  });
  return res.length ? res[0] - 1: -1;
}
const nums1 = [1,2,3,5];
const result1 = findMissingNum(nums1);
console.log(result1 === 4);

wataruoguchi

// https://practice.geeksforgeeks.org/problems/number-of-occurrence/0
// https://www.geeksforgeeks.org/count-number-of-occurrences-or-frequency-in-a-sorted-array/
function numberOfOccurrence(arr, targetNum) {
  return arr.filter((num) => num === targetNum).length || -1;
}
const nums1 = [1,1,2,2,2,2,3];
const result1 = numberOfOccurrence(nums1,2);
console.log(result1 === 4);
const nums2 = [1,1,2,2,2,2,3];
const result2 = numberOfOccurrence(nums2,4);