Algorithm design patterns are reusable solutions to common computational problems. Understanding these patterns is crucial for acing technical interviews and becoming a better problem solver. Let's dive into the three most important patterns with practical JavaScript implementations.
Greedy Algorithms: Making Locally Optimal Choices
Greedy algorithms make the locally optimal choice at each step with the hope of finding a global optimum. They're simple, fast, and work well for certain problems.
When to Use Greedy Algorithms
- Greedy Choice Property: Local optimal choices lead to global optimum
- Optimal Substructure: Optimal solution contains optimal solutions to subproblems
- No Backtracking: Once a choice is made, it's not revisited
Classic Greedy Problems
1. Jump Game
javascript
function canJump(nums) {
let maxReach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) return true;
}
return false;
}
// Usage
console.log(canJump([2, 3, 1, 1, 4])); // true
console.log(canJump([3, 2, 1, 0, 4])); // false2. Minimum Number of Arrows to Burst Balloons
javascript
function findMinArrowShots(points) {
if (points.length === 0) return 0;
// Sort by end coordinate
points.sort((a, b) => a[1] - b[1]);
let arrows = 1;
let end = points[0][1];
for (let i = 1; i < points.length; i++) {
if (points[i][0] > end) {
arrows++;
end = points[i][1];
}
}
return arrows;
}
// Usage
console.log(findMinArrowShots([[10,16],[2,8],[1,6],[7,12]])); // 23. Partition Labels
javascript
function partitionLabels(s) {
const lastOccurrence = {};
// Store last occurrence of each character
for (let i = 0; i < s.length; i++) {
lastOccurrence[s[i]] = i;
}
const result = [];
let start = 0;
let end = 0;
for (let i = 0; i < s.length; i++) {
end = Math.max(end, lastOccurrence[s[i]]);
if (i === end) {
result.push(end - start + 1);
start = i + 1;
}
}
return result;
}
// Usage
console.log(partitionLabels("ababcbacadefegdehijhklij")); // [9,7,8]4. Task Scheduler
javascript
function leastInterval(tasks, n) {
const freq = {};
let maxFreq = 0;
let maxCount = 0;
// Count frequency and find most frequent task
for (const task of tasks) {
freq[task] = (freq[task] || 0) + 1;
if (freq[task] > maxFreq) {
maxFreq = freq[task];
maxCount = 1;
} else if (freq[task] === maxFreq) {
maxCount++;
}
}
// Calculate minimum intervals needed
const partCount = Math.max(0, maxFreq - 1);
const partLength = n - (maxCount - 1);
const emptySlots = partCount * partLength;
const availableTasks = tasks.length - maxFreq * maxCount;
const idles = Math.max(0, emptySlots - availableTasks);
return tasks.length + idles;
}
// Usage
console.log(leastInterval(["A","A","A","B","B","B"], 2)); // 8Greedy Pattern: Interval Problems
javascript
// Generic interval scheduling template
function intervalScheduling(intervals) {
if (intervals.length === 0) return 0;
// Sort by end time
intervals.sort((a, b) => a.end - b.end);
let count = 1;
let end = intervals[0].end;
for (let i = 1; i < intervals.length; i++) {
if (intervals[i].start >= end) {
count++;
end = intervals[i].end;
}
}
return count;
}Dynamic Programming: Breaking Down Complex Problems
Dynamic programming (DP) solves complex problems by breaking them down into simpler subproblems and storing their solutions to avoid redundant calculations.
DP Core Concepts
- 1Overlapping Subproblems: Same subproblems solved multiple times
- 2Optimal Substructure: Optimal solution can be constructed from optimal solutions of subproblems
- 3Memoization: Top-down approach with caching
- 4Tabulation: Bottom-up approach with table filling
Classic DP Problems
1. Fibonacci Sequence (Memoization)
javascript
// Top-down with memoization
function fibonacciMemo(n, memo = {}) {
if (n in memo) return memo[n];
if (n <= 1) return n;
memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
return memo[n];
}
// Bottom-up with tabulation
function fibonacciTab(n) {
if (n <= 1) return n;
const dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// Space optimized
function fibonacciOptimized(n) {
if (n <= 1) return n;
let prev = 0;
let curr = 1;
for (let i = 2; i <= n; i++) {
[prev, curr] = [curr, prev + curr];
}
return curr;
}2. Climbing Stairs
function climbStairs(n) {
if (n <= 2) return n;
let prev = 1;
let curr = 2;
for (let i = 3; i <= n; i++) {
[prev, curr] = [curr, prev + curr];
}
return curr;
}
// With different step options
function climbStairsK(n, k) {
if (n <= 1) return 1;
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
for (let j = 1; j <= k && j <= i; j++) {
dp[i] += dp[i - j];
}
}
return dp[n];
}3. Longest Increasing Subsequence
javascript
// O(n²) approach
function lengthOfLIS(nums) {
if (nums.length === 0) return 0;
const dp = new Array(nums.length).fill(1);
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
}
// O(n log n) approach with binary search
function lengthOfLISOptimized(nums) {
const tails = [];
for (const num of nums) {
let left = 0;
let right = tails.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (tails[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
if (left === tails.length) {
tails.push(num);
} else {
tails[left] = num;
}
}
return tails.length;
}4. Longest Common Subsequence
javascript
function longestCommonSubsequence(text1, text2) {
const m = text1.length;
const n = text2.length;
// Create 2D DP table
const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
// Reconstruct the actual LCS
function longestCommonSubsequenceWithResult(text1, text2) {
const m = text1.length;
const n = text2.length;
const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Reconstruct LCS
const lcs = [];
let i = m, j = n;
while (i > 0 && j > 0) {
if (text1[i - 1] === text2[j - 1]) {
lcs.unshift(text1[i - 1]);
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return lcs.join('');
}5. Coin Change
javascript
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
// Usage
console.log(coinChange([1, 2, 5], 11)); // 3 (5 + 5 + 1)
console.log(coinChange([2], 3)); // -16. Edit Distance
javascript
function minDistance(word1, word2) {
const m = word1.length;
const n = word2.length;
const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
// Initialize base cases
for (let i = 0; i <= m; i++) dp[i][0] = i;
for (let j = 0; j <= n; j++) dp[0][j] = j;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(
dp[i - 1][j], // Delete
dp[i][j - 1], // Insert
dp[i - 1][j - 1] // Replace
);
}
}
}
return dp[m][n];
}DP Pattern: Knapsack Problems
javascript
// 0/1 Knapsack
function knapsack(weights, values, capacity) {
const n = weights.length;
const dp = Array(n + 1).fill(null).map(() => Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(
dp[i - 1][w],
values[i - 1] + dp[i - 1][w - weights[i - 1]]
);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
// Space-optimized version
function knapsackOptimized(weights, values, capacity) {
const dp = new Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
}
}
return dp[capacity];
}Divide & Conquer: Breaking Problems Down
Divide and conquer algorithms work by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly.
Key Components
- 1Divide: Break problem into smaller subproblems
- 2Conquer: Solve subproblems recursively
- 3Combine: Combine solutions to solve original problem
Classic Divide & Conquer Problems
1. Merge Sort
javascript
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return [...result, ...left.slice(i), ...right.slice(j)];
}
// In-place version to save space
function mergeSortInPlace(arr, left = 0, right = arr.length - 1) {
if (left < right) {
const mid = Math.floor((left + right) / 2);
mergeSortInPlace(arr, left, mid);
mergeSortInPlace(arr, mid + 1, right);
mergeInPlace(arr, left, mid, right);
}
return arr;
}2. Quick Sort
javascript
function quickSort(arr, left = 0, right = arr.length - 1) {
if (left < right) {
const pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
return arr;
}
function partition(arr, left, right) {
const pivot = arr[right];
let i = left - 1;
for (let j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
return i + 1;
}3. Maximum Subarray Sum (Kadane's Algorithm)
javascript
function maxSubArray(nums) {
let maxSum = nums[0];
let currentSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
// Divide and conquer version
function maxSubArrayDivideConquer(nums, left = 0, right = nums.length - 1) {
if (left === right) return nums[left];
const mid = Math.floor((left + right) / 2);
const leftMax = maxSubArrayDivideConquer(nums, left, mid);
const rightMax = maxSubArrayDivideConquer(nums, mid + 1, right);
// Find max crossing sum
let leftCrossMax = -Infinity;
let sum = 0;
for (let i = mid; i >= left; i--) {
sum += nums[i];
leftCrossMax = Math.max(leftCrossMax, sum);
}
let rightCrossMax = -Infinity;
sum = 0;
for (let i = mid + 1; i <= right; i++) {
sum += nums[i];
rightCrossMax = Math.max(rightCrossMax, sum);
}
const crossMax = leftCrossMax + rightCrossMax;
return Math.max(leftMax, rightMax, crossMax);
}4. Binary Search
javascript
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;
}
// Find first occurrence in sorted array with duplicates
function findFirst(arr, target) {
let left = 0;
let right = arr.length - 1;
let result = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
result = mid;
right = mid - 1; // Continue searching left
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
// Find element in rotated sorted array
function searchRotated(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;
// Check if left half is sorted
if (arr[left] <= arr[mid]) {
if (arr[left] <= target && target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// Right half is sorted
else {
if (arr[mid] < target && target <= arr[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}Comparison of Approaches
| Pattern | Time Complexity | Space Complexity | When to Use | |---------|----------------|------------------|-------------| | Greedy | O(n log n) | O(1) | Local optimum leads to global optimum | | DP (Memoization) | O(n) | O(n) | Overlapping subproblems | | DP (Tabulation) | O(n²) | O(n²) | Optimal substructure | | Divide & Conquer | O(n log n) | O(log n) | Problem can be divided |
Problem-Solving Strategy
- 1Identify the Pattern
- Greedy: Look for optimal substructure - DP: Look for overlapping subproblems - Divide & Conquer: Look for independent subproblems
- 1Start with Brute Force
- Understand the problem thoroughly - Identify inefficiencies
- 1Optimize Step by Step
- Add memoization for recursive solutions - Use tabulation for bottom-up approach - Optimize space complexity
- 1Test Edge Cases
- Empty input - Single element - All same elements - Large inputs
Practice Problems by Pattern
Greedy:
- Jump Game II
- Gas Station
- Candy
- Partition Equal Subset Sum
Dynamic Programming:
- House Robber
- Decode Ways
- Unique Paths
- Perfect Squares
Divide & Conquer:
- Convert Sorted Array to BST
- Kth Largest Element
- Pow(x, n)
- Search in Rotated Sorted Array
Interview Tips
- 1State the Approach: Explain which pattern you're using and why
- 2Start Simple: Begin with brute force, then optimize
- 3Trace Examples: Walk through small examples manually
- 4Discuss Trade-offs: Compare time and space complexity
- 5Code Cleanly: Use meaningful variable names and comments
Mastering these patterns takes practice. Start with easy problems and gradually work your way up to harder ones. Remember, recognition comes with experience!