DEV Community: kanishkaisuru

Problem Solving Patterns (Part 4): Divide and Conquer

kanishkaisuru — Wed, 01 Jan 2025 02:23:52 +0000

Welcome Back!

Welcome back to the "Problem Solving Patterns" series! In this series, we explore different patterns to enhance your problem-solving skills and algorithmic thinking. Here’s a quick recap of the patterns we’ve covered so far:

Recap

Part 1: Frequency Counter Pattern - Read here

Part 2: Multiple Pointers Pattern - Read here

Part 3: Sliding Window Pattern - Read here

If you missed these posts, check them out to build a strong foundation for the series!

Key Concepts of Divide and Conquer

Divide: Split the problem into smaller sub-problems that are easier to solve.

Conquer: Solve each sub-problem recursively. If the sub-problems are small enough, solve them directly.

Combine: Merge the solutions of the sub-problems to solve the original problem.

This approach works best for problems that can be recursively divided and where combining the solutions is relatively straightforward.

Common Examples of Divide and Conquer

Binary Search
Merge Sort
Quick Sort

Finding the maximum and minimum in an array

Example: Binary Search

Let’s implement a simple binary search algorithm using the Divide and Conquer pattern. Binary search is used to find the position of a target value within a sorted array.

Problem Statement

Given a sorted array and a target value, return the index of the target value. If the target does not exist, return -1.

Steps to Solve

Divide the array into two halves by calculating the middle index.
Compare the target value with the middle element:
- If the target is equal to the middle element, return the index.
- If the target is less than the middle element, repeat the search on the left half.
- If the target is greater than the middle element, repeat the search on the right half.

Conquer by recursively solving the smaller sub-problems until the target is found or the array is fully traversed.

Implementation

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1; // Target not found
}

// Example Usage
const sortedArray = [1, 3, 5, 7, 9, 11];
const target = 5;
const result = binarySearch(sortedArray, target);
console.log(result); // Output: 2

Explanation

Initial Step: The array is divided into two halves.

Recursive Check: The middle element is compared with the target value.

Combine: The result is obtained by determining whether the target exists in the left or right sub-array.

Why Use Divide and Conquer?

Efficiency: It reduces the problem size exponentially at each step.

Scalability: Works well for large datasets.

Simplicity: Many complex problems can be broken down into smaller, manageable parts.

Applications in Real Life

Sorting Algorithms: Merge Sort and Quick Sort use Divide and Conquer to efficiently sort data.

Searching Algorithms: Binary Search significantly reduces the time complexity of searching operations.

Optimization Problems: Dynamic programming often builds upon the Divide and Conquer principle.

Practice Problem

Try implementing a mergeSort algorithm using the Divide and Conquer pattern. Here’s a quick outline:

Divide the array into two halves.
Recursively sort each half.
Merge the sorted halves into a single sorted array.

Stay tuned for the next post in this series, where we’ll dive into the Dynamic Programming Pattern. It’s a game-changer for solving optimization problems efficiently!

The Divide and Conquer pattern is a cornerstone of algorithm design. By mastering it, you’ll gain the ability to tackle complex problems more efficiently and with greater confidence.

Happy coding! Let me know your thoughts and experiences with this pattern in the comments below.

Problem Solving Patterns (Part 3)

kanishkaisuru — Sun, 01 Sep 2024 06:39:44 +0000

Welcome Back to the Problem Solving Patterns Series

In our journey to become more efficient problem solvers, we've already explored two fundamental patterns: Frequency Counters and Multiple Pointers. These patterns have given us tools to approach and solve problems with greater clarity and efficiency.

Recap of Previous Patterns

Frequency Counters (Part1): We learned how to use objects or sets to keep track of frequencies in problems where counting or checking for uniqueness is crucial.

Multiple Pointers (Part2): We explored how using pointers to represent different positions in a data structure can help solve problems that involve sequences or pairs, often in a more space-efficient way.

Introducing the Sliding Window Pattern

Now, let's move on to the third pattern in our series: the Sliding Window. This pattern is particularly useful for solving problems involving a contiguous subset of elements in an array or string. Whether it's finding the maximum sum of a subarray of fixed size or checking for the existence of a specific sequence, the Sliding Window technique can significantly reduce time complexity compared to a brute-force approach.

Deep Dive into the Sliding Window Pattern

The Sliding Window pattern is an incredibly efficient technique used when dealing with problems involving a subset of data elements that are contiguous in nature, such as subarrays or substrings. Instead of recalculating for each possible subset, we "slide" a window across the data to find our solution in a more optimized way.

Example Problem: Maximum Sum Subarray of Size K

Problem Statement: Given an array of integers and a number k, find the maximum sum of a subarray of size k.

Example:

Input: arr = [2, 1, 5, 1, 3, 2], k = 3
Output: 9
Explanation: Subarray with maximum sum is [5, 1, 3].

Basic Solution

function maxSubArraySum(arr, num){
    if(num > arr.length){
        return null;
    }

    var max = -Infinity;

    for (let i = 0; i < arr.length - num + 1; i++) {
        temp = 0;
        for (let j = 0; j < num; j++) {
            temp += arr[i+j]
        }
        if(temp > max){
            max = temp
        }
    }
    return max
}

Time Complexity - O(N^2)

Step-by-Step Guide using Sliding Window Pattern:

Understanding the Brute Force Approach:

In a brute-force solution, we would calculate the sum of every possible subarray of size k and keep track of the maximum sum.
This approach has a time complexity of O(n * k), where n is the length of the array. For large arrays, this becomes inefficient.
Space Complexity: O(1) since we only use a few extra variables for calculation.

