DSA

Coding Patterns

Rohit Kumar

•

19 April 2025

•

18 mins

Coding Patterns

Coding Patterns: ace your DSA Interviews

Introduction

Coding patterns are a set of techniques or strategies that can be applied to solve common problems in programming. They help you recognize the underlying structure of a problem and apply the appropriate solution.

Why Coding Patterns?

  • Efficiency: Coding patterns help you solve problems more efficiently by providing a structured approach to problem-solving.
  • Reusability: Once you learn a pattern, you can apply it to multiple problems, saving time and effort.
  • Confidence: Knowing coding patterns can boost your confidence during interviews, as you can quickly identify the right approach to a problem.
  • Problem-Solving Skills: Coding patterns enhance your problem-solving skills by teaching you how to break down complex problems into manageable parts.

Common Coding Patterns

  1. Sliding Window: This pattern is used to solve problems involving arrays or strings where you need to find a subarray or substring that meets certain criteria. It involves maintaining a window of elements and adjusting its size as needed. These are some examples from leetcode with their link:
  2. Two Pointers: This pattern involves using two pointers to traverse an array or string from different ends or at different speeds. It is often used to solve problems related to pairs or triplets.

    Template in Java to solve Two pointers problems:

     public class TwoPointers {
     public int[] twoSum(int[] numbers, int target) {
         int left = 0;
         int right = numbers.length - 1;
         while (left < right) {
             int sum = numbers[left] + numbers[right];
             if (sum == target) {
                 return new int[]{left, right};
             } else if (sum < target) {
                 left++;
             } else {
                 right--;
             }
         }
         return new int[]{-1, -1}; // Not found
     }
 }
  3. Fast and Slow Pointers: This pattern is used to detect cycles in linked lists or arrays. It involves using two pointers that move at different speeds to identify the presence of a cycle.
  4. Binary Search: This pattern is used to search for an element in a sorted array or to find the position of a target value. It involves dividing the search space in half repeatedly until the target is found.
  5. Backtracking: This pattern is used to solve problems that involve exploring all possible combinations or permutations. It involves building a solution incrementally and backtracking when a solution is not feasible.
  6. Permutation: This pattern is used to generate all possible arrangements of a set of elements. It is often used in problems involving combinations or arrangements. 
     public class Permutations {
     public List<List<Integer>> permute(int[] nums) {
         List<List<Integer>> result = new ArrayList<>();
         backtrack(result, new ArrayList<>(), nums);
         return result;
     }

     private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums) {
         if (tempList.size() == nums.length) { // Base case: all numbers are used
             result.add(new ArrayList<>(tempList));
             return;
         }
         for (int i = 0; i < nums.length; i++) {
             if (tempList.contains(nums[i])) continue; // Skip duplicates
             tempList.add(nums[i]); // select current number
             backtrack(result, tempList, nums);
             tempList.remove(tempList.size() - 1); // backtrack - undo selection
         }
     }
 }
  7. Dynamic Programming: This pattern is used to solve problems that can be broken down into overlapping subproblems. It involves storing the results of subproblems to avoid redundant calculations.
  8. Heap: This pattern is used to efficiently manage a collection of elements with a priority. It is often used in problems involving sorting or finding the k-th largest/smallest element.

    Template to solve Heap problems:

     /*s
  We don't need to implement our own priority queue. We can use the built-in PriorityQueue class in Java. 
  Here is PriorityQueue useful methods -
  - PriorityQueue(): Creates an empty priority queue.
  - PriorityQueue(Comparator<? super E> comparator): Creates an empty priority queue with the specified comparator.
  - isEmpty(): Checks if the priority queue is empty.
  - offer(E e): Adds the specified element to the priority queue.
  - poll(): Retrieves and removes the head of the queue, or returns null if the queue is empty.
  - peek(): Retrieves, but does not remove, the head of the queue, or returns null if the queue is empty.
 */
 import java.util.*;

 public class Solution {
     public ListNode mergeKLists(ListNode[] lists) {
         var minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
         for (ListNode node : lists) {
             if (node != null) {
                 minHeap.offer(node);
             }
         }
         var dummy = new ListNode(0);
         ListNode curr = dummy;
         while (!minHeap.isEmpty()) {
             curr.next = minHeap.poll();
             curr = curr.next;
             if (curr.next != null) {
                 minHeap.offer(curr.next);
             }
         }
         return dummy.next;
     }
 }
  9. Two heaps: This pattern is used to efficiently manage two heaps to maintain the median of a stream of numbers. It is often used in problems involving dynamic median calculation.

    public class MedianFinder { private PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder()); private PriorityQueue minHeap = new PriorityQueue<>();

    public void addNum(int num) {
    maxHeap.offer(num);
    minHeap.offer(maxHeap.poll());
    if (minHeap.size() > maxHeap.size()) {
        maxHeap.offer(minHeap.poll());
    }
}

