What are Problem Solving Patterns?
Let’s look at some problem solving patterns in this post. In the previous post we saw the problem solving approaches.
#1] Frequency Counter Pattern
This pattern uses objects or sets to collect values/frequencies of values. This can often avoid the need for nested loops or O(N^2) operations with arrays/strings.
For example:-
Write a function called same, which accepts two arrays. The function should return true if every value in the array has it’s 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
}
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], [4,1,9]) // true
same([1,2,3], [1,9]) // false
same([1,2,1], [4,4,1]) // false (must be same frequency)
same([1,2,3], [1,9]) // false
same([1,2,1], [4,4,1]) // false (must be same frequency)
#2] Multiple Pointers
Creating pointers or values that correspond to an index or position and move towards the beginning, end or middle based on a certain conditions. It is very efficient for solving problems with minimal space complexity as well.
For example:-
Write a function called sumZero which accepts a sorted array of integers. The function should find the first pair where the sum is 0. Return an array that includes both values that sum to zero or undefined if a pair does not exits.
function sumZero(arr){
let left = 0;
let right = arr.length – 1;
while(left < right){
let sum = arr[left] + arr[right];
if(sum === 0){
return [arr[left], arr[right]];
} else if(sum > 0){
right—;
} else {
left++;
}
}
}
sumZero([-3,-2,-1,0,1,2,3]) // [-3,3]
sumZero([-2,0,1,3]) // undefined
sumZero([1,2,3]) // undefined
sumZero([-2,0,1,3]) // undefined
sumZero([1,2,3]) // undefined
#3] Sliding Window
This pattern involves creating a window which can either be an array or number from 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 etc.
For example:-
Write a function 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.
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([1,2,5,2,8,1,5],2) // 10
maxSubarraySum([1,2,5,2,8,1,5],4) // 17
maxSubarraySum([4,2,1,6],1) // 6
maxSubarraySum([4,2,1,6,2],4) // 13
maxSubarraySum([],4) // null
maxSubarraySum([1,2,5,2,8,1,5],4) // 17
maxSubarraySum([4,2,1,6],1) // 6
maxSubarraySum([4,2,1,6,2],4) // 13
maxSubarraySum([],4) // null
Time Complexity – O(N^2)
#4] Divide and Conquer
This pattern involves dividing a data set into smaller chunks and then repeating a process with a subset of data.
This pattern can tremendously decrease time complexity.
for example:-
Give an array of integers, write a function called search, that accepts a value and returns the index where the value passed to function is located. If the value is 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;
}
//search([1,2,3,4,5,6], 4) //3
//search([1,2,3,4,5,6], 11) // -1
Time Complexity – Log(N)
Recap
- Developing a problem solving approach is incredibly important
- Thinking about code before writing code will always make you solve problems faster
- Be mindful about problem solving patterns
- Using frequency counters, multiple pointers, sliding window, divide & conquer will help you reduce time and space complexity and help solve more challenging problems.
Thank You for reading this post. If you like it please bookmark and share. Will be back with new contents for you. Keep supporting.