PROBLEM PATTERNS - rs-hash/Senior GitHub Wiki

1. Frequency Counter

A technique that uses a hash table or an object to collect the frequencies of elements. This is particularly useful for problems involving comparisons of frequency and counts.

Use Case:

  • Counting the frequency of characters in a string.
  • Checking if two arrays have the same frequency of elements.

Common Problems:

  • Anagram Check: Determine if two strings are anagrams.
  • Frequency of Elements: Find the most frequent element in an array.
  • Unique Characters: Check if a string has all unique characters.

FREQUENCY-COUNTER-PATTERN

2. Multiple Pointers

An approach where two or more pointers are used to traverse the data structure, typically from different ends or at different speeds.

Use Case:

  • Finding pairs in sorted arrays.
  • Comparing elements in sequences.

Common Problems:

  • Two Sum II: Find indices of two numbers such that they add up to a target.
  • Palindrome Check: Check if a string is a palindrome.
  • Remove Duplicates: Remove duplicates from a sorted array in-place.

MULTIPLE-POINTERS-PATTERN

3. Sliding Window

A technique that involves a window (subarray or substring) that slides over the data structure to solve problems involving contiguous sequences.

Use Case:

  • Finding subarrays or substrings that meet a certain condition.
  • Optimizing the sum or length of subarrays.

Common Problems:

  • Maximum Sum Subarray of Size K: Find the maximum sum of any contiguous subarray of size K.
  • Smallest Subarray with a Given Sum: Find the smallest contiguous subarray with a sum greater than or equal to the target.
  • Longest Substring Without Repeating Characters: Find the longest substring with all distinct characters.

4. Divide and Conquer

A technique that divides the problem into smaller subproblems, solves each subproblem recursively, and then combines their solutions.

Use Case:

  • Sorting algorithms.
  • Searching algorithms.

Common Problems:

  • Merge Sort: Sort an array using merge sort.
  • Quick Sort: Sort an array using quick sort.
  • Binary Search: Search for an element in a sorted array

5. Dynamic Programming

A method for solving complex problems by breaking them down into simpler subproblems and storing the results of subproblems to avoid redundant computations.

Use Case:

  • Optimization problems.
  • Problems with overlapping subproblems and optimal substructure.

Common Problems:

  • Fibonacci Sequence: Calculate the nth Fibonacci number.
  • 0/1 Knapsack Problem: Determine the maximum value that can be obtained from a set of items with given weights and values.
  • Longest Increasing Subsequence: Find the length of the longest increasing subsequence in an array.

6. Greedy Algorithm

An approach that makes a series of choices, each of which is locally optimal, with the hope that the global solution is optimal.

Use Case:

  • Problems where local optimization leads to a global solution.
  • Scheduling problems.

Common Problems:

  • Activity Selection: Select the maximum number of activities that don't overlap.
  • Fractional Knapsack Problem: Maximize the total value in the knapsack.
  • Minimum Spanning Tree: Find the minimum spanning tree in a graph using Kruskal's or Prim's algorithm.

7. Backtracking

A technique for solving problems incrementally by trying partial solutions and then backtracking if the partial solution cannot be extended to a complete solution.

Use Case:

  • Combinatorial problems.
  • Constraint satisfaction problems.

Common Problems:

  • N-Queens Problem: Place N queens on an N x N chessboard such that no two queens threaten each other.
  • Sudoku Solver: Solve a Sudoku puzzle.
  • Permutations and Combinations: Generate all permutations or combinations of a set.