Introducing the Sliding Window Approach:

Instead of recalculating the sum for each subarray, we maintain a running sum of the current window of size k.
As we slide the window by one element, we subtract the element that is leaving the window and add the element that is entering the window.

Implementing the Sliding Window Approach:

Let’s walk through the problem step by step in JavaScript.

function maxSubarraySum(arr, k) {
    let maxSum = 0;
    let windowSum = 0;
    let windowStart = 0;

    for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
        windowSum += arr[windowEnd];                // Add the next element to the window

        // Slide the window, we don't need to slide if we've not hit the required window size of 'k'
        if (windowEnd >= k - 1) {
            maxSum = Math.max(maxSum, windowSum);  // Update the maximum sum
            windowSum -= arr[windowStart];         // Subtract the element going out
            windowStart += 1;                      // Slide the window ahead
        }
    }

    return maxSum;
}

// Test the function
const arr = [2, 1, 5, 1, 3, 2];
const k = 3;
console.log(maxSubarraySum(arr, k));              // Output: 9

Breaking Down the Code:

Initialize Variables:
- maxSum: Tracks the maximum sum encountered.
- windowSum: Stores the sum of the current window.
- windowStart: The index where the window starts.
Sliding the Window:
- We iterate over the array, adding each element to the windowSum.
- Once the window reaches size k, we check if the current windowSum. is greater than maxSum and update maxSum accordingly.
- We then slide the window by subtracting the element that is going out and incrementing windowStart.

Conclusion

The Sliding Window pattern is a versatile and powerful technique that can be applied to a variety of problems involving contiguous subarrays or substrings. By understanding and mastering this pattern, you'll be better equipped to tackle more complex challenges efficiently.

Stay tuned! In the next chapter of this series, we will dive into the Divide and Conquer pattern, a fundamental strategy that breaks down complex problems into simpler sub-problems to solve them more effectively.

Problem Solving Patterns (Part 2)

kanishkaisuru — Sun, 18 Aug 2024 11:59:32 +0000

Welcome back to our blog series on problem solving in modern software engineering!

In Part 1, we explored the Frequency Counter Pattern, a powerful technique for optimizing algorithms by efficiently counting the frequency of elements. If you missed it or want a quick refresher, feel free to check it out before continuing.

In this part, we’ll be diving into another essential pattern: the Multipointer Pattern. This pattern is invaluable when dealing with scenarios where multiple elements need to be compared, searched, or traversed simultaneously. Let’s explore how it works and where you can apply it to improve your code’s efficiency.

02. Multipointer Pattern

The Multipointer Pattern is a technique used in algorithm design where multiple pointers (or iterators) are employed to traverse data structures like arrays or linked lists. Instead of relying on a single pointer or loop, this pattern uses two or more pointers that move through the data at different speeds or from different starting points.

Example Problem

Write a function called sumZero that accepts a sorted array of integers. The function should find the first pair where the sum is zero. If such a pair exists, return an array that includes both values; otherwise, return undefined.

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

Basic Solution

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) {
                console.log(arr[i] + arr[j])
                return [arr[i], arr[j]]
            }
        }
    }
}

Time Complexity - O(N^2)

Solution using Multipointer Pattern

step 1: Understand the problem
We need to find two numbers in a **sorted array that add up to zero. Since the array is sorted, we can take advantage of this order to find the solution more efficiently.

step 2: Initialize Two Pointers
Set up two pointers: one (left) starting at the beginning of the array, and the other (right) starting at the end.

Example:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5

Step 3: Calculate the Sum of the Values at the Pointers
Add the values at the left and right pointers to get the sum

Sum = -4 + 5 = 1

Step 4: Compare the Sum with Zero

If the sum is greater than zero: Move the right pointer one step to the left to decrease the sum.

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

If the sum is less than zero: Move the left pointer one step to the right to increase the sum.

New Sum = -4 + 2 = -2
Sum is -2 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -3
Right Pointer (R): 2

Step 5: Repeat the Process
Continue moving the pointers and calculating the sum until they meet or a pair is found.

New Sum = -3 + 2 = -1
Sum is -1 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -2
Right Pointer (R): 2

The sum is zero, so the function returns [-2, 2].

If the loop completes without finding such a pair, return undefined.

Final Code

function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left < right) {                // Continue until the pointers meet
    const sum = arr[left] + arr[right]; // Calculate the sum of the values at the pointers

    if (sum === 0) {                    // If the sum is zero, return the pair
      return [arr[left], arr[right]];
    } else if (sum > 0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left++;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}

NOTE:
Time Complexity: O(n) – The function is efficient and scales linearly with the size of the array.
Space Complexity: O(1) – The function uses a minimal amount of additional memory.

Conclusion

The Multipointer Pattern is a powerful technique for solving problems that involve searching, comparing, or manipulating elements in a sorted data structure. By using multiple pointers that move towards each other, we can significantly improve the efficiency of algorithms, reducing time complexity from O(n²) to O(n) in many cases. This pattern is versatile and can be applied to a wide range of problems, making it an essential strategy for optimizing performance in your code.

Stay tuned for our next post, where we’ll dive into the Sliding Window Pattern another essential tool for tackling problems involving dynamic data segments. It’s an incredibly useful pattern that can help you solve even more complex challenges with ease!

Problem Solving Patterns (Part 1)

kanishkaisuru — Sun, 04 Aug 2024 09:07:15 +0000

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 Conquer
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!