Saurabh Kurve

Posted on Sep 4

16 Essential Problem-Solving Patterns

Data Structures and Algorithms (DSA) are crucial for efficient problem-solving. Here are 16 key patterns, with use cases and examples, to help tackle real-world problems. This guide includes concise Java examples to demonstrate each pattern in action.

1. Sliding Window Pattern

Used to track a subset of data that shifts over time, commonly in arrays or strings.

Use Case: Maximum sum of subarrays.
Example: Maximum sum of subarray of size K.

public int maxSubArraySum(int[] arr, int k) {
    int maxSum = 0, windowSum = 0;
    for (int i = 0; i < arr.length; i++) {
        windowSum += arr[i];
        if (i >= k - 1) {
            maxSum = Math.max(maxSum, windowSum);
            windowSum -= arr[i - (k - 1)];
        }
    }
    return maxSum;
}

2. Two Pointer Pattern

Two pointers work towards a solution by converging from different ends of an array.

Use Case: Find pairs in a sorted array.
Example: Find two numbers that sum up to a target.

public int[] twoSum(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;
        else right--;
    }
    return new int[]{};
}

3. Fast & Slow Pointers Pattern

Two pointers move at different speeds to detect cycles in sequences.

Use Case: Detect cycles in linked lists.
Example: Check if a linked list has a cycle.

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

4. Merge Intervals Pattern

This pattern merges overlapping intervals.

Use Case: Scheduling meetings.
Example: Merge overlapping intervals.

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> merged = new ArrayList<>();
    for (int[] interval : intervals) {
        if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
            merged.add(interval);
        } else {
            merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
        }
    }
    return merged.toArray(new int[merged.size()][]);
}

5. Cyclic Sort Pattern

Sort numbers when elements fall within a range.

Use Case: Finding missing numbers.
Example: Find the missing number from 1 to N.

public int findMissingNumber(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        if (nums[i] != i && nums[i] < nums.length) {
            int temp = nums[nums[i]];
            nums[nums[i]] = nums[i];
            nums[i] = temp;
        } else {
            i++;
        }
    }
    for (i = 0; i < nums.length; i++) {
        if (nums[i] != i) return i;
    }
    return nums.length;
}

6. In-Place Reversal of Linked List Pattern

Reverse a linked list in-place.

Use Case: Reversing a sublist of a linked list.
Example: Reverse a linked list.

public ListNode reverseList(ListNode head) {
    ListNode prev = null, current = head;
    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

7. Tree Breadth-First Search (BFS) Pattern

Explore nodes level by level in a tree.

Use Case: Level-order traversal.
Example: Traverse a binary tree level by level.

public List<List<Integer>> bfs(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    if (root != null) queue.add(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> currentLevel = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            currentLevel.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        result.add(currentLevel);
    }
    return result;
}

8. Depth-First Search (DFS) Pattern

Explore as deep as possible along a branch before backtracking.

Use Case: Searching in trees or graphs.
Example: Finding all root-to-leaf paths.

public void dfs(TreeNode node, List<Integer> path, List<List<Integer>> result) {
    if (node == null) return;
    path.add(node.val);
    if (node.left == null && node.right == null) result.add(new ArrayList<>(path));
    dfs(node.left, path, result);
    dfs(node.right, path, result);
    path.remove(path.size() - 1);
}

9. Two Heap Pattern

Use two heaps to maintain dynamic datasets.

Use Case: Finding the median in a data stream.
Example: Find the median of a stream of numbers.

class MedianFinder {
    private PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> high = new PriorityQueue<>();

    public void addNum(int num) {
        low.offer(num);
        high.offer(low.poll());
        if (low.size() < high.size()) low.offer(high.poll());
    }

    public double findMedian() {
        return low.size() > high.size() ? low.peek() : (low.peek() + high.peek()) / 2.0;
    }
}

10. Subsets Pattern

Generate all possible subsets.

Use Case: Combination and permutation problems.
Example: Find all subsets of a set.

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    result.add(new ArrayList<>());
    for (int num : nums) {
        int size = result.size();
        for (int i = 0; i < size; i++) {
            List<Integer> subset = new ArrayList<>(result.get(i));
            subset.add(num);
            result.add(subset);
        }
    }
    return result;
}

11. Modified Binary Search Pattern

Search in a rotated or partially sorted array.

Use Case: Finding an element in rotated arrays.
Example: Search for a target in a rotated sorted array.

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[left] <= nums[mid]) {
            if (target >= nums[left] && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else {
            if (target > nums[mid] && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

12. Bitwise XOR Pattern

Solve problems involving pairs using XOR.

Use Case: Finding unique numbers.
Example: Find the single number in an array.

public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) result ^= num;
    return result;
}

13. Top 'K' Elements Pattern

Use heaps to find the top K elements in a dataset.

Use Case: Finding top K frequent elements.
Example: Find the K most frequent numbers.

public List<Integer> topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> countMap = new HashMap<>();
    for (int num : nums) countMap.put(num, countMap.getOrDefault(num, 0) + 1);
    PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
    for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
        heap.offer(entry);
        if (heap.size() > k) heap.poll();
    }
    return heap.stream().map(Map.Entry::getKey).collect(Collectors.toList());
}

K-Way Merge Pattern Merge multiple sorted arrays efficiently.

Use Case: Merging K sorted lists.
Example: Merge K sorted linked lists.

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
    ListNode dummy = new ListNode(0), tail = dummy;
    for (ListNode list : lists) if (list != null) heap.offer(list);
    while (!heap.isEmpty()) {
        tail.next = heap.poll();
        tail = tail.next;
        if (tail.next != null) heap.offer(tail.next);
    }
    return dummy.next;
}

15. 0/1 Knapsack Dynamic Programming Pattern

Optimize selection under constraints.

Use Case: Resource allocation.
Example: Solve the 0/1 knapsack problem.

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][capacity];
}

16. Topological Sort Graph Pattern

Find a valid task order in Directed Acyclic Graphs (DAG).

Use Case: Course scheduling.
Example: Find the correct order of courses.

public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<Integer>[] graph = new ArrayList[numCourses];
    int[] inDegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) graph[i] = new ArrayList<>();
    for (int[] pre : prerequisites) {
        graph[pre[1]].add(pre[0]);
        inDegree[pre[0]]++;
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) if (inDegree[i] == 0) queue.add(i);
    int[] result = new int[numCourses];
    int idx = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        result[idx++] = course;
        for (int next : graph[course]) {
            inDegree[next]--;
            if (inDegree[next] == 0) queue.add(next);
        }
    }
    return idx == numCourses ? result : new int[0];
}

These 16 problem-solving patterns are crucial for mastering DSA. Each pattern can be applied to a wide range of real-world problems, providing an efficient path to optimal solutions.