input:  arr = [0, 1, 2, 3]

output: 4

const swapUntilCorrect = (arr: number[], idx: number) => {
	const element = arr[idx];
	console.table({ element, idx, arr });
	if (element === idx) return;
	if (element > arr.length - 1) return;
	[arr[element], arr[idx]] = [arr[idx], arr[element]];
	return swapUntilCorrect(arr, idx);
};

function getDifferentNumber(arr: number[]) {
	for (let idx = 0; idx < arr.length; idx++) {
		swapUntilCorrect(arr, idx);
	}

	for (let idx = 0; idx < arr.length; idx++) {
		if (arr[idx] !== idx) return idx;
	}

	return arr.length;
}

console.log(getDifferentNumber([0, 5, 4, 1, 3, 6, 2]));

0, 2, 3, 4
^ first iterateion, leave 0 as it is

0, 3, 2, 4 < swap 2 and 3, since 3 is not at the correct index
   ^
0, 4, 2, 3 < 4 cannot be swapped because 4 its out of range

0, 4, 2, 3 < 2 is at the correct index
      ^
0, 4, 2, 3 < 3 is at the correct index
         ^

now 1 is the missing number, since at 1st index, 4 is present instead of one

// [2,3,1,2,4,3]
//  L
//  R
//  L  R
function minSubArrayLen(target: number, nums: number[]): number {
	let variableIdx = 0;
	let sum = 0;
	let min = Infinity;

	for (let fixedIdx = 0; fixedIdx < nums.length; fixedIdx++) {
		const valueAtFixedIdx = nums[fixedIdx];
		sum += valueAtFixedIdx;

		while (sum >= target) {
			min = Math.min(min, fixedIdx - variableIdx + 1);
			const valueAtVariableIdx = nums[variableIdx];
			sum -= valueAtVariableIdx;
			variableIdx += 1;
		}
	}

	if (min === Infinity) {
		return 0;
	}

	return min;
}

[2, 3, 1, 2, 4, 3], target = 7
 0  1  2  3  4  5

- when sum is graeter than or equal to target, we need to shrink the window
  eg,
  2 + 3 + 1 + 2 = 8, 8 is greater than 7 ( set min length to 4 )

  shrink the window by removing 2
  3 + 1 + 2 = 6, 6 is less than 7 so break the loop

- when sum is less than target, we need to expand the window
  eg,
  2 + 3 = 5, 5 is less than 7
  expand the window by adding 1
  2 + 3 + 1 = 6, 6 is less than 7
  expand the window by adding 2
  2 + 3 + 1 + 2 = 8, 8 is greater than 7, set min length here
  shrink the window by removing 2
  3 + 1 + 2 = 6, 6 is less than 7
  expand the window by adding 4
  2 + 3 + 1 + 2 + 4 = 12, 12 is greater than 7, set min length here
  shrink the window by removing 2
  3 + 1 + 2 + 4 = 10, 10 is greater than 7, set min length here
  shrink the window by removing 3
  1 + 2 + 4 = 7, 7 is equal to 7, set min length here
  expand the window by adding 3
  2 + 3 + 1 + 2 + 4 + 3 = 15, 15 is greater than 7, set min length to Min(prevMin, 4)

const shortestSubarray = (nums: number[], target: number) => {
	// hold the sum to the elements at the ith index of the nums array
	const prefixSums = new Array(nums.length + 1).fill(0);
	for (let idx = 0; idx < nums.length; idx++) {
		prefixSums[idx + 1] = prefixSums[idx] + nums[idx];
	}

	console.log({ prefixSums });

	let minSubArrayLength = Infinity;
	// holds the index of the prefix sum
	const deque = [];

	for (let idx = 0; idx < prefixSums.length; idx++) {
		const sumAtIdx = prefixSums[idx];
		console.log('DEQUE__BEFORE', { idx, deque, sumAtIdx, minSubArrayLength });
		while (deque.length > 0 && sumAtIdx - prefixSums[deque[0]] >= target) {
			console.log('DEQUE__AFT--1', { idx, deque });
			const frontIdx = deque.shift();
			const newSubArrayLength = idx - frontIdx;
			minSubArrayLength = Math.min(minSubArrayLength, newSubArrayLength);
		}
		while (
			deque.length > 0 &&
			sumAtIdx <= prefixSums[deque[deque.length - 1]]
		) {
			console.log('DEQUE__AFT--2', { idx, deque });
			deque.pop();
		}
		deque.push(idx);
	}

	return minSubArrayLength === Infinity ? -1 : minSubArrayLength;
};

console.log(shortestSubarray([2, -1, 2], 3));

// Prefix sums hold the sum of the elements at the ith index of the nums array
// [0, 2, 1, 3]
//
// we remove from front if target is reached, set minLength and remove from deque
// we remove form back to keep the deque in monotonically increasing order

export const bestSeat = (seats: number[]) => {
	// [0, 1, 2, 3, 4, 5, 6]
	// [1, 0, 1, 0, 0, 0, 1] => 4
	let maxConsequtiveSeats: number[] = []; // O(N)
	let currentConsequtiveSeats: number[] = []; // O(N)
	for (let idx = 0; idx < seats.length; idx++) {
		const el = seats[idx];
		if (el !== 0) {
			if (maxConsequtiveSeats.length < currentConsequtiveSeats.length) {
				maxConsequtiveSeats = currentConsequtiveSeats;
			}
			currentConsequtiveSeats = []; // creating a new empty array is O(1)
			continue;
		}
		currentConsequtiveSeats.push(idx);
	}
	if (maxConsequtiveSeats.length === 0) {
		return -1;
	}
	if (maxConsequtiveSeats.length === 1) {
		return maxConsequtiveSeats[0];
	}
	const isEven = maxConsequtiveSeats.length % 2 === 0;
	const middle = Math.floor(maxConsequtiveSeats.length / 2);
	if (isEven) {
		return maxConsequtiveSeats[middle - 1];
	}
	return maxConsequtiveSeats[middle];
};

console.log(bestSeat([1, 0, 1, 0, 0, 0, 1]));
console.log(bestSeat([1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]));
console.log(bestSeat([1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1]));

array = [7, 6, 4, -1, 1, 2]
targetSum = 16

array = [-1, -5, -10, -1100, -1100, -1101, -1102, -9001]

true

package main

import "fmt"

func IsMonotonic(array []int) bool {
	isIncreasing := true
	isDecreasing := true
	for index := 0; index < len(array); index += 1 {

		el := array[index]

		nextEl, nextElErr := func() (int, error) {
			if index < len(array)-1 {
				return array[index+1], nil
			}
			return 0, fmt.Errorf("Index out of range")
		}()

		if nextElErr != nil {
			break
		}

    if (isIncreasing == false && isDecreasing == false) {
      break
    }

    if nextEl == el {
      continue
    }

		// increasing
		if nextEl > el {
			isDecreasing = false
			continue
		}

		// decreasing
		isIncreasing = false
	}
	return isIncreasing || isDecreasing
}

func main() {
	println("Hello World")
	println(IsMonotonic([]int{1, 1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 8, 9, 10, 11}))
}

array = [2, 1, 2, 2, 2, 3, 4, 2]
toMove = 2

[1, 3, 4, 2, 2, 2, 2, 2] // the numbers 1, 3, and 4 could be ordered differently

export function moveElementToEnd(
	array: number[],
	toMove: number,
	leftPointer: number = 0,
	rightPointer: number = array.length - 1
): number[] {
	const elAtLeftPointer = array[leftPointer];
	const elAtRightPointer = array[rightPointer];
	const isElAtLeftPointerEqToMove = elAtLeftPointer === toMove;
	const isElAtRightPointerEqToMove = elAtRightPointer === toMove;

	if (leftPointer >= rightPointer) return array;

	// if both left pointer and right pointer has the desired value
	if (isElAtLeftPointerEqToMove && isElAtRightPointerEqToMove) {
		// move left pointer value to right
		array.splice(leftPointer, 1);
		array.push(elAtLeftPointer);
		// since last element is already in a desired position move right pointer inward
		return moveElementToEnd(array, toMove, leftPointer, rightPointer - 1);
	}

	// swap el positions,
	// if right has non desired value
	// if left has desired value
	if (isElAtLeftPointerEqToMove && !isElAtRightPointerEqToMove) {
		array.splice(leftPointer, 1, elAtRightPointer);
		array.splice(rightPointer, 1, elAtLeftPointer);
		// since now the left pointer will not have the desired value move it right, by one place
		// since now the right pointer will have the desired value move it left, by one place
		return moveElementToEnd(array, toMove, leftPointer + 1, rightPointer - 1);
	}

	// if left is not having desired value move on to next value
	if (!isElAtRightPointerEqToMove && isElAtRightPointerEqToMove) {
		// since right is already at desired value move left
		return moveElementToEnd(array, toMove, leftPointer + 1, rightPointer - 1);
	}

	return moveElementToEnd(array, toMove, leftPointer + 1, rightPointer);
}

export function moveElementToEnd(array: number[], toMove: number): number[] {
	let prevToMoveElPoss = 0;
	array.forEach((currentEl, currentIndex) => {
		if (currentEl !== toMove) {
			// avoids 0, 0
			if (prevToMoveElPoss != currentIndex) {
				// swapping
				array[prevToMoveElPoss] = array[currentIndex];
				array[currentIndex] = toMove;
			}
			prevToMoveElPoss += 1;
		}
	});
	return array;
}

arrayOne = [-1, 5, 10, 20, 28, 3]
arrayTwo = [26, 134, 135, 15, 17]

[28, 26]

type Pair = [number, number] | [];
const assendingSorter = (a: number, b: number) => a - b;

export const smallestDifference = (
  arrayOne: number[],
  arrayTwo: number[],
  smallestPairDiscovered: Pair = [],
  arrayOnePointer: number = 0,
  arrayTwoPointer: number = 0,
  isArraysSorted = false
): Pair => {
  const arrayOneSorted = isArraysSorted
    ? arrayOne
    : arrayOne.sort(assendingSorter);
  const arrayTwoSorted = isArraysSorted
    ? arrayTwo
    : arrayTwo.sort(assendingSorter);

  const arrayOneMaxIndex = arrayOneSorted.length - 1;
  const arrayTwoMaxIndex = arrayTwoSorted.length - 1;

  const isArrayOnePointerExhausted = arrayOnePointer > arrayOneMaxIndex;
  const isArrayTwoPointerExhausted = arrayTwoPointer > arrayTwoMaxIndex;

  // A: [ -01, 03, 05, 010, 020, 28 ]
  //                             X
  // B: [ 15, 17, 26, 134, 135,     ]
  //              X
  // There is further no possible solutions,
  // since the smallest possible pair is already found.
  if (isArrayOnePointerExhausted || isArrayTwoPointerExhausted)
    return smallestPairDiscovered;

  const currentPair: Pair = [
    arrayOne[isArrayOnePointerExhausted ? arrayOneMaxIndex : arrayOnePointer],
    arrayTwo[isArrayTwoPointerExhausted ? arrayTwoMaxIndex : arrayTwoPointer],
  ];

  const [firstValue, lastValue] = currentPair;

  const currentPairDiff: number = Math.abs(lastValue - firstValue);

  if (currentPairDiff === 0) return currentPair;

  const isSmallestPairDiscoveredValid = smallestPairDiscovered.length === 2;
  const [smallestPairFirstValue = 0, smallestPairLastValue = 0] =
    isSmallestPairDiscoveredValid ? smallestPairDiscovered : [];
  const smallestPairDiscoveredDiff = Math.abs(
    smallestPairLastValue - smallestPairFirstValue
  );

  const newPair =
    isSmallestPairDiscoveredValid &&
      smallestPairDiscoveredDiff < currentPairDiff
      ? smallestPairDiscovered
      : currentPair;

  if (firstValue > lastValue)
    return smallestDifference(
      arrayOne,
      arrayTwo,
      newPair,
      arrayOnePointer,
      arrayTwoPointer + 1
    );

  return smallestDifference(
    arrayOne,
    arrayTwo,
    newPair,
    arrayOnePointer + 1,
    arrayTwoPointer
  );
};

console.log(smallestDifference([-1, 5, 10, 20, 28, 3], [26, 134, 135, 15, 17]));

array = [12, 3, 1, 2, -6, 5, -8, 6]

[[ -8, 2, 6 ], [ -8, 3, 5 ], [ -6, 1, 5 ]]

type Triplet = [number, number, number];
type SumPair = [number, number];

export function threeNumberSum(array: number[], targetSum: number): Triplet[] {
	// O(N)
	const sumCombos: { [T: string]: SumPair[] } = {};
	// O(N)
	for (const num of array) {
		// O(N^2)
		for (const subNum of array) {
			if (num !== subNum) {
				const sum = num + subNum;
				const existingKey = sumCombos[sum];
				const newPair: SumPair = [num, subNum];
				if (existingKey) {
					sumCombos[sum] = [...existingKey, newPair];
					continue;
				}
				sumCombos[sum] = [newPair];
			}
		}
	}

	// O(N)
	const tripletsAsObj: { [T: string]: Triplet } = {};
	// O(N)
	const subComboKeys = Object.keys(sumCombos).map(el => +el);
	// O(N)
	for (const num of array) {
		// O(N^2)
		for (const sum of subComboKeys) {
			const sumAsNum = +sum;
			if (num + sumAsNum === targetSum) {
				const pairs = sumCombos[sum];
				// O(N^3)
				for (const pair of pairs) {
					if (!pair.includes(num)) {
						const triplet = [...pair, num].sort((a, b) => a - b) as Triplet;
						tripletsAsObj[triplet.join(',')] = triplet;
					}
				}
			}
		}
	}
	// O(N)
	return (
		Object.values(tripletsAsObj)
			// O(N)
			.sort((a, b) => a[2] - b[2])
			// O(N)
			.sort((a, b) => a[1] - b[1])
			// O(N)
			.sort((a, b) => a[0] - b[0])
	);
}

type Triplet = [number, number, number];

export const threeNumberSum = (
	array: number[],
	targetAmount: number,
	pairsFound: Triplet[] = []
): any => {
	// Sort in place,
	// O(n) time, O(1) space
	const sortedArray = array.sort((a, b) => a - b);

	const sortedArrayLength = sortedArray.length;
	const sortedArrayMaxIndex = sortedArrayLength - 1;

	// O(n)
	for (
		let fixedPointer = 0;
		fixedPointer <= sortedArrayMaxIndex;
		fixedPointer += 1
	) {
		const fixedPointerValue = sortedArray[fixedPointer];
		let leftPointer = fixedPointer + 1;
		let rightPointer = sortedArrayMaxIndex;

		if (leftPointer > sortedArrayMaxIndex) break;
		if (rightPointer < 0) break;

		// O(n^2)
		for (let index = 0; index <= sortedArrayMaxIndex; index += 1) {
			const leftPointerValue = sortedArray[leftPointer];
			const rightPointerValue = sortedArray[rightPointer];

			const currentSum =
				fixedPointerValue + leftPointerValue + rightPointerValue;

			// move to next pointer iteration
			if (leftPointerValue >= rightPointerValue) break;

			if (currentSum < targetAmount) {
				leftPointer += 1;
				continue;
			}

			if (currentSum > targetAmount) {
				rightPointer -= 1;
				continue;
			}

			// if triplet is found
			if (currentSum === targetAmount) {
				pairsFound.push([
					fixedPointerValue,
					leftPointerValue,
					rightPointerValue,
				]);
				// if triplet is found,
				// close the gap between left and right pointer
				leftPointer += 1;
				rightPointer -= 1;
				continue;
			}

			// break if all conditions fail
			break;
		}
	}
	return pairsFound;
};

console.log(threeNumberSum([12, 3, 1, 2, -6, 5, -8, 6], 0));

Input = [2, 5, -3, -4, 6, 7, 2]
Output = [5, 6, 6, 6, 7, -1, 5]

export const nextGreaterElement = (array: number[]): number[] => {
	// resultArray: store the next greater element at each index
	// stack: Stores index of elements as we iterate through the array (only for the first loop)

	const resultArray: number[] = new Array(array.length).fill(-1);
	const stack: number[] = [];

	for (let index = 0; index < array.length * 2; index += 1) {
		const currentIdx = index % array.length; // 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6
		const currentEl = array[currentIdx];

		// if the element at the top of the stack is less than the current element
		// then the corresponding index in the resultArray will be the current element
		while (
			stack.length > 0 &&
			resultArray[stack[stack.length - 1]] < currentEl
		) {
			const idx = stack.pop() as number; // remove idx from the stack
			resultArray[idx] = currentEl; // updated the resultArray[idx] with the current element
		}

		if (index >= array.length) continue;
		stack.push(currentIdx);
	}

	return resultArray;
};

