Algorithm Solving Strategies
If you read my previous blog regarding Big O Notation, you may remember that an algorithm is defined as “a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation ” (Wikipedia). Algorithms are important for all software engineers to study as they can help us solve problems we may encounter in the work place.
You may be reading this blog post because you are currently in your job search. If that is the case, LeetCode and HackerRank both have hundreds of practice algorithm problems for job seekers to leverage. The purpose of this blog is to arm you with a few strategies to help tackle these types of problems and those you may encounter in an interview and on the job.
The three strategies to be discussed in this blog include the following:
- Frequency Counter
- Multiple Pointers
- Sliding Window
These strategies come from Colt Steele’s JavaScript Algorithms and Data Structures Masterclass Udemy course, which I highly recommend. The examples primarily come from LeetCode.
Frequency Counter
The frequency counter approach can be applied to algorithms where you need to collect values or check the number of occurrences of a value. This strategy utilizes objects or sets and avoids the need for nested loops (Steele). Moreover, frequency counters improve our solutions’ time complexity from O(n²), if using a nested loops, to O(n).
Now to show the frequency counter strategy in practice, let’s look at an example from Leetcode.
Source: https://leetcode.com/problems/valid-anagram/Problem:Given two strings s and t , write a function to determine if t is an anagram of s. Test Case #1 Input: s = "tennis", t = "entsno"
Output: false Test Case #2 Input: s = "tan", t = "nat"
Output: true
In this example, we will use the frequency counter method to check if each string has all the same letters and those letters appear the same number of times. If both of these checks are true, we know that s and t are anagrams.
Solution:var isAnagram = function(s, t) {
// if string lengths are different, it's impossible for string t
// to be an anagram
if (s.length !== t.length) {
return false;
} const lookup = {}; for (let i = 0; i < s.length; i++) {
let letter = s[i];
// if letter exists, increment by 1, otherwise set to 1
lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
}
console.log(lookup) for (let i = 0; i < t.length; i++) {
let letter = t[i];
// if letter not found or letter value is zero then string t is
// not an anagram of string s
if (!lookup[letter]) {
return false;
} else {
lookup[letter] -= 1;
}
console.log(lookup)
} return true;
};isAnagram("tennis", "entsno")
isAnagram("tan", "nat")Test Case #1 Output: // lookup object after looping over s string
{ t: 1, e: 1, n: 2, i: 1, s: 1 }// lookup object decrementing by matching letters in t string
// after each loop
{ t: 1, e: 0, n: 2, i: 1, s: 1 }
{ t: 1, e: 0, n: 1, i: 1, s: 1 }
{ t: 0, e: 0, n: 1, i: 1, s: 1 }
{ t: 0, e: 0, n: 1, i: 1, s: 0 }
{ t: 0, e: 0, n: 0, i: 1, s: 0 }falseTest Case #2 Output:// lookup object after looping over s string
{ t: 1, a: 1, n: 1 }// lookup object decrementing by matching letters in t string
// after each loop
{ t: 1, a: 1, n: 0 }
{ t: 1, a: 0, n: 0 }
{ t: 0, a: 0, n: 0 }true
In the solution above, we first check to see that the strings are the same length. We have this check because if the strings are different lengths, we know they cannot be an anagram and therefore don’t need to work through any additional code. The first loop in the solution creates a summary of all the letters and their frequencies in string s into an object called lookup. The second loop checks that the letter in string t is present in lookup and the value is greater than 0. If these conditions are both true, then the frequency of the letter in lookup is decremented by 1; if not, we know string t is not an anagram of string s. If the second loop iterates through the final letter in string t, then we return true as the frequencies, and all letters in lookup will be 0.
Multiple Pointers
The multiple pointers strategy is typically used on linear structures (i.e., arrays, strings, and linked lists). The types of problems where multiple pointers are useful are when you need to search for a value or a pair of values that meet a certain condition. Colt Steele describes the process of how this works as follows, “Creating pointers or values that correspond to an index or position and move towards the beginning, end or middle based on a certain condition” (Steele). Steele also goes on to mention that multiple pointer solutions have efficient time complexities O(n) and minimal space complexity O(1).
Now to show the multiple pointers strategy in practice, let’s look at an example.
Source: Colt Steele's JavaScript Algorithms and Data Structures Masterclass Course on UdemyProblem: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 exist.Test Case #1
Input = [-3, -2, -1, 0, 1, 2, 3]
Output = [-3, 3]Test Case #2
Input = [-2, 0, 1, 3]
Output = undefinedTest Case #3
Input = [1, 2, 3]
Output = undefined
In this example, we will use the multiple pointers strategy to see if an array contains two values that when added together equal 0. Since our array is sorted, we can place one pointer at the beginning and one at the end of the array. Then return the values at the two pointers if they sum to 0.
Solution:var sumZero = function(arr) {
let pointer1 = 0
let pointer2 = arr.length - 1;
// Needs to be less than instead of less than or equal to
// to prevent a single 0 creating a false positive.
while(pointer1 < pointer2) {
let sum = arr[pointer1] + arr[pointer2];
console.log(sum, arr[pointer1], arr[pointer2])
if(sum === 0) {
return [arr[pointer1], arr[pointer2]];
} else if(sum > 0) {
pointer2--;
} else {
pointer1++;
}
}
};sumZero([-3, -2, -1, 0, 1, 2, 3])
sumZero([-2, 0, 1, 3])
sumZero([1, 2, 3])Test Case #1 Output:// console.log of sum, value at pointer1, and value at pointer2
0 -3 3// result
[ -3, 3 ]Test Case #2 Output:// console.log of sum, value at pointer1, and value at pointer2
1 -2 3
-1 -2 1
1 0 1// result
undefinedTest Case #3 Output:// console.log of sum, value at pointer1, and value at pointer2
4 1 3
3 1 2// result
undefined
In the solution above, we first set the position of pointer1 to the beginning of the array and pointer2 to the end of the array. Then we see what the sum of the values at pointer1 and pointer2 are equal to. If the sum is negative, we need to move pointer1 one value to the right. If the sum is positive, we need to move pointer2 one value to the left. If the sum is 0, then we have found the pair we were looking for and return the values. We continue this pattern until we have either found a pair that sums to 0 or reach the final iteration of the while loop where pointer1’s position is less than the position of pointer2 and return undefined.
Additional Examples:
Source: https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/727/Problem: Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Solution:var removeDuplicates = function(nums) {
if (nums.length === 0) {
return 0
}
let pointer1 = 0for (let pointer2 = 1; pointer2 < nums.length; pointer2++) {
if (nums[pointer1] !== nums[pointer2]) {
pointer1++;
nums[pointer1] = nums[pointer2]
}
}
return pointer1 + 1
};Source: https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/567/Problem: Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. Input: [0,1,0,3,12]
Output: [1,3,12,0,0]Solution:var moveZeroes = function(nums) { let pointer1 = 0
for(let pointer2 = 0; pointer2 < nums.length; pointer2++) {
if(nums[pointer2] !== 0) {
let temp = nums[pointer1]
nums[pointer1] = nums[pointer2]
nums[pointer2] = temp
pointer1++
}
}
return nums
};moveZeroes([0,1,0,3,12])Video Explanation: https://www.youtube.com/watch?v=0rPuILjoVsg
Sliding Window
The last strategy that we will discuss in this blog is the sliding window. Similar to the multiple pointers strategy, sliding window is typically used on linear structures (i.e., arrays and strings). The types of problems where a sliding window is useful are when you need to find/keep track of a subset of the input that follows some pattern. Colt Steele describes the process of how this works as follows, “This pattern involves creating a window which can either be 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)” (Steele). Also, using a sliding window is preferable as it has an O(n) time complexity.
Now to show the sliding window strategy in practice, let’s look at an example.
Source: Colt Steele's JavaScript Algorithms and Data Structures Masterclass Course on UdemyProblem: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.Test Case #1
Input = [1,2,5,2,8,1,5], n = 2
Output = 10Test Case #2
Input = [1,2,5,2,8,1,5], n = 4
Output = 17
In this example, we will use the sliding window strategy to find the largest sum from a subset of the data. We will do this by creating a window, the size of which is determined by n. Next, we slide the window 1 position to the right and determine if this sum is larger than the previous sums. Then once the final window is summed, we will will return the largest sum.
Solution:function maxSubarraySum(arr, n){
let maxSum = 0;
let tempSum = 0;
if (arr.length < n) return null;
for (let i = 0; i < n; i++) {
maxSum += arr[i];
}
tempSum = maxSum;
for (let i = n; i < arr.length; i++) {
tempSum = tempSum - arr[i - n] + arr[i];
maxSum = Math.max(maxSum, tempSum);
}
return maxSum;
}maxSubarraySum([1,2,5,2,8,1,5],2)
maxSubarraySum([1,2,5,2,8,1,5],4)Test Case #1 Output:// the initial maxSum
3// sliding window, tempSum on left and previous maxSum on right
7 3
7 7
10 7
9 10
6 10// result
10Test Case #2 Output:// the initial maxSum
10// sliding window, tempSum on left and previous maxSum on right
17 10
16 17
16 17// result
17
In the solution above, we first declare two variables, maxSum and tempSum, and set them equal to 0. Then we set an edge case to return null if n, the size of the window, is greater than the array. Next, we find the summation of the first window by looping over only the specified number of n numbers and adding each number to the maxSum variable. Then we set our tempSum variable to the value of maxSum; the temp sum will be our sliding window. Then in our second loop, we find the value of the next window by subtracting the first value from our initial window (arr[0]) and adding the next value in the array that was not in our initial window (i.e., arr[3] if the first window contained arr[0],arr[1],arr[2]) and setting this value to the value of tempSum. Then we use set the value of maxSum equal to the larger of tempSum and the previous maxSum. We continue this process until we reach the end of the array and return maxSum
Thank you for taking the time to learn more about algorithm solving strategies. I hope this blog has equipped you with a few strategies to help you in your job search and/or workplace.
Resources
Steele, C. (n.d.). JavaScript Algorithms and Data Structures Masterclass. Online Course.
Algorithm. (2020, October 07). Retrieved October 10, 2020, from https://en.wikipedia.org/wiki/Algorithm
