trykhov’s gists

trykhov / triangularSum.js

Created September 16, 2024 08:29

	function triangularSum(nums) {

	// duplicate the input array, nums
	let newNums = new Array(nums.length);
	for(let i = 0; i < nums.length; i++) {
	newNums[i] = nums[i];
	}

	// while loop ensures the process continues until newNums.length == 1
	while(newNums.length > 1) {

trykhov / minCoinChange.js

Last active December 28, 2021 15:42

	// assume that coins is an array of positive integers
	// assume that amount is non-negative

	function minCoinChange(coins, amount) {
	// create an array to hold the minimum number of coins to make each amount
	// amount + 1 so that you will have indices from 0 to amount in the array
	const minCoins = new Array(amount + 1).fill(Infinity);
	// there are 0 ways to make amount 0 with positive coin values
	minCoins[0] = 0;
	// look at one coin at a time

trykhov / extractMin.js

Created June 21, 2020 18:34

	// Assume the heap is represented as an array list: heap = [...]
	// Assume we're dealing with a min-heap

	function extractMin() {
	// swap the root with the last node
	let temp = heap[0];
	heap[0] = heap[heap.length - 1];
	heap[heap.length - 1] = temp;

	// pull out the last node

trykhov / siftDown.js

Created June 21, 2020 18:25

	// Assume heap is represented as an array list: heap = [...]
	// Assume min-heap

	function siftDown(idx) {
	let leftChildIdx = (2 * idx) + 1;
	let rightChildIdx = (2 * idx) + 2;
	// base case
	// make sure the heap has children
	// it has to at least have a left child
	if(leftChildIdx >= heap.length) return;

trykhov / insertNode.js

Last active June 21, 2020 09:23

Inserting nodes into a heap

	// Assume the heap is represented as an array list: heap = [...]
	// Assume we're dealing with a min-heap

	function insertNode(node) {
	// add the new node to the end of the list
	heap.push(node);
	// get the index of the new node
	let lastIdx = heap.length - 1;
	// find the parent of the new node
	let parentIdx = lastIdx % 2 === 0 ? Math.floor(lastIdx / 2) - 1 : Math.floor(lastIdx / 2);

trykhov / siftUp.js

Last active June 18, 2020 06:31

	// Suppose our heap is an array: heap = [...]
	// assume min-heap
	function siftUp(idx) {
	// can't sift up further than the root
	if(idx === 0) return heap[0];
	// odd idx means that the child node is the left child
	// even idx means that the child node is the right child
	let parentIdx = idx % 2 === 1 ? Math.floor(idx / 2) : Math.floor(idx / 2) - 1;
	// for a min-heap, we ask if the parent > child
	// for a max-heap, we would ask if the parent < child

trykhov / topsort.js

Created June 8, 2020 23:12

	// assuming our adjacency matrix is {A: [B, C, D], B:[D, E], ...}
	// assuming that our vertices have the following properties:
	// 1. (boolean) visited

	// ASSUME graph is a DAG
	function topSort(adj) {
	// get the number of vertices in the DAG
	let numV = Object.keys(adj).length;
	// initialize resulting array
	let res = Array.new(numV).fill(null);

trykhov / cyclicGraphDetection.js

Last active February 18, 2021 17:39

	// assuming our adjacency matrix is {A: [B, C, D], B:[D, E], ...}
	// assuming that our vertices have the following properties:
	// 1. (boolean) visited
	// 2. (boolean) explore

	function cyclicGraphDetection(adj) {
	// get all the vertices from the adjacency matrix
	let vertices = Object.keys(adj);
	// look through all the vertices in the graph
	for(let vertex of vertices) {

trykhov / bfs.js

Last active May 15, 2020 04:35

BFS

	// assuming that the input is an adjacency list
	// e.g adj = {A:[B,C,D], B:[E,F], ... }

	function bfs(adj, s, t) {
	// adj is the adjacency list
	// s is the starting vertex
	// t is the final destination

	// initialize the queue
	let queue = [];

trykhov / dfs.js

Created May 15, 2020 00:59

DFS demo code

	// assuming that the input is an adjacency list
	// e.g adj = {A: [B,C], B:[D,F], ... }
	function dfs(adj, v, t) {
	// adj is the adjacency list
	// v is the node that's being visited
	// t is the final destination

	// these are the base cases
	// either reach the destination or has already been visited
	if(v === t) return true;

Try trykhov