nextGreaterElement([2, 5, -3, -4, 6, 7, 2]);

tree =    1
        /   \
       2     3
      /  \    \
     4    5    6
            / \
           7   8

16

interface Node {
	value: number;
	left?: Node | null;
	right?: Node | null;
}

let total = 0;
const calculateNodeDepths = (
	currentNodeObject: Node | null = { value: 0 },
	currentDepth = 0
): number => {
	if (!currentNodeObject) return currentDepth;
	// both left and right needs to be called
	[currentNodeObject?.left, currentNodeObject?.right].forEach(el => {
		if (el?.value) {
			if (currentNodeObject?.value) {
				// map current child to parent
				total += currentDepth + 1;
			}
		}
		// call child of current left and right node.
		calculateNodeDepths(el, currentDepth + 1);
	});
	return total;
};

export function nodeDepths(root: BinaryTree) {
	return calculateNodeDepths(root);
}

// This is the class of the input binary tree.
class BinaryTree {
	value: number;
	left: BinaryTree | null;
	right: BinaryTree | null;

	constructor(value: number) {
		this.value = value;
		this.left = null;
		this.right = null;
	}
}

const root = new BinaryTree(1);
root.left = new BinaryTree(2);
root.left.left = new BinaryTree(4);
root.left.left.left = new BinaryTree(8);
root.left.left.right = new BinaryTree(9);
root.left.right = new BinaryTree(5);
root.right = new BinaryTree(3);
root.right.left = new BinaryTree(6);
root.right.right = new BinaryTree(7);
const actual = nodeDepths(root);
console.log(actual, 'Actual');

// Do not edit the class below except
// for the depthFirstSearch method.
// Feel free to add new properties
// and methods to the class.
export class Node {
  name: string;
  children: Node[];

  constructor(name: string) {
    this.name = name;
    this.children = [];
  }

  addChild(name: string) {
    this.children.push(new Node(name));
    return this;
  }

  depthFirstSearch(
    array: string[] = [],
    node: { name: string; children: Node[] } = {
      name: this.name,
      children: this.children,
    }
  ) {
    array.push(node.name);
    node.children.forEach(el => this.depthFirstSearch(array, el));
    return array;
  }
}

const graph = new Node('A');
graph.addChild('B').addChild('C').addChild('D');
graph.children[0].addChild('E').addChild('F');
graph.children[2].addChild('G').addChild('H');
graph.children[0].children[1].addChild('I').addChild('J');
graph.children[2].children[0].addChild('K');

console.log(graph.depthFirstSearch());

tree =   10
       /     \
      5      15
    /   \   /   \
   2     5 13   22
 /           \
1            14

true

class BST {
	value: number;
	left: BST | null;
	right: BST | null;

	constructor(value: number) {
		this.value = value;
		this.left = null;
		this.right = null;
	}
}

function* generateQueue(
	node: BST,
	leftLimit: number = -Infinity,
	rightLimit: number = Infinity
): Generator<{ value: number; isValid: boolean }> {
	const { value, left, right } = node;

	console.table({ value, leftLimit, rightLimit });

	if (value < leftLimit || value >= rightLimit) {
		yield { value, isValid: false };
		return;
	}

	yield { value, isValid: true };

	if (left?.value) yield* generateQueue(left, leftLimit, value);

	if (right?.value) yield* generateQueue(right, value, rightLimit);
}

export function validateBst(tree: BST) {
	for (const isValid of generateQueue(tree)) {
		console.log(isValid);
		if (!isValid.isValid) return isValid.isValid;
	}
	return true;
}

const root = new BST(10);
root.left = new BST(5);
root.left.left = new BST(2);
root.left.left.left = new BST(1);
root.left.right = new BST(5);
root.right = new BST(15);
root.right.left = new BST(13);
root.right.left.right = new BST(14);
root.right.right = new BST(22);
console.log(validateBst(root));

tree =     1
        /     \
       3       -2
     /   \    /  \
    6    -5  5    2
  /
 2

Input = 4, 3
Output = 10 ways to traverse the graph

export function numberOfWaysToTraverseGraph(
	width: number,
	height: number
): number {
	if (height === 1 || width === 1) return 1;
	return (
		numberOfWaysToTraverseGraph(width - 1, height) +
		numberOfWaysToTraverseGraph(width, height - 1)
	);
}

export function numberOfWaysToTraverseGraph(
	width: number,
	height: number
): number {
	// O(n*m) ST
	const resultArray = new Array(height)
		.fill(0)
		.map(() => new Array(width).fill(0));

	// O(n) T
	for (let row = 0; row < height; row++) {
		// O(m) T
		for (let col = 0; col < width; col++) {
			// edges of grid
			if (row === 0 || col === 0) {
				resultArray[row][col] = 1;
				continue;
			}
			resultArray[row][col] =
				resultArray[row - 1][col] + resultArray[row][col - 1];
			continue;
		}
	}

	return resultArray[height - 1][width - 1];
}

export function hasSingleCycle(array: number[]) {
	let visitedCount = 0;
	let fistIdxVisited = 0;
	let idx = 0;
	while (visitedCount < array.length) {
		if (idx === 0) fistIdxVisited += 1;
		if (fistIdxVisited > 1) break; // you are going in circles

		const jumpTo = array[idx];
		let jumpToIdx = (idx + jumpTo) % array.length;
		if (jumpToIdx < 0) {
			jumpToIdx = array.length + jumpToIdx;
		}
		idx = jumpToIdx;
		visitedCount += 1;
	}

	return visitedCount === array.length && idx === 0;
}

[2, 3, 1, -4, -4,  2] --- jump to values
 0, 1, 2,  3,  4,  5  --- index
0 -> 2 -> 3 -> 5 -> 1 -> 4 -> 0  --- no of jumps to reach start idx again === 6,
                                     you where already at 0th idx in the beginning, so ignore the first jump

[2, 3, 1, -4, -4] --- jump to values
 0, 1, 2,  3,  4  --- index

