This content originally appeared on DEV Community and was authored by kanishkaisuru
This blog series is designed for beginner to intermediate programmers who want to improve their problem-solving skills in algorithmic challenges. By the end of this series, you'll be familiar with several key patterns that can help you approach coding problems more effectively.
Introduction
When tackling coding challenges, recognizing common problem-solving patterns can help you develop efficient solutions quickly. This blog post is designed for beginner to intermediate programmers who are looking to improve their problem-solving skills in algorithmic challenges. Here are 7 fundamental patterns:
- Frequency Counters
- Multiple Pointers
- Sliding Window
- Divide and Conquet
- Dynamic Programming Pattern
- Greedy Pattern
- Backtracking Pattern
along with simple examples to illustrate each.
Today, we'll start with the Frequency Counter Pattern, a fundamental technique that is essential for comparing data and solving problems involving frequencies.
01. Frequency Counters
The frequency counter pattern uses objects or sets to collect frequencies of values. This can often avoid the need for nested loops or O(N^2) operations with arrays or strings.
Example Problem
Write a function named "same" that takes two arrays as input. The function should return "true" if every value in the first array has its corresponding value squared in the second array. Additionally, the frequency of the squared values must match the frequency of the original values.
Example
Input: [1, 2, 3] and [1, 4, 9]
Output: true
Explanation: Each value in the first array has its corresponding squared value in the second array:
1^2 = 1, 2^2 = 4, 3^3 = 9
Input: [1, 2, 3] and [1, 9, 4]
Output: true
Explanation: The second array contains the squared values of the first array, even if they are not in the same order.
Input: [1, 2, 3] and [1, 4, 4]
Output: false
Explanation: The second array does not contain the squared value of 3.
"Basic Solution"
function same(arr1, arr2){
if(arr1.length !== arr2.length){
return false;
}
for(let i=0; i < arr1.length; i++){
let correctIndex = arr2.indexOf(arr1[i] ** 2)
if(correctIndex === -1){
return false;
}
arr2.splice(correctIndex,1);
}
return true;
}
Most developers use this solution without thinking about this pattern.
Time Complexity - O(N^2)
Solution using Frequency Counter pattern
Lets See Step by Step
I. Check Lengths: First, the function checks if the lengths of the two arrays are different. If they are, it returns false because they cannot have the same frequency of values.
function same(arr1, arr2){
if(arr1.length !== arr2.length){
return false;
}
}
II. Count Frequencies: The function then counts the frequency of each value in the first array and stores it in frequency_counter1. Similarly, it counts the frequency of each value in the second array and stores it in frequency_counter2.
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, frequencyCounter2)
}
When you put this example
same([1,2,3,2], [9,1,4,4])
result is :
We can get each value frequency like the above.
NOTE : Using two separate loops instead of a nested loop reduces the time complexity of quadratic 𝑂(N^2) to linear O(N). This makes the algorithm more efficient, especially for large inputs, as the number of operations is significantly lower.
III. Compare Frequencies: Finally, the function compares the frequency of each value in frequency_counter1 with the frequency of its squared value in frequency_counter2. If any value does not match, the function returns false. and Return True: If all values match, the function returns true.
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, frequencyCounter2)
for (let key in frequencyCounter1) {
if (!(key ** 2 in frequencyCounter2)) {
return false
}
if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
return false
}
}
return true
}
Time Complexity - O(N)
Conclusion
The Frequency Counter Pattern is a powerful tool for solving problems that involve comparing data or counting frequencies. By using this pattern, you can tackle a wide range of algorithmic challenges more effectively. Practice using this pattern with different problems to enhance your problem-solving skills.
Stay tuned for the next post in our series, where we'll explore the Multiple Pointers Pattern. If you have any questions or examples to share, feel free to leave a comment below!
This content originally appeared on DEV Community and was authored by kanishkaisuru
kanishkaisuru | Sciencx (2024-08-04T09:07:15+00:00) Problem Solving Patterns. Retrieved from https://www.scien.cx/2024/08/04/problem-solving-patterns/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.