CollegeStash – Page 10

Continous Subarray Sum

/**
@param {number[]} nums
@param {number} k
@return {boolean}
*/
const checkSubarraySum = (nums, k) => {
  const map = { 0: -1};
  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i]; 
    if (k != 0)
      sum %= k;
    if (map[sum] >= -1) {
      if (i - map[sum] > 1)
        return true;
    } else
      map[sum] = i;
  }
  return false;
};
// Time Complexity O(n)
// Space Complexity O(n)

console.log(checkSubarraySum([23, 2, 4, 6, 7], 6));
// Output: true

/**
@param {number[]} nums
@param {number} k
@return {boolean}
*/
const checkSubarraySumBruteForce = (nums, k) => {
  for (var start = 0; start < nums.length - 1; start++) {
    var sum = nums[start];
    for (var end = start + 1; end < nums.length; end++) {
      sum += nums[end];
      if (sum === k || (k !== 0 && sum % k === 0))
        return true;
    }
  }
  return false;
};
// Time Complexity O(n2)
// Space Complexity O(1)

console.log(checkSubarraySumBruteForce([23, 2, 4, 6, 7], 6));
// Output: true

Demo

May 21, 2020

Multiply Strings

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
  num1 = num1.split('').reverse().join('');
  num2 = num2.split('').reverse().join('');
  var result = [];
  for (let i = 0; i < num1.length + num2.length; i++) {
    result[i] = 0;
  }

  for (let i = 0; i < num1.length; i++) {
    for (let j = 0; j < num2.length; j++) {
      result[i + j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
    }
  }

  var str = '';
  for (let i = 0; i < result.length; i++) {
    var curr = result[i] % 10;
    var carry = Math.floor(result[i] / 10);
    if (i < result.length - 1)
      result[i + 1] += carry;
    str = curr + str;
  }

  while (str.charAt(0) === '0' && str.length > 1) {
    var n = str.length;
    str = str.substring(1, n);
  }

  return str;
};

console.log(multiply('2', '3'));
// Ouput: "6"

// var multiply = function(num1, num2) {
//  num1 = parseInt(num1, 10);
//  num2 = parseInt(num2, 10);
//  return (num1*num2)+'';
// }

Demo

May 21, 2020

Lowest Common Ancestor of a Binary Tree

/**
Definition for a binary tree node.
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
/ /*
@param {TreeNode} root
@param {TreeNode} p
@param {TreeNode} q
@return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
  if (root === null)
    return root;
  if (root === p || root === q)
    return root;
  var left = lowestCommonAncestor(root.left, p, q);
  var right = lowestCommonAncestor(root.right, p, q);
  if (left !== null && right !== null)
    return root;
  return left === null ? right : left;
};
// if only one of the Nodes is present in the given Binary Tree, then it is returned,
// you can traverse through the returned Node and check if the other one is present.

Demo

May 20, 2020

Number of subsets

For a given list of integers and integer K, find the number of non-empty subsets S such that min(S) + max(S) <= K.

Example 1:

nums = [2, 4, 5, 7]
k = 8
Output: 5
Explanation: [2], [4], [2, 4], [2, 4, 5], [2, 5]

Code:

var nums = [2, 4, 5, 7];

var findNum = function(nums, k) {
  nums.sort((a, b) => a - b);
  var count = 0;
  var low = 0;
  var high = nums.length - 1;
  while (low <= high) {
    if (nums[low] + nums[high] > k) {
      high--;
    } else {
      // Total subsets for set of n =  2^n
      count += 1 << (high - low);
      low++;
    }
  }
  return count;
}

console.log(findNum(nums, 8));
// Runtime complexity O(nlogn)
// Output: 5

Demo

May 20, 2020

Shortest Distance to a Character

class Solution {
    public int[] shortestToChar(String S, char C) {
        int n = S.length();
        int prev = Integer.MIN_VALUE/2;
        int[] store = new int[n];
        for(int i = 0; i < n; i++) {
            if(S.charAt(i) == C) {
                store[i] = 0;
                prev = i;
            }
            else 
                store[i] = i - prev; 
        }
        prev = Integer.MAX_VALUE/2;
        for(int i = n-1; i >= 0; i--) {
             if(S.charAt(i) == C)
                prev = i;
            else 
                store[i] = Math.min(store[i], prev - i); 
        }
        return store;
    }
}

May 5, 2020

Largest 1-Bordered Square

class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int[][] h = new int[grid.length][grid[0].length];
        int[][] v = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    h[i][j] = 0;
                    v[i][j] = 0;
                } else {
                    h[i][j] = j > 0 ? h[i][j - 1] + 1 : 1;
                    v[i][j] = i > 0 ? v[i - 1][j] + 1 : 1;
                }
            }
        }
        int max = 0;
        for (int i = grid.length - 1; i >= 0; i--) {
            for (int j = grid[0].length - 1; j >= 0; j--) {
                int small = Math.min(v[i][j], h[i][j]);
                while (small > max) {
                    if (v[i][j + 1 - small] >= small && h[i + 1 - small][j] >= small) {
                        max = Math.max(max, small);
                    }
                    small--;
                }
            }
        }
        return max * max;
    }
}

May 5, 2020

Longest Common Prefix using Binary Search (ES6)

const arr = ["hello", "helloworld", "helloworld1"];

const allContains = (inp, start, end) => {
for(let i=0; i<inp.length; i++) {
	for(let j=start; j<=end; j++) {
		if(inp[0].charAt(j)!==inp[i].charAt(j)) {
			return false;
    	}
	}
}
return true;
};

const findSubstring = (inp) => {
let min = Number.MAX_VALUE;
  for(let i=0; i<inp.length; i++) {
  	 min = Math.min(inp[i].length, min);
  }
let low = 0, high = min-1;
let prefix = '';
 while(low<=high) {
 	let mid = low + Math.round((high-low)/2);
  	if(allContains(inp, low, mid)) {
   		prefix += inp[0].substring(low, mid+1);
  		low = mid+1;
  	} else
  	high = mid-1;
		}
return prefix;
};

console.log(findSubstring(arr));

// Output: hello
// Runtime complexity: O(m*log(n)) 
// m- length of input array or list and n is length of 
// smallest string.

Demo

April 30, 2020

Verifying an Alien Dictionary (Js)

/**
 * @param {string[]} words
 * @param {string} order
 * @return {boolean}
 */
