-Problem Solving Patterns
-Frequency Counter Patterns
-Multiple Pointers Patterns
-Sliding Window Pattern
-Divide and Conquer Pattern
Problem Solving Patterns
These are some common patterns to solving problems with code.
Frequency Counter
Multiple Pointers
Sliding Window
Divide and Conquer
Dynamic Programming
Greedy Algorithms
Backtracking
and many many more.
There are many different approaches to solving common problems.
Frequency Counter Patterns
A frequency counter uses objects or sets to collect values and frequencies. May often avoid the need for nested loops operations with array and strings.
Frequency Counter Problem
Write a function called same, which accepts two arrays. The function should return true if every value in the array has its corresponding value squared in the second array. The frequency of values must be the same.
function same(arr1, arr2){
if(arr1.length !== arr2.length){
return false;
}
let frequencyCounter1 = {}
let frequencyCounter2 = {}
for(let val of arr1){
frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
}
for(let val of arr2){
frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1
}
console.log(frequencyCounter1);
console.log(frequencyCounter2);
for(let key in frequencyCounter1){
if(!(key ** 2 in frequencyCounter2)){
return false
}
if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
return false
}
}
return true
}
same([1,2,3,2,5], [9,1,4,4,11])
Anagram Problem
Given two strings, write a function to determine if the second string is an anagram of the first.
function validAnagram(first, second) {
if (first.length !== second.length) {
return false;
}
const lookup = {};
for (let i = 0; i < first.length; i++) {
let letter = first[i];
// if letter exists, increment, otherwise set to 1
lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
}
console.log(lookup)
for (let i = 0; i < second.length; i++) {
let letter = second[i];
// can't find letter or letter is zero then it's not an anagram
if (!lookup[letter]) {
return false;
} else {
lookup[letter] -= 1;
}
}
return true;
}
// {a: 0, n: 0, g: 0, r: 0, m: 0,s:1}
validAnagram('anagrams', 'nagaramm')
Multiple Pointers Patterns
Creating pointers or values that correspond to an index or position and move towards the beginning, end, or middle based on certain condition.
Multiple Pointers is very efficient for solving problems with minimal space complexity as well.
Sum Zero Problem
function sumZero(arr){
for(let i = 0; i < arr.length; i++){
for(let j = i+1; j < arr.length; j++){
if(arr[i] + arr[j] === 0){
return [arr[i], arr[j]];
}
}
}
}
sumZero([-4,-3,-2,-1,0,1,2,5])
Count Unique Values Problem
Implement a function called countUniqueValues, which accepts a sorted array, and counts the unique values in the array. There can be negative numbers in the array, but it will always be sorted.
function countUniqueValues(arr){
if(arr.length === 0) return 0;
var i = 0;
for(var j = 1; j < arr.length; j++){
if(arr[i] !== arr[j]){
i++;
arr[i] = arr[j]
}
}
return i + 1;
}
countUniqueValues([1,2,2,5,7,7,99])
Sliding Window Pattern
This pattern involves creating a window which can be either an array or number from one position to another. Depending on a certain condition, the window either increases or closes and a new window is created.
Very useful for keeping track of a subset of data in an array/string.
Max Subarray Sum Problem
function maxSubarraySum(arr, num){
let maxSum = 0;
let tempSum = 0;
if (arr.length < num) return null;
for (let i = 0; i < num; i++) {
maxSum += arr[i];
}
tempSum = maxSum;
for (let i = num; i < arr.length; i++) {
tempSum = tempSum - arr[i - num] + arr[i];
maxSum = Math.max(maxSum, tempSum);
}
return maxSum;
}
maxSubarraySum([2,6,9,2,1,8,5,6,3],3)
Write a function called maxSubarraySum which accepts an array of integers and a number called n. The function should calculate the maximum sum of n consecutive elements in the array.
Divide and Conquer Pattern
This pattern involves dividing a data set into smaller chunks and then repeating a process with a subset of data.
This pattern can decrease time complexity.
Divide and Conquer Problem
Given a sorted array of integers, write a function called search, that accepts a value and returns the index where the value passed to the function is located. If the value if not found, return -1.
function search(array, val) {
let min = 0;
let max = array.length - 1;
while (min <= max) {
let middle = Math.floor((min + max) / 2);
let currentElement = array[middle];
if (array[middle] < val) {
min = middle + 1;
}
else if (array[middle] > val) {
max = middle - 1;
}
else {
return middle;
}
}
return -1;
}
Top comments (0)