```ts
10 % 5 = 0 // returns the first idx
6 % 5 = 1
5 % 5 = 1
-22 % 5 = -2 // the value is right, but we need to normalise it to 3 ( send idx from last )
             // array.length + -2 = 5 + -2 = 3

[1, -1, 1, -1] -- the same cycle is played multiple times

class Airport {
	name: string;
	destinations: Airport[];

	constructor(name: string) {
		this.name = name;
		this.destinations = [];
	}

	addDestination(airport: Airport) {
		this.destinations.push(airport);
	}
}

interface Graph {
	[key: string]: Airport;
}

const getReachableAirports = (
	graph: Graph,
	originatingAirport: string,
	airport: string = originatingAirport,
	reachableAirports: Set<string> = new Set()
): Set<string> => {
	const airportNode = graph[airport];
	const destinations = airportNode.destinations;

	for (let destination of destinations) {
		if (reachableAirports.has(destination.name)) continue;
		if (destination.name === originatingAirport) continue;
		reachableAirports.add(destination.name);
		getReachableAirports(
			graph,
			originatingAirport,
			destination.name,
			reachableAirports
		);
	}

	return reachableAirports;
};

const getUnreachableAirports = (graph: Graph, startingAirport: string) => {
	const unreachableAirports: Set<[string, number]> = new Set();
	const reachableAirports = getReachableAirports(graph, startingAirport);
	for (let airport in graph) {
		if (reachableAirports.has(airport) || airport === startingAirport) continue;
		unreachableAirports.add([
			airport,
			getReachableAirports(graph, airport).size,
		]);
	}
	return Array.from(unreachableAirports).sort((a, b) => b[1] - a[1]);
};

export function airportConnections(
	airports: string[],
	routes: [string, string][],
	startingAirport: string
) {
	const graph: Graph = {};

	for (let airport of airports) {
		if (graph[airport] !== undefined) continue;
		graph[airport] = new Airport(airport);
	}

	for (let route of routes) {
		const [source, destination] = route;
		graph[source].addDestination(graph[destination]);
	}

	let unreachableAirports = getUnreachableAirports(graph, startingAirport);
	const destinationsAdded = [];
	while (unreachableAirports.length > 0) {
		console.log(unreachableAirports);
		graph[startingAirport].addDestination(graph[unreachableAirports[0][0]]);
		destinationsAdded.push([startingAirport, unreachableAirports[0][0]]);
		unreachableAirports = getUnreachableAirports(graph, startingAirport);
	}

	console.log(destinationsAdded);

	return destinationsAdded.length;
}

console.log(
	airportConnections(
		[
			'BGI',
			'CDG',
			'DEL',
			'DOH',
			'DSM',
			'EWR',
			'EYW',
			'HND',
			'ICN',
			'JFK',
			'LGA',
			'LHR',
			'ORD',
			'SAN',
			'SFO',
			'SIN',
			'TLV',
			'BUD',
		],
		[
			['DSM', 'ORD'],
			['ORD', 'BGI'],
			['BGI', 'LGA'],
			['SIN', 'CDG'],
			['CDG', 'SIN'],
			['CDG', 'BUD'],
			['DEL', 'DOH'],
			['DEL', 'CDG'],
			['TLV', 'DEL'],
			['EWR', 'HND'],
			['HND', 'ICN'],
			['ICN', 'JFK'],
			['JFK', 'LGA'],
			['EYW', 'LHR'],
			['LHR', 'SFO'],
			['SFO', 'SAN'],
			['SFO', 'DSM'],
			['SAN', 'EYW'],
		],
		'LGA'
	)
);

export function minNumberOfJumps(array: number[]) {
	const jumps = new Array(array.length).fill(Infinity);
	jumps[0] = 0; // you start at the first index, so you don't need to jump

	for (let fixedIdx = 0; fixedIdx < array.length; fixedIdx++) {
		const fixed = array[fixedIdx];
		for (let variableIdx = 0; variableIdx < fixedIdx; variableIdx++) {
			const variable = array[variableIdx];

			const fixedjumps = jumps[fixedIdx];
			const variablejumps = jumps[variableIdx];

			const isItPossibleToReachFixedIdx = variable >= fixedIdx - variableIdx;

			if (!isItPossibleToReachFixedIdx) continue;

			const maxJump = Math.min(fixedjumps, variablejumps + 1);
			jumps[fixedIdx] = maxJump;
		}
	}
	console.log(jumps);
	return jumps[array.length - 1];
}

console.log(minNumberOfJumps([3, 4, 2, 1, 2, 3, 7, 1, 1, 1, 3])); // 4

function jobScheduling(
	startTime: number[],
	endTime: number[],
	profit: number[]
): number {
	const times = endTime
		.map((_, idx) => [startTime[idx], endTime[idx], profit[idx]])
		.sort((a, b) => a[1] - b[1]);
	const profits = times.map(time => time[2]);

	for (let fixedIdx = 0; fixedIdx < times.length; fixedIdx++) {
		for (let variableIdx = 0; variableIdx < fixedIdx; variableIdx++) {
			const [start, , profit] = times[fixedIdx];
			const [, varEnd] = times[variableIdx];

			const isConflicting = varEnd > start;
			if (isConflicting) {
				profits[fixedIdx] = Math.max(profits[fixedIdx], profits[variableIdx]);
				continue;
			}
			profits[fixedIdx] = Math.max(
				profits[fixedIdx],
				profits[variableIdx] + profit
			);
		}
	}

	return profits[profits.length - 1];
}

console.log(
	jobScheduling([1, 2, 3, 4, 6], [3, 5, 10, 6, 9], [20, 20, 100, 70, 60])
);

// 1. Prices, on each day, are given in an array
export function maxProfitWithKTransactions(
	prices: number[],
	noOfTransactions: number
): number {
	// if there is no price, our profit will be zero
	if (prices.length === 0) return 0;
	const profits: number[][] = [];
	for (let idx = 0; idx < noOfTransactions + 1; idx++) {
		profits.push(new Array(prices.length).fill(0));
	}

	console.table(profits);

	for (let transaction = 1; transaction < noOfTransactions + 1; transaction++) {
		let maxProfitSoFar = -Infinity;
		for (let day = 1; day < prices.length; day++) {
			const profitOnPrevDayPrevTransaction = profits[transaction - 1][day - 1];
			const priceOnPrevDay = prices[day - 1];
			const priceOnCurrDay = prices[day];
			const netProfitOnPrevDayPrevTransaction =
				profitOnPrevDayPrevTransaction - priceOnPrevDay;

			maxProfitSoFar = Math.max(
				maxProfitSoFar,
				netProfitOnPrevDayPrevTransaction
			);

			const profitOnPrevDay = profits[transaction][day - 1];
			profits[transaction][day] = Math.max(
				profitOnPrevDay,
				maxProfitSoFar + priceOnCurrDay
			);
		}
	}

	console.table(profits);

	return profits[noOfTransactions][prices.length - 1];
}

maxProfitWithKTransactions([5, 11, 3, 50, 60, 90], 2);

┌─────────┬───┬────┬───┬────┬────┬────┐
│ (trans) │ 5 │ 11 │ 3 │ 50 │ 60 │ 90 │
├─────────┼───┼────┼───┼────┼────┼────┤
│ 0       │ 0 │ 0  │ 0 │ 0  │ 0  │ 0  │ < first row is zero because there is no profit on transaction one yet (you need to buy first)
│ 1       │ 0 │ 0  │ 0 │ 0  │ 0  │ 0  │
│ 2       │ 0 │ 0  │ 0 │ 0  │ 0  │ 0  │
└─────────┴───┴────┴───┴────┴────┴────┘
            ^ first column is zero because there is no profit on day one

┌─────────┬───┬───┬───┬────┬────┬────┐
│ 0       │ 0 │ 0 │ 0 │ 0  │ 0  │ 0  │
│ 1       │ 0 │ 6 │ 6 │ 47 │ 57 │ 87 │
│ 2       │ 0 │ 6 │ 6 │ 53 │ 63 │ 93 │
└─────────┴───┴───┴───┴────┴────┴────┘

value = 6 based on the following formula,

maxSoFar = Math.max(-Infinity, 0 - 5) = -5
curr = Math.max(0, -5 + 11) = 6

export const zeroSumSubarray = (nums: number[]) => {
	if (nums.length === 0) return false;

	const sums: { [T: number]: undefined | true } = {};

	let currentSum = 0;

	for (let index = 0; index < nums.length; index++) {
		const element = nums[index];
		currentSum += element;
		if (sums[currentSum]) {
			return true;
		}
		sums[currentSum] = true;
	}

	return currentSum === 0;
};

export const zeroSumSubarray = (nums: number[]) => {
	if (nums.length === 0) return false;

	const sums: { [T: number]: undefined | number } = {};

	let currentSum = 0;

	for (let index = 0; index < nums.length; index++) {
		console.log(sums);
		const element = nums[index];
		currentSum += element;
		if (typeof sums[currentSum] === 'number') {
			return [sums[currentSum] + 1, index];
		}
		sums[currentSum] = index;
	}

	return [0, nums.length - 1];
};

console.log(zeroSumSubarray([-5, -5, 2, 3, -2]));
// returns [1, 3]

flowchart TD
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px,color:#000000;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px,color:#000000;
    classDef blue fill:#ccccff,stroke:#000,stroke-width:2px,color:#000000;
    classDef orange fill:#ffcc99,stroke:#000,stroke-width:2px,color:#000000;
    classDef yellow fill:#ffff99,stroke:#000,stroke-width:2px,color:#000000;

    0[0] --> 1[1]:::blue
    0[0] --> 2[2]
    1 --> 12[2]:::blue
    1 --> 13[3]
    12 --> 123[3]:::blue
    12 --> 124[4]
    123 --> 1234[4]:::blue --> 12345[5]:::green
    1234 --> 12346[6]:::red
    123 --> 1235[5]:::green
    124 --> 1245[5]:::green
    124 --> 1246[6]:::red
    13 --> 135[5]:::green
    13 --> 136[6]:::red
    2 --> 23[3]
    2 --> 24[4]
    23 --> 234[4]
    23 --> 235[5]:::green
    234 --> 2345[5]:::green
    234 --> 2346[6]:::red
    24 --> 245[5]:::green
    24 --> 246[6]:::red

// O(2^N) time and O(N) space
function climbStairs(
	steps: number,
	stepsTakenSoFar = 0,
	noOfPaths = 0
): number {
	if (stepsTakenSoFar === steps) {
		return noOfPaths + 1;
	}
	if (stepsTakenSoFar > steps) {
		return noOfPaths;
	}
	return (
		climbStairs(steps, stepsTakenSoFar + 1, noOfPaths) +
		climbStairs(steps, stepsTakenSoFar + 2, noOfPaths)
	);
}

// O(N) time and O(N) space
interface Memo {
	[key: number]: number;
}

const countNoOfPaths = (
	steps: number,
	stepsTakenSoFar = 0,
	noOfPaths = 0,
	memo: Memo = {}
): number => {
	if (stepsTakenSoFar === steps) {
		return noOfPaths + 1;
	}
	if (stepsTakenSoFar > steps) {
		return noOfPaths;
	}
	const alreadyComputedPath = memo[stepsTakenSoFar];
	if (typeof alreadyComputedPath === 'number') {
		return alreadyComputedPath;
	}
	const noOfStepPaths =
		countNoOfPaths(steps, stepsTakenSoFar + 1, noOfPaths, memo) +
		countNoOfPaths(steps, stepsTakenSoFar + 2, noOfPaths, memo);
	memo[stepsTakenSoFar] = noOfStepPaths;
	return noOfStepPaths;
};

function climbStairs(steps: number): number {
	const memo: Memo = {};
	const paths = countNoOfPaths(steps, 0, 0, memo);
	return paths;
}

// O(N) time and O(N) space
function climbStairs(steps: number): number {
	const seq = new Array(steps + 1).fill(0);
	for (let idx = seq.length - 1; idx >= 0; idx--) {
		if (idx === seq.length - 1 || idx === seq.length - 2) {
			seq[idx] = 1;
			continue;
		}
		const [one, two] = [seq[idx + 1], seq[idx + 2]];
		seq[idx] = one + two;
	}
	console.log(seq);
	return seq[0];
}

// O(N) time and O(1) space
function climbStairs(steps: number): number {
	let one = 1;
	let two = 1;
	for (let idx = steps; idx >= 0; idx--) {
		if (idx === steps || idx === steps - 1) {
			continue;
		}
		const oldOne = one;
		one = one + two;
		two = oldOne;
		console.log({ idx, one, two });
	}
	return one;
}

// O(n) time | O(n) space
export function staircaseTraversal(
	height: number,
	maxSteps: number,
	stepsTakenSoFar = 0,
	noOfPaths = 0,
	memo: Record<string, number> = {}
): number {
	if (stepsTakenSoFar === height) {
		return noOfPaths + 1;
	}
	if (stepsTakenSoFar > height) {
		return noOfPaths;
	}
	let totalPaths = 0;
	for (let idx = 0; idx < maxSteps; idx++) {
		const branch = stepsTakenSoFar + idx + 1;
		if (typeof memo[branch] === 'number') {
			totalPaths += memo[branch];
			continue;
		}
		const totalPathsForBranch = staircaseTraversal(
			height,
			maxSteps,
			branch,
			noOfPaths,
			memo
		);
		memo[branch] = totalPathsForBranch;
		totalPaths += totalPathsForBranch;
	}
	return totalPaths;
}

[1, 2, 4, 8, 7, 9]

flowchart TD
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px,color:#000000;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px,color:#000000;
    classDef blue fill:#ccccff,stroke:#000,stroke-width:2px,color:#000000;
    classDef orange fill:#ffcc99,stroke:#000,stroke-width:2px,color:#000000;
    classDef yellow fill:#ffff99,stroke:#000,stroke-width:2px,color:#000000;

    0[0] --> 1[1]:::blue
    0[0] --> 2[2]
    1 --> 14[4]:::blue
    1 --> 18[8]:::blue
    1 --> 17[7]:::green
    1 --> 19[9]:::green

    14 --> 147[7]:::blue
    14 --> 149[9]:::blue

    2 --> 28[8]:::green
    2 --> 27[7]:::green
    2 --> 29[9]:::green

    28 --> 289[9]:::green

    0 --> 4[4]:::blue
    4 --> 47[7]:::blue
    4 --> 49[9]:::green

    0 --> 08[8]:::green
    08 --> 089[9]:::green

    0 --> 07[7]:::green

    0 --> 09[9]:::green

interface Memo {
	[key: number]: number;
}

// 1, 2, 3, 8 ...
// 1 + rob(3...) or rob(2...)

// O(N)T | O(N)S
function rob(houses: number[], houseIdx = 0, memo: Memo = {}): number {
	if (houseIdx >= houses.length) {
		return 0;
	}
	if (houseIdx in memo) return memo[houseIdx];
	const robbingCurrentHouse =
		houses[houseIdx] + rob(houses, houseIdx + 2, memo);
	const skippingCurrentHouse = rob(houses, houseIdx + 1, memo);
	memo[houseIdx] = Math.max(skippingCurrentHouse, robbingCurrentHouse);
	return memo[houseIdx];
}

//          1, 2, 3, 1   <--- houses
//   pp, p, 1            <--- sequence
//          Math.max(p, pp + 1)
//          1, 2, 4, 4

// O(N)T | O(N)S
function rob(houses: number[]) {
	const memo: number[] = new Array(houses.length).fill(0);
	for (let house = 0; house < houses.length; house++) {
		const houseVal = houses[house];
		const prevHouseVal = memo[house - 1] ?? 0;
		const prevToPrevHouseVal = memo[house - 2] ?? 0;
		memo[house] = Math.max(prevHouseVal, prevToPrevHouseVal + houseVal);
	}
	return memo[houses.length - 1];
}

console.log(rob([1, 2, 3, 1])); // 4
console.log(rob([2, 7, 9, 3, 1])); // 12

// O(N)T | O(1)S
function rob(houses: number[]) {
	let prevHouseVal = 0;
	let prevToPrevHouseVal = 0;
	for (let house = 0; house < houses.length; house++) {
		const houseVal = houses[house];
		const maxHouse = Math.max(prevHouseVal, prevToPrevHouseVal + houseVal);
		prevToPrevHouseVal = prevHouseVal;
		prevHouseVal = maxHouse;
	}
	return prevHouseVal;
}

console.log(rob([1, 2, 3, 1])); // 4
console.log(rob([2, 7, 9, 3, 1])); // 12

interface Block {
	[key: string]: boolean;
}

export function apartmentHunting(blocks: Block[], reqs: string[]) {
	const proximities = new Array(blocks.length)
		.fill([])
		.map(() => new Array(reqs.length).fill(Infinity));

	for (let reqIdx = 0; reqIdx < reqs.length; reqIdx++) {
		const req = reqs[reqIdx];

		let closest = Infinity;
		for (let blockIdx = 0; blockIdx < blocks.length; blockIdx++) {
			const block = blocks[blockIdx];
			if (block[req]) {
				closest = blockIdx;
				proximities[blockIdx][reqIdx] = 0;
				continue;
			}
			proximities[blockIdx][reqIdx] = Math.min(
				proximities[blockIdx][reqIdx],
				Math.abs(blockIdx - closest)
			);
		}

		closest = Infinity;
		for (let blockIdx = blocks.length - 1; blockIdx >= 0; blockIdx--) {
			const block = blocks[blockIdx];
			if (block[req]) {
				closest = blockIdx;
				continue;
			}
			proximities[blockIdx][reqIdx] = Math.min(
				proximities[blockIdx][reqIdx],
				Math.abs(blockIdx - closest)
			);
		}
	}

	let maxProximityBlockIdx = 0;
	let maxProximity = Infinity;
	for (let procIdx = 0; procIdx < proximities.length; procIdx++) {
		const proximity = proximities[procIdx];
		const maxProc = Math.max(...proximity);
		if (maxProc < maxProximity) {
			maxProximity = maxProc;
			maxProximityBlockIdx = procIdx;
		}
	}
	return maxProximityBlockIdx;
}

console.log(
	apartmentHunting(
		[
			{
				gym: false,
				school: true,
				store: false,
			},
			{
				gym: true,
				school: false,
				store: false,
			},
			{
				gym: true,
				school: true,
				store: false,
			},
			{
				gym: false,
				school: true,
				store: false,
			},
			{
				gym: false,
				school: true,
				store: true,
			},
		],
		['gym', 'school', 'store']
	)
);

gym:    1, 0, 0, 1, 2
school: 0, 1, 0, 0, 0
store:  4, 3, 2, 1, 0

loop over block

closest gym is Infinity
- if gym is present, set proximity to 0
    - closest gym is blockIdx             Infinity
- if gym not preset, set proximity to min(proximity at block, abs(blockIdx - closest))

do this forwards and backwards

// ON ST
interface Memo {
	[key: number]: number;
}

const climbStairs = (
	cost: number[],
	currIdx = 0,
	pathCost = 0,
	memo: Memo = {}
): number => {
	if (currIdx >= cost.length) {
		return pathCost;
	}

	if (currIdx in memo) {
		return memo[currIdx];
	}

	const leftMax = climbStairs(cost, currIdx + 1, cost[currIdx + 1] ?? 0, memo);
	const rightMax = climbStairs(cost, currIdx + 2, cost[currIdx + 2] ?? 0, memo);

	if (leftMax > rightMax) {
		memo[currIdx] = rightMax + pathCost;
		return memo[currIdx];
	}

	memo[currIdx] = leftMax + pathCost;
	return memo[currIdx];
};

function minCostClimbingStairs(cost: number[]): number {
	const memo: Memo = {};
	const value = climbStairs(cost, 0, cost[0], memo);
	return Math.min(value, memo[1] ?? Infinity);
}

flowchart TD
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px,color:#000000;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px,color:#000000;
    classDef blue fill:#ccccff,stroke:#000,stroke-width:2px,color:#000000;
    classDef orange fill:#ffcc99,stroke:#000,stroke-width:2px,color:#000000;
    classDef yellow fill:#ffff99,stroke:#000,stroke-width:2px,color:#000000;

    0[0, 10] --> 1[1, 15]:::green
    1 --> 12[2, 20]:::green
    1 --> 13[3, 0]:::green

    0 --> 2[2, 20]:::blue
    2 --> 23[3, 0]:::blue

// O(N) S
function minCostClimbingStairs(cost: number[]): number {
	for (let idx = cost.length - 1; idx >= 0; idx--) {
		const curr = cost[idx] ?? 0;
		const next = cost[idx + 1] ?? 0;
		const nextToNext = cost[idx + 2] ?? 0;

		const singleJumpSum = curr + next;
		const doubleJumpSum = curr + nextToNext;

		if (singleJumpSum > doubleJumpSum) {
			cost[idx] = doubleJumpSum;
			continue;
		}

		cost[idx] = singleJumpSum;
	}
	return Math.min(cost[0], cost[1]);
}

console.log(minCostClimbingStairs([10, 15, 20]));
// 10, 15, 20
//         20 + 0
//         20 + - + 0
// 10, 15,  20
//     15 + 20
//     15 + -  + 0
// 10,  15,  20
// 10 + 15
// 10 + -  + 20
//
// 25,  15,  20

function longestPalindrome(str: string) {
	let longestLeft = 0;
	let longestRight = 0;
	let length = longestRight - longestLeft;

	for (let idx = 0; idx < str.length; idx++) {
		let left = idx;
		let right = idx;

		while (left >= 0 && right < str.length) {
			if (str[left] === str[right]) {
				const currentLength = right - left;
				if (currentLength > length) {
					longestLeft = left;
					longestRight = right;
					length = currentLength;
				}
				left--;
				right++;
				continue;
			}
			break;
		}

		left = idx;
		right = idx + 1;

		while (left >= 0 && right < str.length) {
			if (str[left] === str[right]) {
				const currentLength = right - left;
				if (currentLength > length) {
					longestLeft = left;
					longestRight = right;
					length = currentLength;
				}
				left--;
				right++;
				continue;
			}
			break;
		}
	}

	return str.substring(longestLeft, longestRight + 1);
}

console.log(longestPalindrome('abaxyzzyxf'));

function countSubstrings(str: string) {
	let count = 0;

	for (let idx = 0; idx < str.length; idx++) {
		let left = idx;
		let right = idx;

		while (left >= 0 && right < str.length) {
			if (str[left] === str[right]) {
				count += 1;
				left--;
				right++;
				continue;
			}
			break;
		}

		left = idx;
		right = idx + 1;

		while (left >= 0 && right < str.length) {
			if (str[left] === str[right]) {
				count += 1;
				left--;
				right++;
				continue;
			}
			break;
		}
	}

	return count;
}

console.log(countSubstrings('aaa'));

flowchart TD
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px,color:#000000;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px,color:#000000;
    classDef blue fill:#ccccff,stroke:#000,stroke-width:2px,color:#000000;
    classDef orange fill:#ffcc99,stroke:#000,stroke-width:2px,color:#000000;

    Start["Start_Index_-1"]:::blue
    Start --> A["1_valid_A_Index_0"]:::green
    Start --> B["11_valid_K_Index_1"]:::green

    A --> A1["1_valid_A_Index_1"]:::green
    A --> A2["11_valid_J_Index_2"]:::green

    B --> B1["1_valid_A_Index_2"]:::green
    B --> B2["10_valid_J_Index_3"]:::green

    A1 --> A11["1_valid_A_Index_2"]:::green
    A1 --> A12["10_valid_J_Index_3"]:::green

    A11 --> A111["0_invalid_Index_3"]:::red
    A11 --> A112["06_invalid_Index_4"]:::red

    A12 --> A121["6_valid_F_Index_4"]:::green

    A2 --> A21["0_invalid_Index_3"]:::red
    A2 --> A22["06_invalid_Index_4"]:::red

    B1 --> B11["0_invalid_Index_3"]:::red
    B1 --> B12["06_invalid_Index_4"]:::red

    B2 --> B22["6_valid_Index_4"]:::green

const getAlphaMap = (): Map<string, string> => {
	const alphaMap = new Map<string, string>();
	alphaMap.set('1', 'A');
	alphaMap.set('2', 'B');
	alphaMap.set('3', 'C');
	alphaMap.set('4', 'D');
	alphaMap.set('5', 'E');
	alphaMap.set('6', 'F');
	alphaMap.set('7', 'G');
	alphaMap.set('8', 'H');
	alphaMap.set('9', 'I');
	alphaMap.set('10', 'J');
	alphaMap.set('11', 'K');
	alphaMap.set('12', 'L');
	alphaMap.set('13', 'M');
	alphaMap.set('14', 'N');
	alphaMap.set('15', 'O');
	alphaMap.set('16', 'P');
	alphaMap.set('17', 'Q');
	alphaMap.set('18', 'R');
	alphaMap.set('19', 'S');
	alphaMap.set('20', 'T');
	alphaMap.set('21', 'U');
	alphaMap.set('22', 'V');
	alphaMap.set('23', 'W');
	alphaMap.set('24', 'X');
	alphaMap.set('25', 'Y');
	alphaMap.set('26', 'Z');

	return alphaMap;
};

function numDecodings(
	encodedString: string,
	alphMap = getAlphaMap(),
	memo = new Map<number, number>(),
	isLeft = true,
	currIdx = -1,
	noOfPaths = 0
): number {
	let encodedSubString = '';

	if (currIdx === -1) {
		encodedSubString = '';
	} else if (isLeft) {
		encodedSubString = `${encodedString[currIdx] ?? ''}`;
	} else {
		encodedSubString = `${encodedString[currIdx - 1] ?? ''}${encodedString[currIdx] ?? ''}`;
	}

	const isEncodedSubStringValid = alphMap.has(encodedSubString);

	if (currIdx !== -1 && !isEncodedSubStringValid) {
		return noOfPaths;
	}

	if (currIdx === encodedString.length - 1) {
		if (isEncodedSubStringValid) return noOfPaths + 1;
		return noOfPaths;
	}

	if (memo.has(currIdx)) {
		return (memo.get(currIdx) ?? 0) + noOfPaths;
	}

	const leftNoOfPaths = numDecodings(
		encodedString,
		alphMap,
		memo,
		true,
		currIdx + 1,
		noOfPaths
	);

	const righNoOfPaths = numDecodings(
		encodedString,
		alphMap,
		memo,
		false,
		currIdx + 2,
		noOfPaths
	);

	const totalNoOfPaths = leftNoOfPaths + righNoOfPaths;

	memo.set(currIdx, totalNoOfPaths);

	return totalNoOfPaths + noOfPaths;
}

console.log(numDecodings('11106'));

   11106
   1 or 11 (if I go with 11, increase sequence + 2)

    0 1 2 3 4
    1 1 1 0 6
    0 0 0 0 0
    1 0 0 0 0  ( stand alone 1 is valid )
    1 2 0 0 0  ( stand alone 1 and prev with previous value 11 is valid )
    1 2 3 0 0  ( stand alone 1 + prev and prev with previous value 11 is valid )
    1 2 3 2 0  ( stand alone 0 is not valid, 3 cannot be added to curr, 2 can be added to curr )
    1 2 3 2 2  ( stand alone 6 is valid, 2 can be added to curr, 06 is not valid )

    S 1 1 1 0 6
  0 1 0 0 0 0 0

  0 1 1 0 0 0 0 ( 1 is valid, 0+1 )
  0 1 1 0 0 0 0 ( "" + 1 is valid, 0+1 )
  0 1 1 2 0 0 0 ( 1 is valid, 11 is valid )
  0 1 1 2 3 0 0 ( 1 is valid (0 + 2), 11 is valid (2 + 1) )
  0 1 1 2 3 2 0 ( 0 is not valid, 10 is valid (2 + 0))
  0 1 1 2 3 2 2 ( 6 is valid, 2 is valid )

const getAlphaMap = (): Map<string, string> => {
	const alphaMap = new Map<string, string>();
	alphaMap.set('1', 'A');
	alphaMap.set('2', 'B');
	alphaMap.set('3', 'C');
	alphaMap.set('4', 'D');
	alphaMap.set('5', 'E');
	alphaMap.set('6', 'F');
	alphaMap.set('7', 'G');
	alphaMap.set('8', 'H');
	alphaMap.set('9', 'I');
	alphaMap.set('10', 'J');
	alphaMap.set('11', 'K');
	alphaMap.set('12', 'L');
	alphaMap.set('13', 'M');
	alphaMap.set('14', 'N');
	alphaMap.set('15', 'O');
	alphaMap.set('16', 'P');
	alphaMap.set('17', 'Q');
	alphaMap.set('18', 'R');
	alphaMap.set('19', 'S');
	alphaMap.set('20', 'T');
	alphaMap.set('21', 'U');
	alphaMap.set('22', 'V');
	alphaMap.set('23', 'W');
	alphaMap.set('24', 'X');
	alphaMap.set('25', 'Y');
	alphaMap.set('26', 'Z');

	return alphaMap;
};

function numDecodings(encodedString: string): number {
	const alphaMap = getAlphaMap();

	let prevWays = 1;
	let prevToPrevWays = 0;
	for (let idx = 0; idx < encodedString.length; idx++) {
		const encodedChar = encodedString[idx];
		const prevEncodedChar = encodedString[idx - 1] ?? '';

		let currWays = 0;
		if (alphaMap.has(encodedChar)) {
			currWays += prevWays;
			console.log('alphaMap.has(encodedChar)', currWays);
		}
		if (alphaMap.has(`${prevEncodedChar}${encodedChar}`)) {
			currWays += prevToPrevWays;
			console.log('alphaMap.has(`${encodedChar}${prevEncodedChar}`)', currWays);
		}

		console.log({
			idx,
			encodedChar,
			prevEncodedChar,
			currWays,
			prevWays,
			prevToPrevWays,
		});

		prevToPrevWays = prevWays;
		prevWays = currWays;
	}

	return prevWays;
}

console.log(numDecodings('11106'));

const traverseDown = (
	remainingAmount: number,
	coins: number[],
	memo: Map<number, number>
): number => {
	const memoisedValue = memo.get(remainingAmount);
	if (memoisedValue !== undefined) {
		return memoisedValue;
	}
	if (remainingAmount < 0) {
		return -1; // not a valid path
	}
	if (remainingAmount === 0) {
		return 0; // a valid path
	}
	let minNoOfCoins = Infinity;
	for (let coin of coins) {
		const remainingNoOfCoins = Math.min(
			traverseDown(remainingAmount - coin, coins, memo),
			minNoOfCoins
		);
		if (remainingNoOfCoins <= -1) continue;
		// +1 for the current coin
		minNoOfCoins = Math.min(minNoOfCoins, remainingNoOfCoins + 1);
	}
	const noOfCoins = minNoOfCoins === Infinity ? -1 : minNoOfCoins;
	memo.set(remainingAmount, noOfCoins);
	// return -1 here also if no valid paths
	return noOfCoins;
};

function coinChange(coins: number[], amount: number): number {
	const memo = new Map<number, number>();
	return traverseDown(amount, coins, memo);
}

console.log(coinChange([1, 3, 4, 5], 7)); // 2

flowchart LR
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px,color:#000000;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px,color:#000000;
    classDef blue fill:#ccccff,stroke:#000,stroke-width:2px,color:#000000;
    classDef orange fill:#ffcc99,stroke:#000,stroke-width:2px,color:#000000;
    classDef yellow fill:#ffff99,stroke:#000,stroke-width:2px,color:#000000;

    root[7]:::green
    root --> 7_1[6 - 1]
    root --> 7_3[4 - 3]
    root --> 7_4[3 - 4]
    root --> 7_5[2 - 5]

    7_1 --> 7_1_1[5 - 1]
    7_1 --> 7_1_3[3 - 3]
    7_1 --> 7_1_4[2 - 4]
    7_1 --> 7_1_5[1 - 5]

    7_3 --> 7_3_1[3 - 1]
    7_3 --> 7_3_3[1 - 3]
    7_3 --> 7_3_4[0 - 4]:::blue
    7_3 --> 7_3_5[-1 - 5]:::red

    7_4 --> 7_4_1[2 - 1]
    7_4 --> 7_4_3[0 - 3]:::blue
    7_4 --> 7_4_4[-1 - 4]:::red
    7_4 --> 7_4_5[-2 - 5]:::red

    7_5 --> 7_5_1[1 - 1]
    7_5 --> 7_5_3[-1 - 3]:::red
    7_5 --> 7_5_4[-2 - 4]:::red
    7_5 --> 7_5_5[-3 - 5]:::red

    7_1_1 --> 7_1_1_1[4 - 1]
    7_1_1 --> 7_1_1_3[2 - 3]
    7_1_1 --> 7_1_1_4[1 - 4]
    7_1_1 --> 7_1_1_5[0 - 5]:::blue

    7_1_3 --> 7_1_3_1[2 - 1]
    7_1_3 --> 7_1_3_3[0 - 3]:::blue
    7_1_3 --> 7_1_3_4[-1 - 4]:::red
    7_1_3 --> 7_1_3_5[-2 - 5]:::red

    7_1_4 --> 7_1_4_1[1 - 1]
    7_1_4 --> 7_1_4_3[-1 - 3]:::red
    7_1_4 --> 7_1_4_4[-2 - 4]:::red
    7_1_4 --> 7_1_4_5[-3 - 5]:::red

    7_1_5 --> 7_1_5_1[0 - 1]:::blue
    7_1_5 --> 7_1_5_3[-2 - 3]:::red
    7_1_5 --> 7_1_5_4[-3 - 4]:::red
    7_1_5 --> 7_1_5_5[-4 - 5]:::red

    7_3_1 --> 7_3_1_1[2 - 1]
    7_3_1 --> 7_3_1_3[0 - 3]:::blue
    7_3_1 --> 7_3_1_4[-1 - 4]:::red
    7_3_1 --> 7_3_1_5[-2 - 5]:::red

    7_3_3 --> 7_3_3_1[0 - 1]:::blue
    7_3_3 --> 7_3_3_3[-2 - 3]:::red
    7_3_3 --> 7_3_3_4[-3 - 4]:::red
    7_3_3 --> 7_3_3_5[-4 - 5]:::red

    7_4_1 --> 7_4_1_1[1 - 1]
    7_4_1 --> 7_4_1_3[-1 - 3]:::red
    7_4_1 --> 7_4_1_4[-2 - 4]:::red
    7_4_1 --> 7_4_1_5[-3 - 5]:::red

    7_5_1 --> 7_5_1_1[0 - 1]:::blue
    7_5_1 --> 7_5_1_3[-2 - 3]:::red
    7_5_1 --> 7_5_1_4[-3 - 4]:::red
    7_5_1 --> 7_5_1_5[-4 - 5]:::red

Time Complexity: no_of_coins ^ depth_of_decision_tree, no_of_coins * amount (max depth possible)
Space Complexity: no_of_coins ( see level 1, we create n recusive stacks )

With memoisation
Time Complexity: no_of_coins * amount
Space Complexity: no_of_coins

function coinChange(coins: number[], amount: number): number {
	const dp: number[] = new Array(amount + 1).fill(Infinity);
	dp[0] = 0; // there is exactly one way to make 0 amount, that is by not selecting any coin
	for (let denom = 1; denom < dp.length; denom++) {
		for (let coin of coins) {
			// we cannot make the demonination with the coin whose value is greater than the demonination
			// assuming may not be sorted
			if (coin > denom) continue;
			// keep current coins to make denom or
			// coins to make prev denom + 1
			dp[denom] = Math.min(dp[denom], dp[denom - coin] + 1);
		}
	}
	const lastValue = dp[dp.length - 1];
	return lastValue === Infinity ? -1 : lastValue;
}

// console.log(coinChange([1, 2, 5], 11)); // 3
console.log(coinChange([1, 2], 3)); // 3

┌─────────┬───┬──────────┬──────────┬──────────┬────────┐
│ (index) │ 0 │ 1        │ 2        │ 3        │ Values │
├─────────┼───┼──────────┼──────────┼──────────┼────────┤
│ denom   │   │          │          │          │ 1      │
│ coin    │   │          │          │          │ 1      │
│ dp      │ 0 │ Infinity │ Infinity │ Infinity │        │ < Math.min(Infinity, 0(prev denom) + 1)
└─────────┴───┴──────────┴──────────┴──────────┴────────┘
┌─────────┬───┬───┬──────────┬──────────┬────────┐
│ (index) │ 0 │ 1 │ 2        │ 3        │ Values │
├─────────┼───┼───┼──────────┼──────────┼────────┤
│ denom   │   │   │          │          │ 1      │
│ coin    │   │   │          │          │ 2      │
│ dp      │ 0 │ 1 │ Infinity │ Infinity │        │
└─────────┴───┴───┴──────────┴──────────┴────────┘
┌─────────┬───┬───┬──────────┬──────────┬────────┐
│ (index) │ 0 │ 1 │ 2        │ 3        │ Values │
├─────────┼───┼───┼──────────┼──────────┼────────┤
│ denom   │   │   │          │          │ 2      │
│ coin    │   │   │          │          │ 1      │
│ dp      │ 0 │ 1 │ Infinity │ Infinity │        │
└─────────┴───┴───┴──────────┴──────────┴────────┘
┌─────────┬───┬───┬───┬──────────┬────────┐
│ (index) │ 0 │ 1 │ 2 │ 3        │ Values │
├─────────┼───┼───┼───┼──────────┼────────┤
│ denom   │   │   │   │          │ 2      │
│ coin    │   │   │   │          │ 2      │
│ dp      │ 0 │ 1 │ 2 │ Infinity │        │
└─────────┴───┴───┴───┴──────────┴────────┘
┌─────────┬───┬───┬───┬──────────┬────────┐
│ (index) │ 0 │ 1 │ 2 │ 3        │ Values │
├─────────┼───┼───┼───┼──────────┼────────┤
│ denom   │   │   │   │          │ 3      │
│ coin    │   │   │   │          │ 1      │
│ dp      │ 0 │ 1 │ 1 │ Infinity │        │
└─────────┴───┴───┴───┴──────────┴────────┘
┌─────────┬───┬───┬───┬───┬────────┐
│ (index) │ 0 │ 1 │ 2 │ 3 │ Values │
├─────────┼───┼───┼───┼───┼────────┤
│ denom   │   │   │   │   │ 3      │
│ coin    │   │   │   │   │ 2      │
│ dp      │ 0 │ 1 │ 1 │ 2 │        │
└─────────┴───┴───┴───┴───┴────────┘
2

type Memo = Map<string, number>;

const recursiveNoOfWays = (
	amount: number,
	coins: number[],
	index: number = 0,
	memo: Memo
): number => {
	console.table({ amount, coins, index });
	if (amount === 0) return 1;
	if (amount < 0) return 0;
	if (index >= coins.length) return 0;

	if (memo.has(`${amount}-${index}`)) {
		return memo.get(`${amount}-${index}`) as number;
	}

	const val =
		recursiveNoOfWays(amount - coins[index], coins, index, memo) +
		recursiveNoOfWays(amount, coins, index + 1, memo);

	memo.set(`${amount}-${index}`, val);

	return val;
};

const change = (amount: number, coins: number[]) => {
	const memo: Memo = new Map();
	return recursiveNoOfWays(amount, coins, 0, memo);
};

console.log(change(5, [1, 2, 5])); // 4

flowchart TD
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px,color:#000000;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px,color:#000000;
    classDef blue fill:#ccccff,stroke:#000,stroke-width:2px,color:#000000;
    classDef orange fill:#ffcc99,stroke:#000,stroke-width:2px,color:#000000;
    classDef yellow fill:#ffff99,stroke:#000,stroke-width:2px,color:#000000;

    root[5 - X]:::blue
    root -->|1| 4_1[4]
    root -->|2| 3_2[3]
    root -->|5| 0_5[0]:::green

    4_1 -->|1| 3_1_1[3]
    3_1_1 -->|1| 3_1_1_1[2]
    3_1_1_1 -->|1| 3_1_1_1_1[1] -->|1| 3_1_1_1_1_1[0]:::green
    3_1_1_1 -->|2| 3_1_1_1_2[0]:::green
    3_1_1 -->|2| 3_1_1_2[1] -->|1| 3_1_1_2_1[0]:::green

    4_1 -->|2| 2_1_2[2]

    2_1_2 -->|1| 2_1_2_1[1] -->|1| 2_1_2_1_1[0]:::green
    2_1_2 -->|2| 2_1_2_2[0]:::green

    3_2 -->|1| 3_2_1[2]
    3_2_1 -->|1| 3_2_1_1[1] --> |1| 3_2_1_1_1[0]:::green
    3_2_1 -->|2| 3_2_1_2[0]:::green
    3_2 -->|2| 3_2_2[1] --> |1| 3_2_2_1[0]:::green

    root:::blue

1,1,1,1,1
1,1,1,2
1,1,2,1 << we need to avoid this duplicate path
1,2,1,1
1,2,2

At each node me make no_of_coins decisions
Max depth can be amount

Time Complexity: no_of_coins ^ amount
Space Complexity: no_of_coins

With memoisation

Time Complexity: no_of_coins * amount
Space Complexity: no_of_coins

// O(no_of_coins * target_amount) time complexity
// O(no_of_coins * target_amount) space complexity
const change = (targetAmount: number, coins: number[]): number => {
	const dp: number[][] = Array.from({ length: coins.length + 1 }, () =>
		Array.from({ length: targetAmount + 1 }, (_, idx) => (idx === 0 ? 1 : 0))
	);
	// O(c)
	for (let coinIdx = 1; coinIdx < coins.length + 1; coinIdx++) {
		const coin = coins[coinIdx - 1];
		// O(t)
		for (let amount = 1; amount < targetAmount + 1; amount++) {
			const noOfWaysWithoutThisCoin = dp[coinIdx - 1][amount];
			const noOfWaysWithThisCoin = dp[coinIdx][amount - coin] ?? 0;
			dp[coinIdx][amount] = noOfWaysWithoutThisCoin + noOfWaysWithThisCoin;
		}
	}
	return dp[dp.length - 1][dp[0].length - 1];
};

console.log(change(5, [1, 2, 5])); // 4

               0, 1, 2, 3, 4, 5   < target amount
1 coin         1, 0, 0, 0, 0, 0
1, 2 coins     1, 0, 0, 0, 0, 0
1, 2, 5 coins  1, 0, 0, 0, 0, 0

first row first column is 1, because there is only one way to make 0 amount, that is by not selecting any coin

               0, 1, 2, 3, 4, 5   < target amount
1 coin         1, 1, 1, 1, 1, 1
1, 2 coins     1, 1, 2, x, 3, 3
1, 2, 5 coins  1, 1, 2, 2, 3, 4

No of ways to make 3 amount with 1, 2, coins =
No of ways to make 3 amount with 1 coin +
No of ways to make 1 amount with 1, 2 coins

dp[1][3] = dp[0][3] + dp[1][3 - 2] = 1 + 1 = 2

               0, 1, 2, 3, 4, 5   < target amount
1 coin         1, 1, 1, 1, 1, 1
1, 2 coins     1, 1, 2, 2, 3, 3
1, 2, 5 coins  1, 1, 2, 2, 3, 4

// O(no_of_coins * target_amount) time complexity
// O(target_amount) space complexity

const change = (targetAmount: number, coins: number[]): number => {
	// you only need to keep track of the previous row
	let dp = Array.from({ length }, (_, idx) => (idx === 0 ? 1 : 0));

	for (const coin of coins) {
		console.log({ coin, dp });
		for (let amount = 1; amount < targetAmount + 1; amount++) {
			dp[amount] += dp[amount - coin] ?? 0;
		}
	}

	return dp[targetAmount];
};

1, 1, 1, 1, 1, 1
1, 1, 2, 2, 3, 3
1, 1, 2, 2, 3, 4

override the same array,
since it has the data of the previous iteration

// Without memoisation
// O(2^n) time complexity where n is the length of the nums array

// With memoisation
// O(n * range of possible sum values) ST complexity
function findTargetSumWays(
	nums: number[],
	target: number,
	numIdx = 0,
	memo = new Map<string, number>()
): number {
	if (numIdx === nums.length) {
		return target === 0 ? 1 : 0;
	}
	if (numIdx > nums.length) {
		return 0;
	}

	const num = nums[numIdx];

	if (memo.has(`${numIdx}-${target}`)) {
		return memo.get(`${numIdx}-${target}`) as number;
	}

	const add = findTargetSumWays(nums, target + num, numIdx + 1);
	const sub = findTargetSumWays(nums, target - num, numIdx + 1);
	const total = add + sub;
	memo.set(`${numIdx}-${target}`, total);

	return total;
}

console.log(findTargetSumWays([1, 1, 1, 1, 1], 3)); // 5

flowchart TD
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px,color:#000000;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px,color:#000000;
    classDef blue fill:#ccccff,stroke:#000,stroke-width:2px,color:#000000;

    3[3]:::blue

    3 --> 3_p[2]
    3 --> 3_n[4]

    %% Level 2
    3_p --> 3_p_p[1]
    3_p --> 3_p_n[3]

    3_n --> 3_n_p[3]
    3_n --> 3_n_n[5]

    %% Level 3
    3_p_p --> 3_p_p_p[0]:::green
    3_p_p --> 3_p_p_n[2]

    3_p_n --> 3_p_n_p[2]
    3_p_n --> 3_p_n_n[4]

    3_n_p --> 3_n_p_p[2]
    3_n_p --> 3_n_p_n[4]

    3_n_n --> 3_n_n_p[4]
    3_n_n --> 3_n_n_n[6]

    %% Level 4
    3_p_p_p --> 3_p_p_p_p[-1]
    3_p_p_p --> 3_p_p_p_n[1]

    3_p_p_n --> 3_p_p_n_p[1]
    3_p_p_n --> 3_p_p_n_n[3]

    3_p_n_p --> 3_p_n_p_p[1]
    3_p_n_p --> 3_p_n_p_n[3]

    3_p_n_n --> 3_p_n_n_p[3]
    3_p_n_n --> 3_p_n_n_n[5]

    3_n_p_p --> 3_n_p_p_p[1]
    3_n_p_p --> 3_n_p_p_n[3]

    3_n_p_n --> 3_n_p_n_p[3]
    3_n_p_n --> 3_n_p_n_n[5]

    3_n_n_p --> 3_n_n_p_p[3]
    3_n_n_p --> 3_n_n_p_n[5]

    3_n_n_n --> 3_n_n_n_p[5]
    3_n_n_n --> 3_n_n_n_n[7]

    %% Level 5
    3_p_p_p_p --> 3_p_p_p_p_p[-2]:::red
    3_p_p_p_p --> 3_p_p_p_p_n[0]:::green

    3_p_p_p_n --> 3_p_p_p_n_p[0]:::green
    3_p_p_p_n --> 3_p_p_p_n_n[2]:::red

    3_p_p_n_p --> 3_p_p_n_p_p[0]:::green
    3_p_p_n_p --> 3_p_p_n_p_n[2]:::red

    3_p_p_n_n --> 3_p_p_n_n_p[2]:::red
    3_p_p_n_n --> 3_p_p_n_n_n[4]:::red

    3_p_n_p_p --> 3_p_n_p_p_p[0]:::green
    3_p_n_p_p --> 3_p_n_p_p_n[2]:::red

    3_p_n_p_n --> 3_p_n_p_n_p[2]:::red
    3_p_n_p_n --> 3_p_n_p_n_n[4]:::red

    3_p_n_n_p --> 3_p_n_n_p_p[2]:::red
    3_p_n_n_p --> 3_p_n_n_p_n[4]:::red

    3_p_n_n_n --> 3_p_n_n_n_p[4]:::red
    3_p_n_n_n --> 3_p_n_n_n_n[6]:::red

    3_n_p_p_p --> 3_n_p_p_p_p[0]:::green
    3_n_p_p_p --> 3_n_p_p_p_n[2]:::red

    3_n_p_p_n --> 3_n_p_p_n_p[2]:::red
    3_n_p_p_n --> 3_n_p_p_n_n[4]:::red

    3_n_p_n_p --> 3_n_p_n_p_p[2]:::red
    3_n_p_n_p --> 3_n_p_n_p_n[4]:::red

    3_n_p_n_n --> 3_n_p_n_n_p[4]:::red
    3_n_p_n_n --> 3_n_p_n_n_n[6]:::red

    3_n_n_p_p --> 3_n_n_p_p_p[2]:::red
    3_n_n_p_p --> 3_n_n_p_p_n[4]:::red

    3_n_n_p_n --> 3_n_n_p_n_p[4]:::red
    3_n_n_p_n --> 3_n_n_p_n_n[6]:::red

    3_n_n_n_p --> 3_n_n_n_p_p[4]:::red
    3_n_n_n_p --> 3_n_n_n_p_n[6]:::red

    3_n_n_n_n --> 3_n_n_n_n_p[6]:::red
    3_n_n_n_n --> 3_n_n_n_n_n[8]:::red

const addValueToMap = (
	map: Map<number, number>,
	key: number,
	value: number
) => {
	if (!map.has(key)) {
		map.set(key, value);
		return;
	}
	map.set(key, map.get(key)! + value);
};

function findTargetSumWays(nums: number[], target: number): number {
	let dp = new Map<number, number>();
	dp.set(0, 1);

	for (const num of nums) {
		const newDp = new Map<number, number>();
		for (const [possition, ways] of dp) {
			if (ways === 0) {
				newDp.set(possition, 2);
				continue;
			}
			addValueToMap(newDp, possition + num, ways);
			addValueToMap(newDp, possition - num, ways);
		}
		// I don't need to do this because
		// 1. even if dp refers to the newDP.
		// 2. newDP is not being used in the next iteration.
		// 3. it gets re-initialized in the next iteration.
		dp = newDp;
	}

	return dp.get(target) ?? 0;
}

// console.log(findTargetSumWays([1, 1, 1, 1, 1], 3)); // 5
// console.log(findTargetSumWays([1, 0], 1)); // 2
console.log(findTargetSumWays([1000], 1000)); // 1

( at each node we make + / - decision )
Time Complexity: 2 ^ (nums (max depth possible) * target_sum)
Space Complexity: no_of_nums ( at each level we make + / - decision )

With memoisation
Time Complexity: 2 * nums * target_sum (sum at each node)

    -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5
0    0,  0,  0,  0,  0, 1, 0, 0, 0, 0, 0

base case, the middle value is 1,
because there is only one way to make 0 amount, that is by not using any coin

1    0,  0,  0,  0,  1, 0,  1, 0, 0, 0, 0
2    0,  0,  0,  1,  0, 2,  0, 1, 0, 0, 0
3    0,  0,  1,  0,  3, 0,  3, 0, 1, 0, 0
4    0,  1,  0,  4,  0, 6,  0, 4, 0, 1, 0
5    1,  0,  5,  0, 10, 0, 10, 0, 5, 0, 1



    -1, 0, 1
0    0, 1, 0
1    1, 0, 1
0    2, 0, 2

processing 0 creates two paths for each existing way.
So double every occurence of non-zero values.


        -1000, 0, 1000
0           0, 1,    0
1000        1, 0,    1

flowchart TD
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px,color:#000000;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px,color:#000000;
    classDef blue fill:#ccccff,stroke:#000,stroke-width:2px,color:#000000;
    classDef orange fill:#ffcc99,stroke:#000,stroke-width:2px,color:#000000;
    classDef yellow fill:#ffff99,stroke:#000,stroke-width:2px,color:#000000;

    10[10]:::blue
    10 -->|1,2| 8 -->|4,3| 5 -->|5,6| -1[-1 no_cap]:::red
    8 --> |5,6| 2 -->|4,3| -1.1[-1 no_cap]:::red
    8 --> |6,7| 1 -->|5,6| -5[-5, no_cap]:::red

    10 ---->|4, 3| 7 --> |1, 2| 5.1[5] -->|5, 6| -1.2[-1 no_cap]:::red
    7 --> |5, 6| 1.1[1] -->|1, 2| -1.3[-1 no_cap]:::red
    7 --> |6, 7| 0:::green

    10 --->|5, 6| 4 -->|1, 2| 3 -->|4, 3| -1.4[-1 no_cap]:::red
    4 --> |4, 3| 1.2[1] -->|1, 2| -1.5[-1 no_cap]:::red
    4 --> |6, 7| -3[-3, no_cap]:::red

    10 ---->|6, 7| 3.1[3] -->|1, 2| 1.4[1] -->|4, 3| -1.6[-1 no_cap]:::red
    3.1 --> |4, 3| 0.1[0]:::green
    3.1 --> |5, 6| -3.2[-3, no_cap]:::red

At each node we need to remember
- the current capacity used
- the path travelled so we dont repeat the same path

We can memoize the following keys
- Current capacity
- Next Item index (sub-tree idx)

type TraversalPathTaken = Map<number, number>;

const recursiveKnapSack = (
	items: [number, number][],
	capacity: number,
	traversalPathTaken: TraversalPathTaken = new Map(),
	maxValue: number = 0,
	memo: Map<string, [number, TraversalPathTaken] | null> = new Map()
): null | [number, TraversalPathTaken] => {
	if (capacity < 0) {
		return null;
	}

	if (capacity === 0) {
		return [maxValue, traversalPathTaken];
	}

	if (traversalPathTaken.size === items.length) {
		return [maxValue, traversalPathTaken];
	}

	let newMaxValue = maxValue;
	let newMaxValuePath: null | TraversalPathTaken = null;

	for (let itemIdx = 0; itemIdx < items.length; itemIdx++) {
		if (traversalPathTaken.has(itemIdx)) continue;

		if (memo.has(`${itemIdx}-${capacity}`)) {
			const memoizedValue = memo.get(`${itemIdx}-${capacity}`);

			if (!memoizedValue) continue;

			const [memoizedVal, memoizedPath] = memoizedValue;
			if (memoizedVal <= newMaxValue) continue;

			newMaxValue = memoizedVal;
			newMaxValuePath = memoizedPath;
		}

		const [value, weight] = items[itemIdx];
		const subTree = recursiveKnapSack(
			items,
			capacity - weight,
			new Map(traversalPathTaken).set(itemIdx, value),
			maxValue + value
		);

		memo.set(`${itemIdx}-${capacity}`, subTree);

		if (!subTree) continue;

		const [subTreeVal, subTreePath] = subTree;
		if (subTreeVal <= newMaxValue) continue;

		newMaxValue = subTreeVal;
		newMaxValuePath = subTreePath;
	}

	if (!newMaxValuePath) return [maxValue, traversalPathTaken];

	return [newMaxValue, newMaxValuePath];
};

export function knapsackProblem(
	items: [number, number][],
	capacity: number
): [number, number[]] {
	const [maxValue, path] = recursiveKnapSack(items, capacity)!;
	return [maxValue, [...path.keys()]];
}

console.log(
	knapsackProblem(
		[
			[1, 2],
			[4, 3],
			[5, 6],
			[6, 7],
		],
		10
	)
); // [10, [1, 3]]

Time Complexity: (no_of_items_in_knapsack - level) ^ capacity
Space Complexity: no_of_items_in_knapsack

Memoisation
Time Complexity: no_of_items_in_knapsack * capacity
Space Complexity: no_of_items_in_knapsack * capacity

┌──────────────┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬────┐
│ (index)      │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ < capacity
├──────────────┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼────┤
│ [v, w]       │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0  │
│ [1, 2]       │ 0 │ 0 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1  │
│ [4, 3]       │ 0 │ 0 │ 1 │ 4 │ 4 │ 5 │ 5 │ 5 │ 5 │ 5 │ 5  │
│ [5, 6]       │ 0 │ 0 │ 1 │ 4 │ 4 │ 5 │ 5 │ 5 │ 6 │ 9 │ 9  │
│ [6, 7]       │ 0 │ 0 │ 1 │ 4 │ 4 │ 5 │ 5 │ 6 │ 6 │ 9 │ 10 │
└──────────────┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴────┘
  ^
  items

Formula,

if weight for item exceeds the capacity so far, then
accept last value

lastValue = dp[itemIdx - 1][capForItem], go up one row
lastValueExcludingCurrentCapacity = dp[itemIdx - 1][capForItem - weight], go up one row and go left by weight
Math.max(lastvalue, value + lastValueExcludingCurrentCapacity)

┌──────────────┬───┬────┬───┬─────┬───┬───┬───┬───┬───┬───┬────┐
│ (index)      │ 0 │ 1  │ 2 │ 3   │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │
├──────────────┼───┼────┼───┼─────┼───┼───┼───┼───┼───┼───┼────┤
│ [v, w]       │ 0 │ 0- │ 0 │ 0   │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0  │
│ [1, 2]       │ 0 │ 0  │ 1 │ 1   │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1  │ 3. last value (4) !== backtracking start (1), that means we took the item (1, 2)
│ [4, 3]       │ 0 │ 0  │ 1 │ 4-  │ 4 │ 5 │ 5 │ 5 │ 5 │ 5 │ 5  │ 1. last value != backtracking start, that means we took the item (6, 7)
│ [5, 6]       │ 0 │ 0  │ 1 │ 4-  │ 4 │ 5 │ 5 │ 5 │ 6 │ 9 │ 9  │ < last value
│ [6, 7]       │ 0 │ 0  │ 1 │ 4   │ 4 │ 5 │ 5 │ 6 │ 6 │ 9 │ 10 │ < backtracking start
└──────────────┴───┴────┴───┴─────┴───┴───┴───┴───┴───┴───┴────┘
                             2. move left by weight (10 - 7 prev weight)
                             < last value
                             < backtracking start
                             last value === backtracking start === 4, that means we did not take the item (5, 6),
                             so move up one row

export function knapsackProblem(
	items: [number, number][],
	capacity: number
): [number, number[]] {
	const dp = Array.from({ length: items.length + 1 }, () =>
		Array.from({ length: capacity + 1 }, () => 0)
	);
	for (let itemIdx = 1; itemIdx < items.length + 1; itemIdx++) {
		const [value, weight] = items[itemIdx - 1];
		for (let capForItem = 1; capForItem <= capacity; capForItem++) {
			const notTakingItem = dp[itemIdx - 1][capForItem];
			if (capForItem < weight) {
				dp[itemIdx][capForItem] = notTakingItem;
				continue;
			}
			const lastValueExculdingCurrentCapacity =
				dp[itemIdx - 1]?.[capForItem - weight] ?? 0;
			const takingItem = value + lastValueExculdingCurrentCapacity;
			dp[itemIdx][capForItem] = Math.max(notTakingItem, takingItem);
		}
	}

	const totalValueInKnapSack = dp[items.length][capacity];
	const knapSackContents: number[] = [];
	for (let itemIdx = items.length, cap = capacity; itemIdx > 0; itemIdx--) {
		if (dp[itemIdx][cap] !== dp[itemIdx - 1][cap]) {
			knapSackContents.push(itemIdx - 1);
			cap -= items[itemIdx - 1][1];
		}
	}
	return [totalValueInKnapSack, knapSackContents.reverse()];
}

console.log(
	knapsackProblem(
		[
			[1, 2],
			[4, 3],
			[5, 6],
			[6, 7],
		],
		10
	)
); // [10, [1, 3]]

type Disk = [number, number, number];
type DiskWithIdx = [Disk, number];
type StackAsMap = Set<number>;

const isPrevDiskSmaller = (prevDisk: Disk, disk: Disk) => {
	const [prevWidth, prevDepth, prevHeight] = prevDisk;
	const [width, depth, height] = disk;
	return prevWidth < width && prevDepth < depth && prevHeight < height;
};

type TraverseDisksReturn = [DiskWithIdx[], StackAsMap, number];

type Memo = Map<string, TraverseDisksReturn | null>;

const createMemoKey = (diskId: number, stackAsMap: StackAsMap) => {
	return `${diskId}-${[...stackAsMap.keys()].join('-')}`;
};

const traverseDisks = (
	disks: Disk[],
	stack: DiskWithIdx[] = [],
	stackAsMap: StackAsMap = new Set(),
	stackHeight = 0,
	memo: Memo = new Map()
): [DiskWithIdx[], StackAsMap, number] => {
	const [prevDisk, prevDiskIdx = 0] = stack[stack.length - 1] ?? [];

	console.log('stack', stack);

	let tallestStack = stack;
	let tallestStackAsMap = stackAsMap;
	let tallestStackHeight = stackHeight;

	for (let diskIdx = prevDiskIdx; diskIdx < disks.length; diskIdx++) {
		if (tallestStackAsMap.has(diskIdx)) continue; // disk has already been stacked

		const disk = disks[diskIdx];

		const memoKey = createMemoKey(diskIdx, stackAsMap);

		if (prevDisk && !isPrevDiskSmaller(prevDisk, disk)) continue; // disk is not stackable <<<<<<<<

		if (memo.has(memoKey)) {
			const memoValue = memo.get(memoKey);
			if (!memoValue) continue;
			[tallestStack, tallestStackAsMap, tallestStackHeight] = memoValue;
		}

		const [stackWithDisk, stackWithDiskAsMap, stackHeightWithDisk] =
			traverseDisks(
				disks,
				[...stack, [disk, diskIdx]],
				new Set(stackAsMap).add(diskIdx),
				stackHeight + disk[2],
				memo
			);

		if (stackHeightWithDisk <= tallestStackHeight) {
			memo.set(memoKey, null);
			continue;
		}

		tallestStack = stackWithDisk;
		tallestStackHeight = stackHeightWithDisk;
		tallestStackAsMap = stackWithDiskAsMap;

		memo.set(memoKey, [tallestStack, tallestStackAsMap, tallestStackHeight]);
	}

	return [tallestStack, tallestStackAsMap, tallestStackHeight];
};

export function diskStacking(disks: Disk[]) {
	disks.sort((a, b) => b[2] - a[2]);
	console.log('disks', disks);
	return traverseDisks(disks)[0].map(([disk]) => disk);
}

console.log(
	diskStacking([
		[2, 1, 2],
		[3, 2, 3],
		[2, 2, 8],
		[2, 3, 4],
		[2, 2, 1],
		[4, 4, 5],
	])
); // [[2, 1, 2], [3, 2, 3], [4, 4, 5]]

flowchart TD
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px,color:#000000;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px,color:#000000;
    classDef blue fill:#ccccff,stroke:#000,stroke-width:2px,color:#000000;
    classDef orange fill:#ffcc99,stroke:#000,stroke-width:2px,color:#000000;
    classDef yellow fill:#ffff99,stroke:#000,stroke-width:2px,color:#000000;

    root[Root]:::blue
    root --> 2_2_1[2, 2, 1]
    root --> 2_1_2[2, 1, 2] --> 3_2_3[3, 2, 3]:::yellow --> 4_4_5[4, 4, 5]:::yellow
    root --> 3_2_3_1[3, 2, 3]:::yellow --> 4_4_5_1[4, 4, 5]:::yellow
    root --> 2_3_4[2, 3, 4]
    root --> 4_4_5_2[4, 4, 5]
    root --> 2_2_8[2, 2, 8]

Time Complexity: no_of_disks^no_of_disks (max depth is no_of_disks)
Space Complexity: no_of_disks

With memoisation
Time Complexity: no_of_disks * no_of_disks = no_of_disks^2
Space Complexity: no_of_disks

type Disk = [number, number, number];

const isPrevDiskSmaller = (prevDisk: Disk, disk: Disk) => {
	const [prevWidth, prevDepth, prevHeight] = prevDisk;
	const [width, depth, height] = disk;
	return prevWidth < width && prevDepth < depth && prevHeight < height;
};

export function diskStacking(disks: Disk[]) {
	// sort the disks by height
	disks.sort((a, b) => a[2] - b[2]);

	const stackHeights = disks.map(disk => disk[2]);
	const sequences = new Array(disks.length).fill(null);

	let maxHeightIdx = 0;

	for (let fixedIdx = 1; fixedIdx < stackHeights.length; fixedIdx++) {
		const fixedDisk = disks[fixedIdx];
		const fixedDiskHeight = fixedDisk[2];

		for (let variableIdx = 0; variableIdx < fixedIdx; variableIdx++) {
			const variableDisk = disks[variableIdx];

			if (!isPrevDiskSmaller(variableDisk, fixedDisk)) continue;

			const stackHeightUpToFixedIdx = stackHeights[fixedIdx];
			const stackHeightUpToVariableIdx = stackHeights[variableIdx];
			const newStackHeightUpToFixedIdx =
				stackHeightUpToVariableIdx + fixedDiskHeight;

			if (newStackHeightUpToFixedIdx <= stackHeightUpToFixedIdx) continue;

			stackHeights[fixedIdx] = newStackHeightUpToFixedIdx;
			sequences[fixedIdx] = variableIdx;
		}

		// NOTE: Potential cause of bug
		// check if maxStackHeight is outdated, only when the fixed variable loop is completed
		const maxStackHeightSoFar = stackHeights[maxHeightIdx];
		const newStackHeightUpToFixedIdx = stackHeights[fixedIdx];
		if (newStackHeightUpToFixedIdx <= maxStackHeightSoFar) continue;

		maxHeightIdx = fixedIdx;
	}

	const stack = [];

	while (maxHeightIdx !== null) {
		const disk = disks[maxHeightIdx];
		stack.unshift(disk);
		maxHeightIdx = sequences[maxHeightIdx];
	}

	return stack;
}

disks = [[2, 1, 2], [3, 2, 3], [2, 2, 8], [2, 3, 4], [2, 2, 1], [4, 4, 5]]

sorted_disks = [[2, 2, 1], [2, 1, 2], [3, 2, 3], [2, 3, 4], [4, 4, 5], [2, 2, 8]]
heights = [1, 2, 3, 4, 5, 8]
sequences = [null, null, null, null, null, null]

1. [2, 2, 1] is stackable on top of [3, 2, 3]

           4, updated height at fixed index
              ( this tells that @idx=2, the max stack height we can build is 4 )
    [1, 2, 3, 4, 5, 8]
           F
     V

                 2 is stackable on top of 0
    [null, null, 0, null, null, null]
     0,    1,    2, 3,    4,    5



           5
    [1, 2, 3, 4, 5, 8]
           F
        V

                 2 is stackable on top of 1
                   ( updated based on new stack height )
    [null, null, 1, null, null, null]
     0,    1,    2, 3,    4,    5

2. [3, 2, 3] is stackable on top of [4, 4, 5]


                 10 (5 + 5)
                 7  (5 + 2)
           5     6  (5 + 1)
    [1, 2, 3, 4, 5, 8]
                 F
     V

    [null, null, 1, null, 2, null]
    [1,    2,    5, 4,   10,    8]
    [0,    1,    2, 3,    4,    5]

type Memo = Map<number, number[]>;
const recursiveLongestIncreasingSubsequence = (
	array: number[],
	index: number = -1,
	traversal: number[] = [],
	memo: Memo = new Map()
): number[] => {
	if (index > array.length - 1) return traversal;

	const elementAtIdx = array[index];

	let maxTraversal = [...traversal];
	let maxTraversalSet = new Set(maxTraversal);
	for (let idx = index + 1; idx < array.length; idx++) {
		const element = array[idx];
		if (index !== -1 && elementAtIdx > element) continue;
		if (
			memo.has(idx) &&
			memo.get(idx)!.length > maxTraversal.length &&
			new Set(memo.get(idx)!).size > maxTraversalSet.size
		) {
			maxTraversal = memo.get(idx)!;
			continue;
		}
		const subTraversal = recursiveLongestIncreasingSubsequence(array, idx, [
			...traversal,
			element,
		]);
		memo.set(idx, subTraversal);
		if (
			subTraversal.length <= maxTraversal.length ||
			new Set(subTraversal).size <= maxTraversalSet.size
		)
			continue;
		maxTraversal = subTraversal;
	}

	return maxTraversal;
};

export function longestIncreasingSubsequence(array: number[]) {
	return recursiveLongestIncreasingSubsequence(array);
}

console.log(
	longestIncreasingSubsequence([5, 7, -24, 12, 10, 2, 3, 12, 5, 6, 35])
);

console.log(longestIncreasingSubsequence([-1, 2, 1, 2]));

flowchart TD
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px,color:#000000;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px,color:#000000;
    classDef blue fill:#ccccff,stroke:#000,stroke-width:2px,color:#000000;
    classDef orange fill:#ffcc99,stroke:#000,stroke-width:2px,color:#000000;
    classDef yellow fill:#ffff99,stroke:#000,stroke-width:2px,color:#000000;

    root[Root]:::blue
    root --> minus1[-1]
    minus1 --> 2[2]:::yellow --> 2.0.1[2]:::yellow
    minus1 --> 1[1]:::yellow --> 2.1[2]:::yellow
    minus1 --> 2.1.1[2]:::yellow

    root --> 2.3[2] --> 2.4[2]
    root --> 1.1[1] --> 2.5[2]
    root --> 2.6[2]

Two distict paths emerge
-1 -> 2 -> 2
-1 -> 1 -> 2 ( this gets preferred because it has more distinct elements )

export function longestIncreasingSubsequence(array: number[]) {
	const sums: number[] = Array(array.length).fill(1);
	const sequences: number[] = Array(array.length).fill(null);

	let maxLengthIdx = 0;
	for (let fixedIdx = 1; fixedIdx < array.length; fixedIdx++) {
		const fixedNum = array[fixedIdx];
		const sumAtFixedIdx = sums[fixedIdx]; // at the beginning of the iteration

		for (let variableIdx = 0; variableIdx < fixedIdx; variableIdx++) {
			const variableNum = array[variableIdx];

			if (variableNum > fixedNum) continue;

			const newPossibleSum = sums[variableIdx] + sumAtFixedIdx;
			const currentSumAtFixedIdx = sums[fixedIdx]; // updated in previous variableIdx iteration

			if (currentSumAtFixedIdx > newPossibleSum) continue;

			sums[fixedIdx] = newPossibleSum;
			sequences[fixedIdx] = variableIdx;
		}
		if (sums[maxLengthIdx] > sums[fixedIdx]) continue;
		maxLengthIdx = fixedIdx;
	}

	const result = [];
	while (maxLengthIdx !== null) {
		result.unshift(array[maxLengthIdx]);
		maxLengthIdx = sequences[maxLengthIdx];
	}

	return result;
}

// console.log(
// 	longestIncreasingSubsequence([5, 7, -24, 12, 10, 2, 3, 12, 5, 6, 35])
// );
//
// console.log(longestIncreasingSubsequence([-1, 2, 1, 2]));
console.log(longestIncreasingSubsequence([1, 5, -1, 10]));

solution similar to disk stacking
┌──────────────┬──────┬───┬──────┬────┬────────┐
│ (index)      │ 0    │ 1 │ 2    │ 3  │ Values │
├──────────────┼──────┼───┼──────┼────┼────────┤
│ array        │ 1    │ 5 │ -1   │ 10 │        │
│              │      │   │      │    │        │
│ sums         │ 1    │ 1 │ 1    │ 1  │        │ < for fixed idx = 1 (5), 5 is greater than 1, so increase its sum
│ sums         │ 1    │ 2 │ 1    │ 3  │        │ < no valid paths for -1
│ sums         │ 1    │ 2 │ 1    │ 3  │        │ < 1 + 1 | 2 + 1 | 1 + 1, taking 3
│              │      │   │      │    │        │       ***notice that the fixed idx at 3 is considered as 1 not the one manipulated in the previous iteration
│ sequences    │ null │ 0 │ null │ 1  │        │
│ maxLengthIdx │      │   │      │    │ null   │
│ result       │ 1    │ 5 │ 10   │    │        │
└──────────────┴──────┴───┴──────┴────┴────────┘
[ 1, 5, 10 ]

flowchart TD
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px,color:#000000;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px,color:#000000;
    classDef blue fill:#ccccff,stroke:#000,stroke-width:2px,color:#000000;
    classDef orange fill:#ffcc99,stroke:#000,stroke-width:2px,color:#000000;
    classDef yellow fill:#ffff99,stroke:#000,stroke-width:2px,color:#000000;

    a_b[A, B]:::blue --> a_c[A,C] --> a_a[A, A]:::orange
    a_b --> b_b[B, B]:::orange --> c_c[C, C]:::orange

    a_c --> b_a[B, A]

abc
bca

Time complexity = 2^(m + n)
                  m = length of first string
                  n = length of second string
                  m + n = max decision tree depth

Space complexity = m * n

with memoistaion
Time complexity = m * n
Space complexity = m * n

from typing import Dict

Memo = Dict[str, int]


class Solution:
    def recursive(
        self,
        firstText: str,
        secondText: str,
        firstTextIdx: int,
        secondTextIdx: int,
        memo: Memo,
    ) -> int:
        if firstTextIdx == len(firstText) or secondTextIdx == len(secondText):
            return 0

        if memo.get(f"{firstTextIdx}_{secondTextIdx}") is not None:
            return memo[f"{firstTextIdx}_{secondTextIdx}"]

        if firstText[firstTextIdx] == secondText[secondTextIdx]:
            next = self.recursive(
                firstText, secondText, firstTextIdx + 1, secondTextIdx + 1, memo
            )
            memo[f"{firstTextIdx}_{secondTextIdx}"] = 1 + next
            return 1 + next

        left = self.recursive(
            firstText, secondText, firstTextIdx + 1, secondTextIdx, memo
        )
        right = self.recursive(
            firstText, secondText, firstTextIdx, secondTextIdx + 1, memo
        )
        value = max(left, right)

        memo[f"{firstTextIdx}_{secondTextIdx}"] = value

        return value

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        return self.recursive(text1, text2, 0, 0, dict())


solution = Solution()
print(solution.longestCommonSubsequence("abcde", "ace"))
print(solution.longestCommonSubsequence("lemon", "lomomn"))

from typing import Dict

Memo = Dict[str, int]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for _ in range(len(text1) + 1)] for _ in range(len(text2) + 1)]
        # O(n * m)
        for rowIdx in range(1, len(dp)):
            for colIdx in range(1, len(dp[0])):
                rowChar = text2[rowIdx - 1]  # since loop starts from 1
                colChar = text1[colIdx - 1]

                if rowChar != colChar:
                    dp[rowIdx][colIdx] = max(
                        dp[rowIdx - 1][colIdx], dp[rowIdx][colIdx - 1]
                    )
                    continue

                dp[rowIdx][colIdx] = dp[rowIdx - 1][colIdx - 1] + 1

        return dp[-1][-1]


solution = Solution()
# print(solution.longestCommonSubsequence("abcde", "ace"))
print(solution.longestCommonSubsequence("lemon", "lomomn"))

If characters match, take the previous LCS value (diagonal left up) and add 1
dp[rowIdx][colIdx] = dp[rowIdx - 1][colIdx - 1] + 1

If characters do not match, take the max of the two previous values
dp[rowIdx][colIdx] = max(dp[rowIdx - 1][colIdx], dp[rowIdx][colIdx - 1])
                         carry forward the previous LCS value with the set up characters upto the previous idx
                         or carry forward the previous LCS value with the set up characters upto the current idx

[ "-", "l", "e", "m", "o", "n" ]
[ "l",  1,   1,   1,   1,   1  ]
[ "o",  1,   1,   1,   2,   2  ]
[ "m",  1,   1,  _2,   2,   2  ]   characters m and ma match so take the diagonal left up value and add 1 (2)
[ "o",  1,   1,   2,   2,   3  ]
[ "m",  1,   1,   2,   2,   3  ]
[ "n",  1,   1,   2,   2,   3  ]

flowchart TD
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px,color:#000000;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px,color:#000000;
    classDef blue fill:#ccccff,stroke:#000,stroke-width:2px,color:#000000;
    classDef orange fill:#ffcc99,stroke:#000,stroke-width:2px,color:#000000;
    classDef yellow fill:#ffff99,stroke:#000,stroke-width:2px,color:#000000;

    root[Root]:::blue

    subgraph "1"
        1_0[-1]:::green
        1_1[0]:::yellow
    end

    root --> | buy | 1_0
    root --> | pass | 1_1

    subgraph "5"
        2_0[4]:::orange
        2_1[-1]:::yellow
    end

    1_0 --> | sell | 2_0
    1_0 --> | pass | 2_1

    subgraph "3"
        2_2[2]:::orange
        2_3[-1]:::yellow
    end

    2_1 --> | sell | 2_2
    2_1 --> | pass | 2_3

    subgraph "6"
        2_4[5]:::orange
        2_5[-1]:::yellow
    end

    2_3 --> | sell | 2_4
    2_3 --> | pass | 2_5

    subgraph "4"
        2_6[3]:::orange
        2_7[-1]:::yellow
    end

    2_5 --> | sell | 2_6
    2_5 --> | pass | 2_7

    subgraph "Overflow"
        2_8[0]:::orange
    end

    2_7 --> | sell | 2_8

from typing import List

Memo = dict[str, int]


class Solution:
    def recursiveMaxProfit(
        self,
        prices: List[int],
        idx: int,
        is_holding_stock: bool,
        memo: Memo,
    ) -> int:
        if idx == len(prices):
            return 0

        price = prices[idx]

        if f"{idx}_{is_holding_stock}" in memo:
            return memo[f"{idx}_{is_holding_stock}"]

        profit_if_skip = self.recursiveMaxProfit(
            prices, idx + 1, is_holding_stock, memo
        )

        if is_holding_stock:
            profit = max(profit_if_skip, price)
            memo[f"{idx}_True"] = profit
            return profit

        profit_if_buy = -price + self.recursiveMaxProfit(prices, idx + 1, True, memo)
        profit = max(profit_if_skip, profit_if_buy)
        memo[f"{idx}_False"] = profit
        return profit

    def maxProfit(self, prices: List[int]) -> int:
        return self.recursiveMaxProfit(prices, 0, False, dict())


sol = Solution()
print(sol.maxProfit([7, 1, 5, 3, 6, 4]))  # 5
print(sol.maxProfit([7, 6, 4, 3, 1]))  # 0

Time complexity = 2^n
Space complexity = n

With memoisation
Time complexity = n
Space complexity = n

from typing import List

Memo = dict[str, int]


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        left = 0
        right = 1
        max_profit = 0
        while right < len(prices) and right > left:
            if prices[right] > prices[left]:
                max_profit = max(max_profit, prices[right] - prices[left])
                right += 1
                continue
            left = right
            right += 1
        return max_profit


sol = Solution()
# print(sol.maxProfit([1, 2, 3, 0, 2]))  # 3
print(sol.maxProfit([1, 5, 3, 6, 4]))  # 5
print(sol.maxProfit([7, 6, 4, 3, 1]))  # 0

    [7, 1, 5, 3, 6, 4]
                 ^  for 6, min_so_far = 1,
                           max_profit_so_far = max(max_profit_so_far, 6 - 1) = 5

from typing import List

Memo = dict[str, int]


class Solution:
    # O(N)
    def maxProfit(self, prices: List[int]) -> int:
        min_price_so_far = prices[0]
        max_profit_so_far = 0
        for idx in range(1, len(prices)):
            price = prices[idx]
            profit = price - min_price_so_far

            min_price_so_far = min(min_price_so_far, price)
            max_profit_so_far = max(max_profit_so_far, profit)
        return max_profit_so_far


sol = Solution()

from typing import List

Memo = dict[str, int]


class Solution:
    def recursiveMaxProfit(
        self,
        prices: List[int],
        idx: int,
        is_holding_stock: bool,
        memo: Memo,
    ) -> int:
        if idx >= len(prices):
            return 0

        memo_key = f"{idx}_{is_holding_stock}"

        if memo_key in memo:
            return memo[memo_key]

        profit_if_skipped = self.recursiveMaxProfit(
            prices, idx + 1, is_holding_stock, memo
        )
        profit_on_trade = 0

        # We have already bought the stock and we can sell it
        if is_holding_stock:
            profit_on_trade = prices[idx] + self.recursiveMaxProfit(
                prices, idx + 1, False, memo
            )
        else:
            # We can buy the stock
            profit_on_trade = -prices[idx] + self.recursiveMaxProfit(
                prices, idx + 1, True, memo
            )

        profit = max(profit_if_skipped, profit_on_trade)

        memo[memo_key] = profit

        return profit

    def maxProfit(self, prices: List[int]) -> int:
        return self.recursiveMaxProfit(prices, 0, False, dict())

    # dp = [[0, [0, 0]] for _ in range(length_of_prices + 1)]
    # for idx in range(length_of_prices - 1, -1, -1):
    #     dp[idx][1][0] = max(dp[idx + 1][1][0], prices[idx] + dp[idx + 1][1][1])
    #     dp[idx][1][1] = max(dp[idx + 1][1][1], -prices[idx] + dp[idx + 1][1][0])
    def maxProfitDp(self, prices: List[int]) -> int:
        length_of_prices = len(prices)
        # [max profit when holding stock, max profit when not holding stock]
        dp = [[0, 0] for _ in range(length_of_prices + 1)]
        for idx in range(length_of_prices - 1, -1, -1):
            dp[idx][0] = max(dp[idx + 1][0], prices[idx] + dp[idx + 1][1])
            dp[idx][1] = max(dp[idx + 1][1], -prices[idx] + dp[idx + 1][0])

        print(dp)

        # We should return the max profit when we don't have any stock
        # having stock without selling it is not a valid answer
        return dp[0][1]

    def maxProfitDpOptimised(self, prices: List[int]) -> int:
        max_profit_when_holding_stock = 0
        max_profit_when_not_holding_stock = 0

        length_of_prices = len(prices)
        for idx in range(length_of_prices - 1, -1, -1):
            max_profit_when_holding_stock = max(
                max_profit_when_holding_stock,
                prices[idx] + max_profit_when_not_holding_stock,
            )
            max_profit_when_not_holding_stock = max(
                max_profit_when_not_holding_stock,
                -prices[idx] + max_profit_when_holding_stock,
            )

        return max_profit_when_not_holding_stock

sol = Solution()
# print(sol.maxProfit([7, 1, 5, 3, 6, 4]))  # 7
print(sol.maxProfitDp([7, 1, 5, 3, 6, 4]))  # 7
print(sol.maxProfitDpOptimised([7, 1, 5, 3, 6, 4]))  # 7

from typing import List

Memo = dict[str, int]


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        left = 0
        right = 1
        max_profit = 0
        while right < len(prices) and right > left:
            if prices[right] > prices[left]:
                max_profit += prices[right] - prices[left]
            left = right
            right += 1
        return max_profit


sol = Solution()
print(sol.maxProfit([7, 4, 10, 15, 3, 10]))

from typing import List

Memo = dict[str, int]


class Solution:
    # O(N) ST because memo key is n * 2 decisions * 2 max trades
    def recursiveMaxProfit(
        self,
        prices: List[int],
        idx: int,
        is_holding_stock: bool,
        no_of_trades: int,
        memo: Memo,
    ) -> int:
        if idx >= len(prices):
            return 0

        if no_of_trades >= 2:
            return 0

        memo_key = f"{idx}_{is_holding_stock}_{no_of_trades}"

        if memo_key in memo:
            return memo[memo_key]

        profit_if_skipped = self.recursiveMaxProfit(
            prices, idx + 1, is_holding_stock, no_of_trades, memo
        )
        profit_on_trade = 0

        # We have already bought the stock and we can sell it
        if is_holding_stock:
            profit_on_trade = prices[idx] + self.recursiveMaxProfit(
                prices, idx + 1, False, no_of_trades + 1, memo
            )
        else:
            # We can buy the stock
            profit_on_trade = -prices[idx] + self.recursiveMaxProfit(
                prices, idx + 1, True, no_of_trades, memo
            )

        profit = max(profit_if_skipped, profit_on_trade)

        memo[memo_key] = profit

        return profit

    def maxProfit(self, prices: List[int]) -> int:
        return self.recursiveMaxProfit(prices, 0, False, 0, dict())

    def maxProfitDp(self, prices: List[int]) -> int:
        length_of_prices = len(prices)

        # dp[i][t] = trade count
        # dp[i][t][0] = profit when holding stock
        # dp[i][t][1] = profit when not holding stock

        dp: List[List[List[int]]] = [
            [[0, 0] for _ in range(2 + 1)] for _ in range(length_of_prices + 1)
        ]
        for idx in range(length_of_prices - 1, -1, -1):
            for trade_idx in range(2):
                dp[idx][trade_idx][0] = max(
                    dp[idx + 1][trade_idx][0],
                    prices[idx] + dp[idx + 1][trade_idx + 1][1],
                )
                dp[idx][trade_idx][1] = max(
                    dp[idx + 1][trade_idx][1], -prices[idx] + dp[idx + 1][trade_idx][0]
                )

        return dp[0][0][1]

    def generateDpArray(self) -> List[List[int]]:
        return [[0, 0] for _ in range(2 + 1)]

    def maxProfitOptimised(self, prices: List[int]) -> int:
        length_of_prices = len(prices)

        # dp[i][t] = trade count
        # dp[i][t][0] = profit when holding stock
        # dp[i][t][1] = profit when not holding stock

        prev = self.generateDpArray()
        next = self.generateDpArray()

        for idx in range(length_of_prices - 1, -1, -1):
            for trade_idx in range(2):
                next[trade_idx][0] = max(
                    prev[trade_idx][0],
                    prices[idx] + prev[trade_idx + 1][1],
                )
                next[trade_idx][1] = max(
                    prev[trade_idx][1], -prices[idx] + prev[trade_idx][0]
                )
            if idx == 0:
                break
            prev = next
            next = self.generateDpArray()

        return next[0][1]


sol = Solution()
print(sol.maxProfitDp([3, 3, 5, 0, 0, 3, 1, 4]))  # 6
print(sol.maxProfitOptimised([3, 3, 5, 0, 0, 3, 1, 4]))  # 6

from typing import List

Memo = dict[str, int]


class Solution:
    # O(NK) ST because memo key is n * 2 decisions * K max trades
    def recursiveMaxProfit(
        self,
        prices: List[int],
        max_trades: int,
        idx: int,
        is_holding_stock: bool,
        no_of_trades: int,
        memo: Memo,
    ) -> int:
        if idx >= len(prices):
            return 0

        if no_of_trades >= max_trades:
            return 0

        memo_key = f"{idx}_{is_holding_stock}_{no_of_trades}"

        if memo_key in memo:
            return memo[memo_key]

        profit_if_skipped = self.recursiveMaxProfit(
            prices, max_trades, idx + 1, is_holding_stock, no_of_trades, memo
        )
        profit_on_trade = 0

        # We have already bought the stock and we can sell it
        if is_holding_stock:
            profit_on_trade = prices[idx] + self.recursiveMaxProfit(
                prices, max_trades, idx + 1, False, no_of_trades + 1, memo
            )
        else:
            # We can buy the stock
            profit_on_trade = -prices[idx] + self.recursiveMaxProfit(
                prices, max_trades, idx + 1, True, no_of_trades, memo
            )

        profit = max(profit_if_skipped, profit_on_trade)

        memo[memo_key] = profit

        return profit

    def maxProfit(self, max_trades: int, prices: List[int]) -> int:
        return self.recursiveMaxProfit(prices, max_trades, 0, False, 0, dict())

    def maxProfitDp(self, max_trades: int, prices: List[int]) -> int:
        length_of_prices = len(prices)

        # dp[i][t] = trade count
        # dp[i][t][0] = profit when holding stock
        # dp[i][t][1] = profit when not holding stock

        dp: List[List[List[int]]] = [
            [[0, 0] for _ in range(max_trades + 1)] for _ in range(length_of_prices + 1)
        ]
        for idx in range(length_of_prices - 1, -1, -1):
            for trade_idx in range(max_trades):
                dp[idx][trade_idx][0] = max(
                    dp[idx + 1][trade_idx][0],
                    prices[idx] + dp[idx + 1][trade_idx + 1][1],
                )
                dp[idx][trade_idx][1] = max(
                    dp[idx + 1][trade_idx][1], -prices[idx] + dp[idx + 1][trade_idx][0]
                )

        return dp[0][0][1]

    def generateDpArray(self, max_trades: int) -> List[List[int]]:
        return [[0, 0] for _ in range(max_trades + 1)]

    def maxProfitOptimised(self, max_trades: int, prices: List[int]) -> int:
        length_of_prices = len(prices)

        # dp[i][t] = trade count
        # dp[i][t][0] = profit when holding stock
        # dp[i][t][1] = profit when not holding stock

        prev = self.generateDpArray(max_trades)
        next = self.generateDpArray(max_trades)

        for idx in range(length_of_prices - 1, -1, -1):
            for trade_idx in range(max_trades):
                next[trade_idx][0] = max(
                    prev[trade_idx][0],
                    prices[idx] + prev[trade_idx + 1][1],
                )
                next[trade_idx][1] = max(
                    prev[trade_idx][1], -prices[idx] + prev[trade_idx][0]
                )
            if idx == 0:
                break
            prev = next
            next = self.generateDpArray(max_trades)

        return next[0][1]


sol = Solution()
print(sol.maxProfit(2, [2, 4, 1]))
print(sol.maxProfitOptimised(2, [2, 4, 1]))

from typing import List

Memo = dict[str, int]


class Solution:
    # O(N) ST because memo key is n * 2 decisions
    def recursiveMaxProfit(
        self,
        prices: List[int],
        idx: int,
        is_holding_stock: bool,
        memo: Memo,
    ) -> int:
        if idx >= len(prices):
            return 0

        memo_key = f"{idx}_{is_holding_stock}"

        if memo_key in memo:
            return memo[memo_key]

        profit_if_skipped = self.recursiveMaxProfit(
            prices, idx + 1, is_holding_stock, memo
        )
        profit_on_trade = 0

        # We have already bought the stock and we can sell it
        if is_holding_stock:
            profit_on_trade = prices[idx] + self.recursiveMaxProfit(
                prices, idx + 2, False, memo
            )  # Cool down, so we skip trading on the next day
        else:
            # We can buy the stock
            profit_on_trade = -prices[idx] + self.recursiveMaxProfit(
                prices, idx + 1, True, memo
            )

        profit = max(profit_if_skipped, profit_on_trade)

        memo[memo_key] = profit

        return profit

    def maxProfit(self, prices: List[int]) -> int:
        return self.recursiveMaxProfit(prices, 0, False, dict())

    def maxProfitDp(self, prices: List[int]) -> int:
        length_of_prices = len(prices)
        # [max profit when holding stock, max profit when not holding stock]
        dp = [[0, 0] for _ in range(length_of_prices + 2)]
        for idx in range(length_of_prices - 1, -1, -1):
            dp[idx][0] = max(dp[idx + 1][0], prices[idx] + dp[idx + 2][1])
            dp[idx][1] = max(dp[idx + 1][1], -prices[idx] + dp[idx + 1][0])

        print(dp)

        # We should return the max profit when we don't have any stock
        # having stock without selling it is not a valid answer
        return dp[0][1]

    def maxProfitDpOptimised(self, prices: List[int]) -> int:
        length_of_prices = len(prices)

        prev_2_prev = [0, 0]
        prev = [0, 0]
        next = [0, 0]

        for idx in range(length_of_prices - 1, -1, -1):
            next[0] = max(prev[0], prices[idx] + prev_2_prev[1])
            next[1] = max(prev[1], -prices[idx] + prev[0])

            if idx == 0:
                break

            prev_2_prev = prev
            prev = next
            next = [0, 0]

        return next[1]


sol = Solution()

print(sol.maxProfit([1, 2, 3, 0, 2]))  # 3
print(sol.maxProfitDp([1, 2, 3, 0, 2]))  # 3
print(sol.maxProfitDpOptimised([1, 2, 3, 0, 2]))  # 3

from typing import List

Memo = dict[str, int]


class Solution:
    # O(N) ST because memo key is n * 2 decisions
    def recursiveMaxProfit(
        self,
        prices: List[int],
        idx: int,
        is_holding_stock: bool,
        fee: int,
        memo: Memo,
    ) -> int:
        if idx >= len(prices):
            return 0

        memo_key = f"{idx}_{is_holding_stock}"

        if memo_key in memo:
            return memo[memo_key]

        profit_if_skipped = self.recursiveMaxProfit(
            prices, idx + 1, is_holding_stock, fee, memo
        )

        profit_on_trade = 0

        # We have already bought the stock and we can sell it
        if is_holding_stock:
            profit_on_trade = (
                prices[idx]
                - fee
                + self.recursiveMaxProfit(prices, idx + 1, False, fee, memo)
            )
        else:
            # We can buy the stock
            profit_on_trade = -prices[idx] + self.recursiveMaxProfit(
                prices, idx + 1, True, fee, memo
            )

        profit = max(profit_if_skipped, profit_on_trade)

        memo[memo_key] = profit

        return profit

    def maxProfit(self, prices: List[int], fee: int) -> int:
        return self.recursiveMaxProfit(prices, 0, False, fee, dict())

    def maxProfitDpOptimised(self, prices: List[int], fee: int) -> int:
        max_profit_when_holding_stock = 0
        max_profit_when_not_holding_stock = 0

        length_of_prices = len(prices)
        for idx in range(length_of_prices - 1, -1, -1):
            max_profit_when_holding_stock = max(
                max_profit_when_holding_stock,
                prices[idx] -fee + max_profit_when_not_holding_stock,
            )
            max_profit_when_not_holding_stock = max(
                max_profit_when_not_holding_stock,
                -prices[idx] + max_profit_when_holding_stock,
            )

        return max_profit_when_not_holding_stock

sol = Solution()
print(sol.maxProfit([1, 3, 2, 8, 4, 9], 2))  # 8
print(sol.maxProfitDpOptimised([1, 3, 2, 8, 4, 9], 2))  # 8

from typing import List, Dict

Memo = Dict[int, bool]


class Solution:
    # n^n
    # aft memo n*n = n^2
    def recursiveJump(self, nums: List[int], idx: int, memo: Memo) -> bool:
        if idx == len(nums) - 1:
            return True

        if idx >= len(nums):
            return False

        next_jump = nums[idx]

        if next_jump == 0:
            return False

        next_jump_max_idx = idx + next_jump

        if next_jump_max_idx == len(nums) - 1:
            return True

        memoised_result = memo.get(next_jump_max_idx, None)
        if memoised_result is not None:
            return memoised_result

        for next_jump_idx in range(idx + 1, next_jump_max_idx + 1):
            if self.recursiveJump(nums, next_jump_idx, memo):
                return True
            memo[next_jump_idx] = False

        return False

    def canJump(self, nums: List[int]) -> bool:
        return self.recursiveJump(nums, 0, dict())

    def canJumpDp(self, nums: List[int]) -> bool:
        nums_length = len(nums)

        dp = [False for _ in range(nums_length)]
        dp[-1] = True

        for idx in range(nums_length - 2, -1, -1):
            can_jump_upto = nums[idx]
            can_jump_upto_idx = min(idx + can_jump_upto, nums_length - 1)
            for jump_idx in range(idx, can_jump_upto_idx + 1):
                if dp[jump_idx]:
                    dp[idx] = True
                    break

        return dp[0]

    def canJumpGreedy(self, nums: List[int]) -> bool:
        length = len(nums)
        max_reach = 0

        for idx in range(length):
            can_reach = nums[idx]
            can_reach_idx = idx + can_reach
            max_reach = max(max_reach, can_reach_idx)
            if max_reach >= length - 1:
                return True
            if idx >= max_reach:
                return False

        return False


sol = Solution()
print(sol.canJumpGreedy([2, 3, 1, 1, 4]))  # True
print(sol.canJumpGreedy([3, 2, 1, 0, 4]))  # False
print(sol.canJumpGreedy([1, 2, 3]))  # True
print(sol.canJumpGreedy([0]))  # True
print(sol.canJumpGreedy([0, 2, 3]))  # False

flowchart TD
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px,color:#000000;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px,color:#000000;
    classDef blue fill:#ccccff,stroke:#000,stroke-width:2px,color:#000000;
    classDef orange fill:#ffcc99,stroke:#000,stroke-width:2px,color:#000000;
    classDef yellow fill:#ffff99,stroke:#000,stroke-width:2px,color:#000000;

    root[2]:::blue

    root --> 3
    3 --> 1.1[1] --> 1.1.2[1] --> 4
    3 --> 1.2[1] --> 4.1[4]
    3 --> 4.2[4]

    root --> 1 --> 1.2.1[1] --> 4.3[4]

from typing import List, Dict

Memo = Dict[int, float]


class Solution:
    # O(m^n)
    # O(m^n) nodes + O(n) stack space

    # With memory optimisation
    # O(m*n) ~ 0(n^2) time
    # O(2n)
    def recursiveJump(
        self, nums: List[int], idx: int, jumps_so_far, memo: Memo
    ) -> float:
        length_nums = len(nums)
        if idx >= length_nums - 1:
            return jumps_so_far

        if idx in memo:
            return memo[idx]

        next_max_jump = nums[idx]
        next_max_jump_idx = min(idx + next_max_jump, length_nums)

        min_jumps_so_far = float("inf")
        for jump_idx in range(idx + 1, next_max_jump_idx + 1):
            min_jumps_so_far = min(
                jumps_so_far + self.recursiveJump(nums, jump_idx, 1, memo),
                min_jumps_so_far,
            )

        memo[idx] = min_jumps_so_far
        return memo[idx]

    def jump(self, nums: List[int]) -> int:
        max_jumps = self.recursiveJump(nums, 0, 0, dict())
        if max_jumps == "inf":
            return -1
        return int(max_jumps)

    def jumpDp(self, nums: list[int]) -> int:
        length = len(nums)
        dp = [float("inf") for _ in range(length)]
        dp[0] = 0

        # O(N)
        for idx in range(length):
            # O(M) ~ O(N)
            for jdx in range(idx + 1, min(idx + nums[idx] + 1, length)):
                dp[jdx] = min(dp[jdx], dp[idx] + 1)

        return int(dp[-1])

    # Greedy
    # 0, 1, 2, 3, 4

    # 2, 3, 1, 1, 4
    # ^ (max_reach = 2, curr_max_reach_end = 2, idx = 0)

    # 2, 3, 1, 1, 4
    #    ^ (max_reach = 4, curr_max_reach_end = 2, idx = 4)

    # 2, 3, 1, 1, 4
    #       ^ (max_reach = 4, curr_max_reach_end = 4, idx = 4, jumps = 1), increment jumps,
    #       when idx = curr_max_reach_end


    def jumpGreedy(self, nums: list[int]) -> int:
        length = len(nums)

        jumps = 0
        max_reach = 0
        curr_max_reach_end = 0

        for idx in range(length - 1):
            max_reach = max(max_reach, min(idx + nums[idx], length - 1))
            if idx == curr_max_reach_end:
                curr_max_reach_end = max_reach
                jumps += 1

        return jumps


sol = Solution()
# print(sol.jump([2, 3, 0, 1, 4]))  # 2
# print(sol.jump([2, 3, 1, 1, 4]))  # 2
# print(sol.jump([1, 2, 1, 1, 1]))  # 3

# print(sol.jumpDp([2, 3, 0, 1, 4]))  # 2
# print(sol.jumpDp([2, 3, 1, 1, 4]))  # 2
print(sol.jumpGreedy([2, 3, 1, 1, 4]))
# print(sol.jumpDp([1, 2, 1, 1, 1]))  # 3

flowchart TD
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px,color:#000000;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px,color:#000000;
    classDef blue fill:#ccccff,stroke:#000,stroke-width:2px,color:#000000;
    classDef orange fill:#ffcc99,stroke:#000,stroke-width:2px,color:#000000;
    classDef yellow fill:#ffff99,stroke:#000,stroke-width:2px,color:#000000;

    f_5[f5]:::blue
    f_5 --> f_4[f4]
    f_5 --> f_3[f3]

    f_4 --> f_3.1[f3]
    f_4 --> f_2[f2]

    f_3 --> f_2.1[f2]
    f_3 --> f_1[f1]

from typing import Dict

Memo = Dict[int, int]


class Solution:
    def fibRecursive(self, target: int, memo: Memo) -> int:
        if target == 0:
            return 0

        if target == 1:
            return 1

        if target in memo:
            return memo[target]

        memo[target] = self.fibRecursive(target - 1, memo) + self.fibRecursive(
            target - 2, memo
        )

        return memo[target]

    def fib(self, n: int) -> int:
        return self.fibRecursive(n, dict())

    def fibDp(self, target: int) -> int:

        if target == 0:
            return 0

        if target == 1:
            return 1

        dp = [0 for _ in range(target + 1)]
        dp[-1] = 0
        dp[-2] = 1

        for idx in range(target - 2, -1, -1):
            dp[idx] = dp[idx + 1] + dp[idx + 2]

        return dp[0]

    def fibDpOptimised(self, target: int) -> int:

        if target == 0:
            return 0

        if target == 1:
            return 1

        left = 1
        right = 0

        for _ in range(target - 2, -1, -1):
            new_left = left + right
            right = left
            left = new_left

        return left


sol = Solution()
print(sol.fib(2))
print(sol.fibDp(3))
print(sol.fibDpOptimised(3))

Sample Input #1
n = 2
Sample Output #1
1 // 0, 1
Sample Input #2
n = 6
Sample Output #2
5 // 0, 1, 1, 2, 3, 5

export const insertionSort = (
	array: number[],
	arrayLength: number = array.length,
	isDesending = false,
	lastSwapPointer: number = 0,
	index = 0
): number[] => {
	// pointers
	const nextIndex = index + 1;
	const prevIndex = index - 1;

	// values
	const el = array[index];
	const nextEl = array[nextIndex];
	const prevEl = array[prevIndex];

	if (isDesending) {
		if (prevEl > el) {
			// swap
			[array[prevIndex], array[index]] = [el, prevEl];
		}
		// no more values to desend to so set to last swap pointer
		if (index === 1) {
			isDesending = false;
			index = lastSwapPointer;
			return insertionSort(
				array,
				arrayLength,
				isDesending,
				lastSwapPointer,
				index
			);
		}
		index = prevIndex;
		return insertionSort(
			array,
			arrayLength,
			isDesending,
			lastSwapPointer,
			index
		);
	}
	if (nextEl < el) {
    // swap
		[array[nextIndex], array[index]] = [el, nextEl];
		lastSwapPointer = nextIndex;
		isDesending = true;
	}
	index = nextIndex;
	if (nextIndex === arrayLength) {
		return array;
	}
	return insertionSort(array, arrayLength, isDesending, lastSwapPointer, index);
};
```