public double findMedian() {
    if (maxHeap.size() > minHeap.size()) {
        return maxHeap.peek();
    }
    return (maxHeap.peek() + minHeap.peek()) / 2.0;
} } ```
  10. Matrix Traversal: This pattern is used to traverse a matrix in various ways, such as row-wise, column-wise, or diagonally. It is often used in problems involving 2D arrays or grids.
    1. Example: Spiral Matrix
    2. Example: Rotate Image
    3. Example: Set Matrix Zeroes
    4. Example: Diagonal Traverse
    5. Example: Search a 2D Matrix
  11. Bit Manipulation: This pattern is used to perform operations on individual bits of integers. It is often used in problems involving binary representations or bitwise operations.
  12. Bitmasking: This pattern is used to represent subsets of a set using binary numbers. It is often used in problems involving combinations or subsets.
  13. Greedy Algorithms: This pattern is used to solve optimization problems by making the locally optimal choice at each step. It is often used in problems involving intervals or resources.
  14. Depth-First Search (DFS): This pattern is used to explore all possible paths in a graph or tree. It involves traversing as deep as possible before backtracking. It is often used in problems involving tree traversal or graph traversal.
  15. Breadth-First Search (BFS): This pattern is used to explore all nodes at the present depth level before moving on to the nodes at the next depth level.
  16. Topological Sort: This pattern is used to order the vertices of a directed acyclic graph (DAG) in a linear sequence. It is often used in scheduling problems.
  17. Union-Find: This pattern is used to solve problems involving disjoint sets or connected components. It involves maintaining a collection of disjoint sets and performing union and find operations.
  18. Trie: This pattern is used to store and search strings efficiently. It is often used in problems involving prefix matching or autocomplete.
  19. Fenwick Tree (Binary Indexed Tree): This pattern is used to efficiently query and update prefix sums in an array. It is often used in problems involving cumulative frequency or range queries.

Here is a simple implementation of Fenwick Tree in Java:

class FenwickTree {
    private int[] tree;
    private int size;

    public FenwickTree(int size) {
        this.size = size;
        tree = new int[size + 1];
    }

    public void update(int index, int value) {
        while (index <= size) {
            tree[index] += value;
            index += index & -index; 
        }
    }

    // lets understand this line with the help of binary representation
    // 4 = 100
    // 5 = 101
    // 4 & -4 = 4
    // 5 & -5 = 1   
    public int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & -index;
        }
        return sum;
    }
}
  1. Segment Tree: This pattern is used to efficiently query and update ranges in an array. It is often used in problems involving range queries or updates. 
    class SegmentTree {
    private int[] tree;
    private int size;

    public SegmentTree(int size) {
        this.size = size;
        tree = new int[4 * size];
        // why 4 * size?
        // this is because the segment tree is a binary tree and in the worst case, we need 4 times the size of the array to store the segment tree
    }

    public void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            tree[node] = Math.min(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    public void update(int index, int value, int node, int start, int end) {
        if (start == end) {
            tree[node] = value;
        } else {
            int mid = (start + end) / 2;
            if (index <= mid) {
                update(index, value, 2 * node + 1, start, mid);
            } else {
                update(index, value, 2 * node + 2, mid + 1, end);
            }
            tree[node] = Math.min(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    public int query(int L, int R, int node, int start, int end) {
        if (R < start || L > end) {
            return Integer.MAX_VALUE; // Return a large value for out of range
        }
        if (L <= start && R >= end) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        return Math.min(query(L, R, 2 * node + 1, start, mid), query(L, R, 2 * node + 2, mid + 1, end));
    }
}

Conclusion

This is not an exhaustive list of coding patterns, but it covers some of the most common ones. Also some problems can be solved using multiple patterns or combinations of patterns. The key is to practice and become familiar with these patterns so that you can recognize them when solving problems.

Additional Resources

« Kafka In and Out Java Versions »