const isAlienSorted = function(words, order) {
  
const isInOrder = {};
  for (let i = 0; i < order.length; i++) {
    isInOrder[order.charAt(i)] = i;
  }

  search: for (let i = 0; i < words.length - 1; i++) {
    const wordBefore = words[i];
    const wordAfter = words[i + 1];
    const minWordLen = Math.min(wordBefore.length, wordAfter.length);
    for (let k = 0; k < minWordLen; k++) {
      if (wordBefore.charAt(k) !== wordAfter.charAt(k)) {
        if (isInOrder[wordBefore.charAt(k)] > isInOrder[wordAfter.charAt(k)]) {
          return false;
          }
        continue search;
      }
    }
   if (wordBefore.length > wordAfter.length) {
     return false;
     }
  }
  return true
};

console.log(isAlienSorted(['ace', 'ad'], 'abcdefghijklmnopqrstuv')); // true

Demo

April 25, 2020

Filter objects (ES6)

// There could potentially be more than 3 keys in the object below.
const items = [{
    color: 'red',
    type: 'tv',
    age: 18
  },
  {
    color: 'silver',
    type: 'phone',
    age: 20
  },
  {
    color: 'yellow',
    type: 'truck',
    age: 10
  },
  {
    color: 'blue',
    type: 'shirt',
    age: 5
  },
];

const excludes = [{
    k: 'color',
    v: 'silver'
  },
  {
    k: 'type',
    v: 'tv'
  },
  {
    k: 'color',
    v: 'red'
  }
];

// SOLUTION

const excludesMap = excludes.reduce((acc, curr) => {
  (acc[curr.k] || (acc[curr.k] = {}))[curr.v] = true;
  return acc;
}, {});

/*
color: red: true,
       green: true ... 
type: tv: true
       truck: true, ...

*/

const exclude = (items, excludes) => items.filter(item => {
  for (const [key, value] of Object.entries(item)) {
   if(excludesMap[key]?.[value])
      return false;
  }
  return true;
});

console.log(exclude(items, excludes));
/*
  [{
    age: 10,
    color: "yellow",
    type: "truck"
  }, {
    age: 5,
    color: "blue",
    type: "shirt"
  }]
*/

Demo

April 19, 2020

Flatten an Array (ES6)

To flatten an array with depth of level 1:

const inputArray = [1, 2, 3, [4, 5]];
console.log([].concat(...inputArray));
// Output: [1, 2, 3, 4, 5]

Demo

To flatten an array of a specified depth:

const input = [1, 2, 3, [4, 5, 6, [8, 9, 10]], 11, [12, 13, 14]];

const flatten = (arr, depth) =>
  depth === 0 || !Array.isArray(arr) ? arr :
  arr.reduce((acc, curr) =>
    Array.isArray(curr) ? acc.concat(flatten(curr, depth - 1)) :
    acc.concat(curr), [])

console.log(flatten(input, 3));
// Ouput: [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14]

Demo

To flatten an array infinitely:

const input = [1, 2, 3, [4, 5, 6, [8, 9, 10]], 11, [12, 13, 14]];

const flatten = (arr) =>
   !Array.isArray(arr) ? arr : arr.reduce((acc, curr) =>
    Array.isArray(curr) ? acc.concat(flatten(curr)) :
    acc.concat(curr), []);

console.log(flatten(input));
// Ouput: [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14]

Demo

April 19, 2020