```typescript
export const insertionSort = (array: number[]): number[] => {
	// increment to next value
	for (let outerPointer = 1; outerPointer < array.length; outerPointer += 1) {
		// check previous values
		for (
			let innerPointer = outerPointer;
			innerPointer > 0 && array[innerPointer] < array[innerPointer - 1];
			innerPointer -= 1
		) {
			const previnnerPointer = innerPointer - 1;
			const prevEl = array[previnnerPointer];
			const el = array[innerPointer];
			[array[innerPointer - 1], array[innerPointer]] = [el, prevEl];
		}
	}
	return array;
};

Time complexity: O(N^2)
since we have to iterate through the array multiple times to sort the array

---------------------
    UP
[8, 5, 2, 9, 5, 6, 3]
[5, 8, 2, 9, 5, 6, 3] swap
    ^
---------------------
       UP
[5, 8, 2, 9, 5, 6, 3]
       ^
[5, 2, 8, 9, 5, 6, 3]
    ^
[5, 2, 8, 9, 5, 6, 3]
 ^
[2, 5, 8, 9, 5, 6, 3]

---------------------
          UP
[2, 5, 8, 9, 5, 6, 3]
          ^
---------------------
             UP
[2, 5, 8, 9, 5, 6, 3]
             ^
[2, 5, 8, 5, 9, 6, 3]
          ^
[2, 5, 5, 8, 9, 6, 3]
       ^
[2, 5, 5, 8, 9, 6, 3]

---------------------
                UP
[2, 5, 5, 8, 9, 6, 3]
                ^
[2, 5, 5, 8, 6, 9, 3]
             ^
[2, 5, 5, 6, 8, 9, 3]
          ^
---------------------
                   UP
[2, 5, 5, 6, 8, 9, 3]
                   ^
[2, 5, 5, 6, 8, 3, 9]
                ^
[2, 5, 5, 6, 3, 8, 9]
             ^
[2, 5, 5, 3, 6, 8, 9]
          ^
[2, 5, 3, 5, 6, 8, 9]
       ^
[2, 3, 5, 5, 6, 8, 9]

---------------------

 >  <
[8, 5, 2, 9, 5, 6, 3]
    >  <
[5, 8, 2, 9, 5, 6, 3]
          >  <
[5, 2, 8, 9, 5, 6, 3]
             >  <
[5, 2, 8, 5, 9, 6, 3]
                >  <
[5, 2, 8, 5, 6, 9, 3]
 >  <
[5, 2, 8, 5, 6, 3, 9]
[2, 5, 8, 5, 6, 3, 9]
       >  <
[2, 5, 8, 5, 6, 3, 9]
[2, 5, 5, 8, 6, 3, 9]
...

export function bubbleSort(
  array: number[],
  arrayLength = array.length,
  maxIndex = arrayLength - 1
): number[] {
  let noMutations = true;
  let largestValueIndex = maxIndex;
  // O(N^2)
  for (let index = 0; index <= largestValueIndex; index++) {
    const nextIndex = index + 1;

    const currentValue = array[index];
    const nextValue = nextIndex <= maxIndex ? array[nextIndex] : null;

    if (typeof nextValue === 'number' && nextValue < currentValue) {
      // only value is updated in array
      array[index] = nextValue;
      // array length remains unchanged
      array[nextIndex] = currentValue;
      noMutations = false;
    }

    // reduce array iteration length when for loop ends
    // the last index will always be the largest possible element,
    if (index === largestValueIndex) largestValueIndex = largestValueIndex - 1;
  }
  if (noMutations) return array;
  return bubbleSort(array, arrayLength, maxIndex);
}

export const quickSort = (array: number[] = []): number[] => {
  if (!array.length) return [];

  const pivotIndex = Math.floor(array.length / 2);
  const pivot = array.slice(pivotIndex)[0];
  const [left, right]: [number[], number[]] = [[], []];

  array.forEach((el, index) => {
    if (pivotIndex === index) return;
    if (el <= pivot) return left.push(el);
    return right.push(el);
  });

  const returnVal = quickSort(left).concat(pivot).concat(quickSort(right));
  console.log('array', {
    pivot,
    left,
    right,
    returnVal,
  });
  return returnVal;
};

//                                                               7
//                                                     [8, 5, 2, 9, 5, 6, 3]
//                                                               ^
//                                                     4   
//                                          [ 8, 5, 2, 5, 6, 3 ]   []
//                                                     ^
//                                             1              5
//                                        [ 5, 2, 3 ]    [ 8, 6 ]
//                                             ^              ^
//                                                    2        6
//        * pivot                            [ ] [ 5, 3 ]    [ 8 ]
//                                                    ^  3     ^
//        * left + right                               [ 5 ]    [ ]               Callstack execution order (LIFO) ^^^ 
//                                                                                Values are returned from left (bottom-up) - pivot - right (bottom-up)
//

flowchart TD
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px,color:#000000;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px,color:#000000;
    classDef blue fill:#ccccff,stroke:#000,stroke-width:2px,color:#000000;
    classDef orange fill:#ffcc99,stroke:#000,stroke-width:2px,color:#000000;
    classDef yellow fill:#ffff99,stroke:#000,stroke-width:2px,color:#000000;

  root[-] --> a --> p --> p1[p] --> l --> e --> end_app1le[$]:::red
  p --> e1 --> end_ape1[$]:::red

interface Children {
	[key: string]: Node;
}

class Node {
	name: string = '';
	children: Children = {};

	constructor(name: string) {
		this.name = name;
	}

	addChild(name: string) {
		const child = new Node(name);
		this.children[name] = child;
	}

	hasChild(name: string): boolean {
		if (this.children[name]) return true;
		return false;
	}

	getChild(name: string): Node {
		return this.children[name];
	}
}

class Trie {
	tree: Node = new Node('');

	constructor() {}

	// N = characters in the word
	// O(N)T | O(N)S
	insert(word: string, currIdx = 0, node = this.tree): void {
		const char = word[currIdx];
		if (!char) {
			node.addChild('$');
			return;
		}
		if (node.hasChild(char)) {
			this.insert(word, currIdx + 1, node.children[char]);
			return;
		}
		node.addChild(char);
		this.insert(word, currIdx + 1, node.children[char]);
		return;
	}

	// O(N)T | O(N)S, recursive stack
	search(word: string, currIdx = 0, node = this.tree): boolean {
		const char = word[currIdx];
		if (!char) {
			return node.hasChild('$');
		}
		if (!node.hasChild(char)) {
			return false;
		}
		return this.search(word, currIdx + 1, node.getChild(char));
	}

	// O(N)T | O(N)S recursive stack
	startsWith(word: string, currIdx = 0, node = this.tree): boolean {
		const char = word[currIdx];
		if (!char) {
			return true;
		}
		if (!node.hasChild(char)) {
			return false;
		}
		return this.startsWith(word, currIdx + 1, node.getChild(char));
	}
}

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

interface Children {
	[key: string]: Node;
}

class Node {
	name: string = '';
	children: Children = {};

	constructor(name: string) {
		this.name = name;
	}

	addChild(name: string) {
		const child = new Node(name);
		this.children[name] = child;
	}

	hasChild(name: string): boolean {
		if (this.children[name]) return true;
		return false;
	}

	getChild(name: string): Node {
		return this.children[name];
	}

	getChildren(): Node[] {
		return Object.values(this.children);
	}
}

class WordDictionary {
	tree: Node = new Node('');

	constructor() {}

	addWord(word: string, currIdx = 0, node = this.tree): void {
		const char = word[currIdx];
		if (!char) {
			node.addChild('$');
			return;
		}
		if (node.hasChild(char)) {
			this.addWord(word, currIdx + 1, node.children[char]);
			return;
		}
		node.addChild(char);
		this.addWord(word, currIdx + 1, node.children[char]);
		return;
	}

	// O(N)T | O(clidren_with_wild_cards^N)S
	search(word: string, currIdx = 0, node = this.tree): boolean {
		const char = word[currIdx];
		if (!char) {
			return node.hasChild('$');
		}
		if (char === '.') {
			for (let child of node.getChildren()) {
				if (this.search(word, currIdx + 1, child)) return true;
			}
			return false;
		}
		if (!node.hasChild(char)) {
			return false;
		}
		return this.search(word, currIdx + 1, node.getChild(char));
	}
}