How to Approach Algorithm Design
understanding the problem (the most important step)
Before writing a single line of code, you must deeply understand the problem. I’ve seen engineers waste days implementing solutions to the wrong problem.
The problem understanding checklist:
- What are the inputs? (Type, format, constraints, edge cases)
- What are the outputs? (Type, format, constraints)
- What are the constraints? (Time limit, memory limit, input size)
- What are the edge cases? (Empty input, single element, duplicates, negative numbers, etc.)
- Can I restate the problem in my own words?
Example: Understanding the “Two Sum” problem
Problem: Given an array of integers nums and an integer target,
return indices of the two numbers such that they add up to target.
Let's understand:
- Input: nums = [2,7,11,15], target = 9
- Output: [0,1] (because nums[0] + nums[1] = 2 + 7 = 9)
- Constraints: Exactly one solution, can't use same element twice
- Edge cases: What if no solution? (Problem says exactly one solution)
- Can I restate? "Find two numbers that sum to target, return their indices"
The brute force approach (always start here):
// BRUTE FORCE: Try every pair
function twoSumBruteForce(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return null; // No solution found
}
// Analysis:
// Time complexity: O(n²) - nested loops
// Space complexity: O(1) - only using a few variables
Optimizing from brute force:
// OPTIMIZED: Use a hash map to find complement in O(1)
function twoSumOptimized(nums, target) {
const numToIndex = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (numToIndex.has(complement)) {
return [numToIndex.get(complement), i];
}
numToIndex.set(nums[i], i);
}
return null;
}
// Analysis:
// Time complexity: O(n) - single pass
// Space complexity: O(n) - hash map stores n elements
The thought process:
- Start with brute force – Get a working solution
- Identify the bottleneck – The inner loop in brute force is O(n)
- Ask: Can I do better? – Can I find the complement in less than O(n)?
- Data structure choice – Hash map provides O(1) lookup
- Trade-off analysis – We traded space (O(n)) for time (O(n²) → O(n))
The algorithm design process
Algorithm design is iterative. Here’s a systematic process:
Step 1: Understand the problem (covered above)
Step 2: Work through examples by hand
Before coding, work through concrete examples. This helps you:
- Understand the flow of the algorithm
- Identify edge cases
- Verify your understanding
// Problem: Reverse a linked list
// Example: 1 → 2 → 3 → null
// Expected output: 3 → 2 → 1 → null
// Working by hand:
// Initial: prev = null, curr = 1
// Iteration 1: next = 2, 1.next = null, prev = 1, curr = 2
// Iteration 2: next = 3, 2.next = 1, prev = 2, curr = 3
// Iteration 3: next = null, 3.next = 2, prev = 3, curr = null
// Return prev (3 → 2 → 1 → null)
function reverseLinkedList(head) {
let prev = null;
let curr = head;
while (curr !== null) {
const next = curr.next; // Store next
curr.next = prev; // Reverse pointer
prev = curr; // Move prev forward
curr = next; // Move curr forward
}
return prev;
}
Step 3: Write pseudocode
Before writing actual code, write pseudocode to clarify the algorithm.
Algorithm: Find Maximum Subarray (Kadane's Algorithm)
Input: Array of integers
Output: Maximum sum of contiguous subarray
Initialize:
maxSoFar = nums[0]
maxEndingHere = nums[0]
For each element nums[i] from index 1 to n-1:
maxEndingHere = max(nums[i], maxEndingHere + nums[i])
maxSoFar = max(maxSoFar, maxEndingHere)
Return maxSoFar
Step 4: Implement and test
function maxSubArray(nums) {
if (nums.length === 0) return 0;
let maxSoFar = nums[0];
let maxEndingHere = nums[0];
for (let i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
// Test cases:
console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])); // 6 (subarray [4,-1,2,1])
console.log(maxSubArray([1])); // 1
console.log(maxSubArray([5,4,-1,7,8])); // 23
console.log(maxSubArray([-1])); // -1
Step 5: Analyze and optimize
After implementing, analyze:
- Time complexity
- Space complexity
- Edge cases
- Possible optimizations
Pattern recognition in algorithm problems
Many algorithm problems follow common patterns. Recognizing these patterns helps you solve problems faster.
Pattern 1: Sliding Window
Used when: Problem involves contiguous subarray or substring.
// PROBLEM: Maximum sum subarray of size k
// Pattern: Sliding window
function maxSumSubarray(arr, k) {
if (arr.length < k) return null;
// Compute sum of first window
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += arr[i];
}
let maxSum = windowSum;
// Slide window
for (let i = k; i < arr.length; i++) {
windowSum = windowSum - arr[i - k] + arr[i];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
// Time: O(n), Space: O(1)
Pattern 2: Two Pointers
Used when: Array is sorted, or problem involves pairs.
// PROBLEM: Remove duplicates from sorted array
// Pattern: Two pointers (slow/fast)
function removeDuplicates(nums) {
if (nums.length === 0) return 0;
let slow = 0;
for (let fast = 1; fast < nums.length; fast++) {
if (nums[fast] !== nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
// Time: O(n), Space: O(1)
Pattern 3: Fast and Slow Pointers
Used when: Detecting cycles in linked lists.
// PROBLEM: Detect cycle in linked list
// Pattern: Fast and slow pointers
function hasCycle(head) {
if (!head || !head.next) return false;
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next; // Move 1 step
fast = fast.next.next; // Move 2 steps
if (slow === fast) {
return true; // Cycle detected!
}
}
return false; // No cycle
}
Pattern 4: Divide and Conquer
Used when: Problem can be broken into smaller subproblems.
// PROBLEM: Merge sort
// Pattern: Divide and conquer
function mergeSort(arr) {
// Base case
if (arr.length <= 1) return arr;
// Divide
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
// Conquer (merge)
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]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
// Time: O(n log n), Space: O(n)
flowchart TD
A[Problem] --> B{Recognize Pattern?}
B -->|Yes| C[Apply Known Pattern]
B -->|No| D[Try Brute Force]
C --> E[Implement Solution]
D --> F[Analyze Bottleneck]
F --> G{Can Optimize?}
G -->|Yes| H[Choose Better Algorithm]
G -->|No| I[Accept Complexity]
H --> E
I --> E
E --> J[Test & Verify]
style A fill:#e1f5ff
style J fill:#e1f5e1
