scratchpad

scratchpad.js

function getNumMatchesAtCoordinate(matrix, x, y) {
	const match = matrix[x][y]; // 1st is row, 2nd is col
	let numMatches = 0; // at least 1 match
	const maxLength = Math.min(matrix.length - x, matrix[0].length - y);
	for (let i = 0; i < maxLength; i++) {
		// increment row
		let isMatch = true;
		for (let j = 0; j <= i; j++) {
			// increment col
			// checks outermost row and column in the growing square
			// we don't need to recheck the middle
			if (matrix[x + j][y + i] !== match || matrix[x + i][y + j] !== match) {
				isMatch = false;
				break;
			}
		}
		if (isMatch) {
			numMatches++;
		} else {
			break;
		}
	}
	return numMatches; // this is the number of cells, which is the area
}

function getMaximalSquare(matrix) {
	let max = 0; // will be at least one
	for (let i = 0; i < matrix.length; i++) {
		// increment row
		for (let j = 0; j < matrix[i].length; j++) {
			// increment col
			if (matrix[i][j] === "1") {
				max = Math.max(max, getNumMatchesAtCoordinate(matrix, i, j));
			}
		}
	}
	return max * max; // multiply to get the area of the square
}

const matrix = [
	["1", "0", "1", "0", "0"],
	["1", "0", "1", "1", "1"],
	["1", "1", "1", "1", "1"],
	["1", "0", "0", "1", "0"],
];

getMaximalSquare(matrix);

function getLongestIncreasingSubsequence(nums) {
	function getLongest(nums) {
		let highest = 0;
		let counter = 0;
		for (let i = 0; i < nums.length; i++) {
			if (nums[i] > highest) {
				highest = nums[i];
				counter++;
			}
		}
		return counter;
	}

	let pointer = 0;
	let longest = 0;
	while (pointer < nums.length) {
		let checkLongest = getLongest(nums.slice(pointer));
		longest = longest > checkLongest ? longest : checkLongest;
		pointer++;
	}
	return longest;
}

function getPalindromes(s) {
	function getIsPalindrome(s) {
		if (s.length === 1) return true;

		const a = s.substring(0, parseInt((s.length - 1) / 2));
		let b = s.substring(parseInt((s.length - 1) / 2));

		if (b.length > a.length) b = b.substring(1);
		b = b.split("").reverse().join("");

		return a === b;
	}

	let count = s.length;
	let charPointer = 0;
	while (charPointer < s.length) {
		count = getIsPalindrome(s.substring(charPointer)) ? count + 1 : count;
		charPointer++;
	}

	return count;
}
getPalindromes("abcba");

// better versioning from chatgpt
function getPalindromes2(s) {
	function getIsPalindrome(s, left, right) {
		while (left >= 0 && right < s.length && s[left] === s[right]) {
			left--;
			right++;
		}
		return right - left - 1;
	}

	let count = s.length;
	for (let i = 0; i < s.length; i++) {
		count += getIsPalindrome(s, i, i) / 2;
		if (i < s.length - 1) {
			count += getIsPalindrome(s, i, i + 1) / 2;
		}
	}

	return count;
}

function findLongestTwoCharSubstringLength(s) {
	if (s.length < 2) return s.length;
	let left = 0;
	let max = 0;
	let right = 0;
	while (right < s.length) {
		let chars = [s.charAt(left)];
		while (chars.length <= 2 && right < s.length) {
			if (!chars.includes(s.charAt(right))) {
				if (chars.length === 2) {
					break;
				}
				chars.push(s.charAt(right));
			}
			right++;
		}
		max = Math.max(max, right - left);
		// Find the start of the next potential substring
		// tracking backwards from right allowing for identical chars at the right pointer
		if (right < s.length) {
			while (s.charAt(right - 1) === s.charAt(right)) {
				right--;
			}
			left = right;
		}
	}
	return max;
}

// or using object
function findLongestTwoCharSubstringLength(s) {
	if (s.length < 2) return s.length;

	let left = 0,
		right = 0,
		max = 0;
	let charCount = {};

	while (right < s.length) {
		// Add the current character at the right pointer to the hash map
		charCount[s[right]] = (charCount[s[right]] || 0) + 1;

		// If we have more than two distinct characters, move the left pointer
		while (Object.keys(charCount).length > 2) {
			charCount[s[left]]--;
			if (charCount[s[left]] === 0) delete charCount[s[left]];
			left++;
		}

		// Update the maximum length
		max = Math.max(max, right - left + 1);

		// Move the right pointer to the next character
		right++;
	}

	return max;
}

// Given an array of integers numbers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
// findTwoNumbers([2, 7, 11, 15], target = 9) // [1, 2]
function findTwoNumbers(nums, target) {
	let left = 0,
		right = nums.length - 1;
	let twoNumbers = [];

	while (left < right && twoNumbers.length === 0) {
		if (nums[left] + nums[right] === target) {
			twoNumbers = [left + 1, right + 1];
		}
		nums[left] + nums[right] < target ? left++ : right--;
	}

	return twoNumbers;
}