DSA Patterns Roadmap for Beginners: 9 Patterns With Runnable Java

import java.util.*;

/** One tiny, runnable example per DSA pattern. Read top to bottom. */
public class Patterns {

    // 1. TWO POINTERS: sorted array, find a pair with a given sum. O(n)
    static int[] twoSumSorted(int[] a, int target) {
        int l = 0, r = a.length - 1;
        while (l < r) {
            int s = a[l] + a[r];
            if (s == target) return new int[]{l, r};
            if (s < target) l++; else r--;
        }
        return new int[]{-1, -1};
    }

    // 2. SLIDING WINDOW: longest substring without repeating characters. O(n)
    static int longestUnique(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int best = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            Integer prev = last.put(s.charAt(right), right);
            if (prev != null && prev >= left) left = prev + 1;     // shrink window past the duplicate
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    // 3. HASHING + PREFIX SUM: number of subarrays whose sum equals k. O(n)
    static int subarraySum(int[] a, int k) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, 1);
        int sum = 0, count = 0;
        for (int x : a) {
            sum += x;
            count += seen.getOrDefault(sum - k, 0);
            seen.merge(sum, 1, Integer::sum);
        }
        return count;
    }

    // 4. BINARY SEARCH: first index with value >= target in a sorted array. O(log n)
    static int lowerBound(int[] a, int target) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] < target) lo = mid + 1; else hi = mid;
        }
        return lo;
    }

    // 5. STACK: are the brackets balanced? O(n)
    static boolean balanced(String s) {
        Deque<Character> st = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if ("([{".indexOf(c) >= 0) st.push(c);
            else {
                if (st.isEmpty()) return false;
                char o = st.pop();
                if ("([{".indexOf(o) != ")]}".indexOf(c)) return false;
            }
        }
        return st.isEmpty();
    }

    // 6. HEAP: k largest elements. O(n log k)
    static List<Integer> topK(int[] a, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int x : a) { minHeap.add(x); if (minHeap.size() > k) minHeap.poll(); }
        List<Integer> out = new ArrayList<>(minHeap);
        out.sort(Comparator.reverseOrder());
        return out;
    }

    // 7. BFS: shortest path in a grid of 0 (free) and 1 (wall). O(rows*cols)
    static int shortestPath(int[][] g) {
        int R = g.length, C = g[0].length;
        int[][] dist = new int[R][C];
        for (int[] row : dist) Arrays.fill(row, -1);
        Deque<int[]> q = new ArrayDeque<>();
        q.add(new int[]{0, 0}); dist[0][0] = 0;
        int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int d = 0; d < 4; d++) {
                int nr = cur[0] + dr[d], nc = cur[1] + dc[d];
                if (nr >= 0 && nc >= 0 && nr < R && nc < C && g[nr][nc] == 0 && dist[nr][nc] < 0) {
                    dist[nr][nc] = dist[cur[0]][cur[1]] + 1;
                    q.add(new int[]{nr, nc});
                }
            }
        }
        return dist[R - 1][C - 1];
    }

    // 8. DYNAMIC PROGRAMMING: fewest coins to make an amount (the exact ATM/vending change problem). O(amount * coins)
    static int minCoins(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++)
            for (int c : coins)
                if (c <= a && dp[a - c] != Integer.MAX_VALUE) dp[a] = Math.min(dp[a], dp[a - c] + 1);
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

    // 9. BACKTRACKING: all subsets. O(2^n)
    static void subsets(int[] a, int i, Deque<Integer> cur, List<List<Integer>> out) {
        if (i == a.length) { out.add(new ArrayList<>(cur)); return; }
        subsets(a, i + 1, cur, out);                       // skip a[i]
        cur.addLast(a[i]); subsets(a, i + 1, cur, out); cur.removeLast();   // take a[i], then undo
    }

    public static void main(String[] args) {
        System.out.println("two pointers   : " + Arrays.toString(twoSumSorted(new int[]{1, 3, 4, 6, 9}, 10)));
        System.out.println("sliding window : " + longestUnique("abcabcbb"));
        System.out.println("prefix + hash  : " + subarraySum(new int[]{1, 2, 3, -3, 3}, 3));
        System.out.println("binary search  : " + lowerBound(new int[]{1, 3, 5, 7, 9}, 6));
        System.out.println("stack          : " + balanced("{[()]}") + " " + balanced("([)]"));
        System.out.println("heap top-3     : " + topK(new int[]{5, 1, 9, 3, 7, 8}, 3));
        System.out.println("BFS grid       : " + shortestPath(new int[][]{{0, 0, 0}, {1, 1, 0}, {0, 0, 0}}));
        System.out.println("DP min coins   : " + minCoins(new int[]{1, 5, 10, 25}, 63) + " (greedy gives the same here)  "
                + minCoins(new int[]{1, 3, 4}, 6) + " (greedy would pick 4+1+1 = 3 coins; DP finds 3+3 = 2)");
        List<List<Integer>> out = new ArrayList<>();
        subsets(new int[]{1, 2, 3}, 0, new ArrayDeque<>(), out);
        System.out.println("backtracking   : " + out);
    }
}

two pointers   : [0, 4]
sliding window : 3
prefix + hash  : 5
binary search  : 3
stack          : true false
heap top-3     : [9, 8, 7]
BFS grid       : 4
DP min coins   : 6 (greedy gives the same here)  2 (greedy would pick 4+1+1 = 3 coins; DP finds 3+3 = 2)
backtracking   : [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]