Skip to content

Instantly share code, notes, and snippets.

@WrungCodes

WrungCodes/dsa.js

Created September 28, 2024 22:05
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save WrungCodes/37bbdc5746f0e11db8ce8b42c14b8f3f to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save WrungCodes/37bbdc5746f0e11db8ce8b42c14b8f3f to your computer and use it in GitHub Desktop.
Download ZIP
Raw
dsa.js
// Find two numbersbers that add up target
/**
| 0 | 1 | 2 | 3 | 4 |
^ ^
low high
*/
const sum = (array, target) => {
let low = 0
let high = array.length - 1
while( low < high ){
const sum = array[low] + array[high]
if(sum === target){
return [array[low], array[high]]
}else if( sum > target){
high--
}else{
low++
}
}
return []
}
// console.log(sum([ 0, 1, 2, 3, 4], 6))
// Find the max sum of an array of integers, only taking `k` items from the right and left side
/**
| 8 | 1 | 2 | 3 | 4 | 10 | 1 | 12 | 3 | 4 |
^ ^
left right
| 8 | 1 | 2 | 3 | 4 | 10 | 1 | 12 | 3 | 4 | === + right - left === +4 - 2 then shift right and left
^ ^
left right
*/
const maxSum = (array, k) => {
let right = k - 1
let left = array.length - 1
let sum = 0
for(let i = 0; i < k; i++){
sum += array[i]
}
let max = sum
for(let i = 0; i < k; i++){
sum += array[right--] - array[left--]
max = Math.max(max, sum)
}
return max
}
// console.log(maxSum([ 8, 1, 2, 3, 4, 10, 1, 12, 3, 4], 4))
/**
| 1 | -1 | 2 | -3 | 4 |
^ ^
prev cur
[-3,4,-1,2,1,-5]
local = 0
-3 or 0 + -3
4 or -3 + 4
-1 or 4 + -1
2 or 3 + 2
1 or 5 + 1
-5 or 6 + -5
local = 1
max = 6
*/
// Find the maximun sum of contiguous elements in an array
const maxSubArraySum = (array) => {
let max = array[0]
for (let i = 1; i < array.length; i++){
// console.log(`take ${array[i]} or ${array[i]} + ${array[i - 1]}, ${Math.max(array[i], array[i] + array[i - 1])} taken, max was ${max} but now ${Math.max(max, Math.max(array[i], array[i] + array[i - 1]))}`)
array[i] = Math.max(array[i], array[i] + array[i - 1])
max = Math.max(max, array[i])
}
return max
}
// console.log(maxSubArraySum([-3,4,-1,2,1,-5]))
// Find the max profit from buying and selling a stock given their daily prices
const maxProfit = (array) => {
let maxProfit = 0
let min = Infinity
// let min = 0
// let mem = {}
// for(let i = 1; i < array.length; i++){
// if(array[min] >= array[i]){
// min = i
// }else{
// maxProfit = Math.max(maxProfit, array[i] - array[min])
// // mem[maxProfit] = [min, i]
// }
for(let i = 0; i < array.length; i++){
min = Math.min(min, array[i])
maxProfit = Math.max(maxProfit, array[i] - min)
}
// console.log(mem)
return maxProfit
}
// console.log(maxProfit([1, 2, 3]))
// Return the length of the longest substring without repeating
const longestSubstring = (word) => {
let map = new Map()
let max = 0
for(let low = 0, high = 0; high < word.length; high++){
if(map.has(word[high])){
low = Math.max(low, map.get(word[high]) + 1)
}
map.set(word[high], high)
max = Math.max(max, (high - low) + 1)
}
return max
}
// console.log(longestSubstring('ehnedjeddme'))
// return the most common words in descending order
const mostCommonWords = (text) => {
const words = text.toLowerCase().match(/\b(\w+)\b/g)
let map = new Map()
let max = 0
let mostCommonWords = []
for(let i = 0; i < words.length; i++){
const newCount = (map.get(words[i]) || 0) + 1
map.set(words[i], newCount)
if(newCount > max){
max = newCount
mostCommonWords = [words[i]]
}else if(newCount == max){
mostCommonWords.push(words[i])
}
}
return mostCommonWords
}
console.log(mostCommonWords('this is a big disgrace; is it not. yes it is'))
const mostCommonWordsWithBan = (text, ban) => {
const words = text.toLowerCase().match(/\b(\w+)\b/g)
const banWordsSet = new Set(ban.map( w => w.toLowerCase()))
let map = new Map()
let max = 0
let mostCommonWords = []
for(let i = 0; i < words.length; i++){
if(!banWordsSet.has(words[i])){
const newCount = (map.get(words[i]) || 0) + 1
map.set(words[i], newCount)
if(newCount > max){
max = newCount
mostCommonWords = [words[i]]
}else if(newCount == max){
mostCommonWords.push(words[i])
}
}
}
return mostCommonWords
}
// console.log(mostCommonWordsWithBan('this is a big disgrace; is it not? yes it is not.', ['is', 'it']))
// Find two numbersbers that add up to the target value. Return empty array if not found
const twoSum = ( array, target ) => {
const map = new Map()
for(let i = 0; i < array.length; i++){
if(map.has(target - array[i])){
return [map.get(target - array[i]), i]
}
map.set(array[i], i)
}
return []
}
// console.log(twoSum( [150, 100, 200], 150 ))
// Find the numbersber of subarrays that add up to k
// const subarraySum = ( array, target) => {
// }
// console.log(subarraySum([1, 1, 1], 1))
const isPalindrome = (text) => {
const len = Math.floor(text.length/2)
for(let i = 0; i < len; i++){
if(text[i].toLowerCase() !== text[text.length - 1 - i].toLowerCase()){
return false
}
}
return true
}
// console.log(isPalindrome('Avid Diva'))
function ListNode(val, next = null) {
this.val = val;
this.next = next;
}
function createListFromArray(values) {
let dummy = new ListNode(0);
let current = dummy;
for (let val of values) {
current.next = new ListNode(val);
current = current.next;
}
return dummy.next;
}
// // Create lists from arrays
// const list1 = createListFromArray(['he', 'll', 'o']);
// const list2 = createListFromArray(['hel', 'lo']);
const mergeTwoList = (list1, list2) => {
if(!list1 || !list2){
return list1 || list2
}
// sort out the head and current pointer of the list
let head, current
if(list1.val > list2.val){
head = list2
list2 = list2.next
}else{
head = list1
list1 = list1.next
}
current = head
// looping through list1 and list2
while(list1 !== null && list2 !== null){
if(list1.val > list2.val){
current.next = list2
list2 = list2.next
}else{
current.next = list1
list1 = list1.next
}
current = current.next
}
current.next = list1 === null ? list2 : list1
return head
}
const numbersberList1 = createListFromArray([1, 4, 5]);
const numbersberList2 = createListFromArray([2, 6]);
// console.log(mergeTwoList(numbersberList1, numbersberList2))
const hasSameData = (list1, list2) => {
let index1 = 0
let index2 = 0
while(list1 !== null && list2 !== null){
const char1 = list1.val[index1++]
const char2 = list2.val[index2++]
if(char1 !== char2)
{
return false
}
if(index1 >= list1.val.length){
list1 = list1.next
index1 = 0
}
if(index2 >= list2.val.length){
list2 = list2.next
index2 = 0
}
}
return list1 === null && list2 === null && index1 === 0 && index2 === 0
}
const list1 = createListFromArray(['he', 'll', 'o']);
const list2 = createListFromArray(['hel', 'lo']);
// console.log(hasSameData(list1, list2))
const isParenthesesValid = (text) => {
const map = new Map([['(', ')'], ['[', ']'], ['{', '}']])
const stack = []
for(let i = 0; i < text.length; i++){
if(map.has(text[i])){
stack.push(map.get(text[i]))
}else if( stack.pop() !== text[i]) {
return false
}
}
return stack.length === 0
}
// console.log(isParenthesesValid('([]{})'))
// console.log(isParenthesesValid('()[]{}'))
const dailyTemperatures = (array) => {
const stack = []
const answer = []
for(let i = array.length - 1; i >= 0; i--){
while(stack.length > 0 && array[i] >= array[stack[stack.length - 1]]){
stack.pop()
}
if(stack.length > 0){
// console.log(stack[stack.length - 1] - i)
answer[i] = stack[stack.length - 1] - i;
}
stack.push(i)
}
return answer
}
// console.log(dailyTemperatures([20, 19, 12, 30, 100]))
function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
function createTreeFromArray(arr) {
if (arr.length === 0 || arr[0] === null) return null;
let root = new TreeNode(arr[0]);
let queue = [root];
let i = 1;
while (queue.length > 0 && i < arr.length) {
let current = queue.shift();
if (arr[i] !== null) {
current.left = new TreeNode(arr[i]);
queue.push(current.left);
}
i++;
if (i < arr.length && arr[i] !== null) {
current.right = new TreeNode(arr[i]);
queue.push(current.right);
}
i++;
}
return root;
}
// const tree1 = createTreeFromArray([1, 2, 3, null, 4, 5, 6, 7, null]);
const diameterOfBinaryTree = (root) => {
let daimeter = 0
const depth = (node) => {
if(!node){
return 0
}
const leftDepth = depth(node.left)
const rightDepth = depth(node.right)
daimeter = Math.max(daimeter, leftDepth + rightDepth)
return 1 + Math.max(leftDepth, rightDepth)
}
depth(root)
return daimeter
}
const tree1 = createTreeFromArray([1, 2, 3, null, 4, 5])
// console.log(diameterOfBinaryTree(tree1))
const rightSideViewDFS = (root) => {
const answer = []
const dfs = (node, level = 0) => {
if(!node) return
if(answer.length === level){
answer.push(node.val)
}
dfs(node.right, level + 1)
dfs(node.left, level + 1)
}
dfs(root)
return answer
}
// console.log(rightSideViewDFS(tree1))
const rightSideViewBFS = (root) => {
if(!root) return []
const answer = []
const queue = [root]
while(queue.length){
const levelSize = queue.length
for(let i = 0; i < levelSize; i++){
const node = queue.shift()
if(i === levelSize - 1){
answer.push(node.val)
}
if(node.left) {
queue.push(node.left)
}
if(node.right){
queue.push(node.right)
}
}
}
return answer
}
// console.log(rightSideViewDFS(tree1))
const canFinish = (courses, prerequisites) => {
const graph = new Map()
for(let i = 0; i < courses; i++){
graph.set(i, [])
}
prerequisites.forEach(([dependant, requisite]) => {
graph.get(requisite).push(dependant)
});
// const visited = new Set()
// const onStack = new Set()
const state = []
const dfsHasCyclicDependecy = (node) => {
if(state[node] === 1){
return true
}
if(state[node] === 2){
return false
}
// if(onStack.has(node)){
// return true
// }
// if(visited.has(node)){
// return false
// }
// onStack.add(node)
// visited.add(node)
state[node] = 1
for(const next of graph.get(node)){
if(dfsHasCyclicDependecy(next)){
return true
}
}
state[node] = 2
// onStack.delete(node)
return false
}
for(let i = 0; i < courses; i++){
if(dfsHasCyclicDependecy(i)){
return false
}
}
return true
}
// console.log(canFinish(3, [[0, 1], [2, 0], [1, 2]]))
const criticalConnections = (nodes, connections) => {
const critical = []
const graph = new Map()
connections.forEach(([u, v]) => {
if(!graph.has(u)){
graph.set(u, [])
}
if(!graph.has(v)){
graph.set(v, [])
}
graph.get(u).push(v)
graph.get(v).push(u)
})
const dfs = (node, parent = null, depth = 0, group = []) => {
group[node] = depth
for(const neigbour of (graph.get(node) || [])) {
if(neigbour === parent){
continue
}
if(group[neigbour] === undefined){
dfs(neigbour, node, depth + 1, group)
}
group[node] = Math.min(group[node], group[neigbour])
if(group[neigbour] >= depth + 1){
critical.push([node, neigbour])
}
}
}
dfs(0)
return critical
}
// console.log(criticalConnections(4, [[0, 1], [1, 2], [2, 0], [1, 3]]))
const mergeSort = (array1, array2) => {
const array = Array(array1.length + array2.length)
for(let index = 0, index1 = 0, index2 = 0; index < array.length; index++){
if(index2 >= array2.length || (index1 < array1.length && array1[index1] <= array2[index2])){
array[index] = array1[index1]
index1 += 1
}else{
array[index] = array2[index2]
index2 += 1
}
}
return array
}
// console.log(mergeSort([1,2,5], [3,4,6]))
const splitSort = (arr) => {
if(arr.length <= 1){
return arr
}
if(arr.length === 2){
return arr[0] < arr[1] ? arr : [arr[1], arr[0]]
}
const half = Math.floor(arr.length / 2)
const left = splitSort(arr.slice(0, half))
const right = splitSort(arr.slice(half))
return mergeSort(left, right)
}
// console.log(splitSort([1,2,5,3,4,6]))
const mergeIntervals = (intervals) => {
intervals.sort((a, b) => a[0] - b[0])
const merged = [intervals[0]]
for(let i = 1; i < intervals.length; i++){
const lastMerged = merged[merged.length - 1]
const [ start, end ] = intervals[i]
if(start <= lastMerged[1]){
lastMerged[1] = Math.max(end, lastMerged[1])
}else{
merged.push(intervals[i])
}
}
return merged
}
// console.log(mergeIntervals([[5,6], [1,3], [2,4]]))
const sortColors = (numbers) => {
let left = 0
let right = numbers.length - 1
let cur = 0
while(cur <= right ){
if(numbers[cur] === 0){
[numbers[cur], numbers[left]] = [numbers[left], numbers[cur]]
cur++
left++
}
else if(numbers[cur] === 2){
[numbers[cur], numbers[right]] = [numbers[right], numbers[cur]]
right--
}
else{
cur++
}
}
return numbers
}
// console.log(sortColors([2, 0, 1]))
const fib = (number, cache = new Map()) => {
if(number < 0){
return 0
}
if(number < 2){
return number
}
if(cache.has(number)){
return cache.get(number)
}
const result = fib(number - 1) + fib(number - 2)
cache.set(number, result)
return result
}
// console.log(fib(10))
const fractionalKnapsack = (inputs, max) => {
let value = 0
let weight = 0
let items = []
inputs.sort((a, b) => a.value/a.weight - b.value/b.weight)
while(weight < max && inputs.length){
const bestRatioItem = inputs.pop()
// weight + bestRatioItem.weight <= max
if(weight + bestRatioItem.weight <= max){
bestRatioItem.partition = 1
}else{
bestRatioItem.partition = (max - weight)/bestRatioItem.weight
}
items.push(bestRatioItem)
weight += bestRatioItem.weight * bestRatioItem.partition
value += bestRatioItem.value * bestRatioItem.partition
}
return {value, weight, items}
}
// console.log(
// fractionalKnapsack(
// [
// { value: 1, weight: 1 },
// { value: 4, weight: 3 },
// { value: 5, weight: 4 },
// { value: 7, weight: 5 },
// ],
// 7
// )
// );
// Returns true if arr[] can be partitioned into two subsets of equal sum, otherwise false
function findPartition(arr, n) {
let sum = arr.reduce((a, b) => a + b, 0);
if (sum % 2 !== 0) return false;
let part = Array(sum / 2 + 1).fill(false);
part[0] = true; // A subset sum of 0 is always possible
for (let i = 0; i < n; i++) {
for (let j = sum / 2; j >= arr[i]; j--) {
// If a subset with sum 'j - arr[i]' exists, then a subset with sum 'j' can be formed
if (part[j - arr[i]] === true) {
part[j] = true;
}
}
}
// Step 5: Check if there's a subset with sum equal to 'sum / 2'
return part[sum / 2];
}
function minCoins(coins, targeValue) {
let dp = new Array(targeValue + 1).fill(Infinity); // DP array for storing min coins for each value
dp[0] = 0; // Base case: 0 coins needed for value 0
// Fill dp array from 1 to V
for (let value = 1; value <= targeValue; value++) {
for (let coin of coins) {
if (coin <= value) {
// If using this coin leads to a solution, update the dp array accordingly
if (dp[value - coin] + 1 < dp[value]) {
dp[value] = dp[value - coin] + 1;
}
}
}
}
console.log(dp)
// dp[V] contains the minimum number of coins for value V
return dp[targeValue] !== Infinity ? dp[targeValue] : -1;
}
// console.log(minCoins([1, 2, 3], 6))
function getKnapSack(capacity, n, values, weights, lookup) {
// base case: when we cannot have take more items
if (capacity < 0) {
return Number.MIN_SAFE_INTEGER;
}
// Check capacity and items on zero
if(capacity === 0 || n < 0){
return 0;
}
// Unique key for map for memoization
const key = `${n}|${capacity}`;
// If the sub-problem is appearing for first time, solve it and store its result in the map
if (!lookup.has(key)){
// pick current item n in knapSack and recur
// for remaining items (n-1) with reduced capacity (capacity - weights[n])
const include = values[n] + getKnapSack(capacity - weights[n], n - 1, values, weights, lookup);
// leave current item n from knapSack and recurcive call for remaining items (n-1)
const exclude = getKnapSack(capacity, n - 1, values, weights, lookup);
// Assign max value we get by picking or leaving the current item
lookup.set(key, Math.max(include, exclude));
}
// return setting the value to the map
return lookup.get(key);
}
const fizzBuzz = (num) => {
for (var i = 1; i < num + 1; i++) {
if (i % 15 == 0) console.log("FizzBuzz");
else if (i % 3 == 0) console.log("Fizz");
else if (i % 5 == 0) console.log("Buzz");
else console.log(i);
}
}
function print_N_mostFrequentNumber(arr, N, K) {
let mp = new Map();
// Put count of all the
// distinct elements in Map
// with element as the key &
// count as the value.
for (let i = 0; i < N; i++) {
// Get the count for the
// element if already present in the
// Map or get the default value which is 0.
if (mp.has(arr[i])) {
mp.set(arr[i], mp.get(arr[i]) + 1)
} else {
mp.set(arr[i], 1)
}
}
// Create a list from elements of HashMap
let list = [...mp];
// Sort the list
list.sort((o1, o2) => {
if (o1[1] == o2[1])
return o2[0] - o1[0];
else
return o2[1] - o1[1];
})
document.write(K + " numbers with most occurrences are: ");
for (let i = 0; i < K; i++)
document.write(list[i][0] + " ");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment