DSA Java

Data Structures & Algorithms Patterns for Java Backend Engineers: LeetCode Approach

Most Java backend engineers can write a Spring Boot service in their sleep, but freeze when asked to reverse a linked list or find the longest substring without repeating characters. This guide maps the 12 essential DSA problem-solving patterns to real Java idioms — PriorityQueue, ArrayDeque, HashMap — and gives you a repeatable LeetCode study system that fits around a full-time engineering job.

Md Sanwar Hossain April 5, 2026 20 min read DSA Java

Why DSA Matters for Java Backend Engineers in 2026

Google, Meta, Amazon, and every FAANG-adjacent company still use LeetCode-style technical screens — even for senior backend roles. Knowing why a TreeMap costs O(log n) per lookup instead of O(1) (HashMap) makes you a better API designer, not just a better interviewee.

The backend world runs on Java. But most Java DSA guides use Python. This guide translates every pattern into idiomatic Java — with the right collection types, comparator lambdas, and edge-case handling you would use in production code.

The 85% Coverage Rule

Research across thousands of FAANG interview reports shows that 85% of coding questions come from just 12 patterns. Master these patterns and you can solve ~80% of Medium problems on sight:

1. Sliding Window
2. Two Pointers
3. Fast & Slow Pointers
4. Merge Intervals
5. Cyclic Sort
6. In-Place Linked List Reversal
7. BFS (Tree & Graph)
8. DFS (Tree & Graph)
9. Two Heaps
10. Subsets / Backtracking
11. Binary Search Variants
12. Dynamic Programming

Pattern 1: Sliding Window

Use when the problem asks for a contiguous subarray/substring meeting a condition (max sum, longest without repeating chars, minimum window substring).

Java idiom: HashMap<Character, Integer> for frequency counting, two int pointers (left, right).

// LC 3: Longest Substring Without Repeating Characters — O(n) time, O(min(m,n)) space
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> charIndex = new HashMap<>();
    int maxLen = 0;
    int left = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (charIndex.containsKey(c)) {
            // Move left past the last seen position of this char
            left = Math.max(left, charIndex.get(c) + 1);
        }
        charIndex.put(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

// LC 76: Minimum Window Substring — O(n) time, O(52) space
public String minWindow(String s, String t) {
    int[] freq = new int[128];
    for (char c : t.toCharArray()) freq[c]++;
    int required = t.length(), left = 0, minLen = Integer.MAX_VALUE, minLeft = 0;

    for (int right = 0; right < s.length(); right++) {
        if (freq[s.charAt(right)]-- > 0) required--;
        while (required == 0) {
            if (right - left + 1 < minLen) { minLen = right - left + 1; minLeft = left; }
            if (freq[s.charAt(left++)]++ == 0) required++;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
}

Pattern 2: Two Pointers

Sort the array first, then use a left and right pointer converging toward the middle. Handles 3Sum, container-with-most-water, remove duplicates.

// LC 15: 3Sum — O(n²) time, O(1) extra space
public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();

    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates

        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++; right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

Pattern 3: Fast & Slow Pointers (Floyd's Cycle)

Used for cycle detection in linked lists and arrays. The slow pointer moves one step; the fast pointer moves two steps. When they meet, a cycle exists.

// LC 142: Linked List Cycle II — O(n) time, O(1) space
public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            // Cycle detected — find entry point
            ListNode entry = head;
            while (entry != slow) {
                entry = entry.next;
                slow = slow.next;
            }
            return entry;
        }
    }
    return null; // no cycle
}

// LC 287: Find the Duplicate Number — O(n) time, O(1) space (treat array as linked list)
public int findDuplicate(int[] nums) {
    int slow = nums[0], fast = nums[0];
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

The fast-and-slow pointer technique works here because Floyd's cycle detection algorithm guarantees that once the two pointers meet inside the cycle, resetting one pointer to the head and advancing both one step at a time will cause them to meet again exactly at the cycle entry point. In an interview, always verify your understanding of why the technique works — interviewers frequently ask follow-up questions about the mathematical proof. The same pattern applies to LC 457 (Circular Array Loop) and detecting loops in functional chains.

Pattern 4: Merge Intervals

Sort intervals by start time, then linearly merge overlapping ones. Key Java idiom: Arrays.sort(intervals, (a,b) -> a[0] - b[0]).

// LC 56: Merge Intervals — O(n log n) time, O(n) space
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[0][]);
}

// LC 253: Meeting Rooms II (min rooms needed) — O(n log n) time
public int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> endTimes = new PriorityQueue<>();

    for (int[] interval : intervals) {
        if (!endTimes.isEmpty() && endTimes.peek() <= interval[0]) {
            endTimes.poll(); // reuse the room
        }
        endTimes.offer(interval[1]);
    }
    return endTimes.size(); // rooms in use
}

Interval problems almost always begin with a sort — sorting by start time enables a single left-to-right pass where each interval either extends the last merged interval (if it overlaps) or starts a new one. The min-heap approach for Meeting Rooms II is particularly elegant: the heap always exposes the earliest-ending meeting, so you can determine in O(log n) whether an incoming meeting can reuse that room. When comparing intervals in a Java comparator, prefer Integer.compare(a[0], b[0]) over a[0] - b[0] to avoid integer overflow with extreme values.

Pattern 5: BFS

Level-by-level graph/tree traversal using a Queue (always ArrayDeque in Java, never LinkedList for performance). Perfect for shortest path, level-order traversal, and minimum steps problems.

// LC 102: Binary Tree Level Order Traversal — O(n) time, O(n) space
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

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

// LC 127: Word Ladder — O(M² × N) time where M=word length, N=wordList size
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<>(wordList);
    if (!wordSet.contains(endWord)) return 0;

    Deque<String> queue = new ArrayDeque<>();
    queue.offer(beginWord);
    int steps = 1;

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            char[] word = queue.poll().toCharArray();
            for (int j = 0; j < word.length; j++) {
                char original = word[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    word[j] = c;
                    String next = new String(word);
                    if (next.equals(endWord)) return steps + 1;
                    if (wordSet.remove(next)) queue.offer(next);
                }
                word[j] = original;
            }
        }
        steps++;
    }
    return 0;
}

BFS guarantees the shortest path in an unweighted graph because it explores all nodes at depth d before any at depth d+1. Always prefer ArrayDeque over LinkedList as the queue implementation in Java — they share the Queue interface but ArrayDeque is backed by a contiguous array with better cache locality, offering roughly 2× better throughput. The key BFS discipline is removing from the word set as you add to the queue (not as you process) — this prevents the same word being enqueued multiple times and blowing up the time complexity from O(N²) to O(N).

Pattern 6: DFS

Use recursion (implicit stack) or an explicit ArrayDeque for iterative DFS. Key for path problems, island counting, and graph coloring.

// LC 200: Number of Islands — O(M×N) time, O(M×N) space (recursion stack)
public int numIslands(char[][] grid) {
    int count = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == '1') {
                count++;
                dfs(grid, r, c);
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') return;
    grid[r][c] = '0'; // mark visited
    dfs(grid, r + 1, c);
    dfs(grid, r - 1, c);
    dfs(grid, r, c + 1);
    dfs(grid, r, c - 1);
}

Mutating the input grid to mark cells as visited avoids a separate boolean[][] visited array, saving O(M×N) extra space. This is acceptable when the input is not needed after the call; if the original grid must be preserved, pass a copy. Recursive DFS risks a StackOverflowError on very large grids (e.g., 300×300 with a single giant island, giving a recursion depth of 90,000). For such cases, convert to iterative DFS with an explicit ArrayDeque stack. The four-directional expansion pattern (up, down, left, right) repeats in dozens of grid problems — extract it as a int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}} constant to reduce typos.

Pattern 7: Two Heaps

Maintain a max-heap for the lower half and a min-heap for the upper half to find the running median in O(log n) per insertion.

// LC 295: Find Median from Data Stream — O(log n) add, O(1) findMedian
class MedianFinder {
    private final PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
    private final PriorityQueue<Integer> upper = new PriorityQueue<>(); // min-heap

    public void addNum(int num) {
        lower.offer(num);
        upper.offer(lower.poll()); // balance: move max of lower to upper
        if (lower.size() < upper.size()) {
            lower.offer(upper.poll()); // keep lower >= upper in size
        }
    }

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

The invariant is that lower always holds the smaller half and upper the larger half, with lower.size() >= upper.size(). The balancing step after every insertion ensures neither heap grows more than one element larger than the other. This pattern also applies to the sliding window median problem (LC 480), where you additionally need to remove the element leaving the window — a harder variant requiring a lazy deletion technique using a separate removal counter, since Java's PriorityQueue does not support O(log n) arbitrary element removal by value.

Pattern 8: Backtracking

Explore all possibilities by building a candidate solution step by step, pruning branches that cannot lead to a valid solution.

// LC 46: Permutations — O(n × n!) time, O(n) space (recursion stack)
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, new ArrayList<>(), new boolean[nums.length], result);
    return result;
}

private void backtrack(int[] nums, List<Integer> current, boolean[] used, List<List<Integer>> result) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        current.add(nums[i]);
        backtrack(nums, current, used, result);
        current.remove(current.size() - 1); // undo
        used[i] = false;
    }
}

// LC 39: Combination Sum — O(N^(T/M)) where T=target, M=min candidate
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(candidates);
    combinationDFS(candidates, 0, target, new ArrayList<>(), result);
    return result;
}

private void combinationDFS(int[] candidates, int start, int remaining,
                             List<Integer> current, List<List<Integer>> result) {
    if (remaining == 0) { result.add(new ArrayList<>(current)); return; }
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remaining) break; // sorted — prune
        current.add(candidates[i]);
        combinationDFS(candidates, i, remaining - candidates[i], current, result);
        current.remove(current.size() - 1);
    }
}

The critical discipline in backtracking is the "undo" step — current.remove(current.size() - 1) and used[i] = false must mirror every "choose" operation exactly. A missing undo is the most common backtracking bug. The pruning line if (candidates[i] > remaining) break converts what would be O(N^(T/M)) exponential time into a practical solution by cutting the search tree short whenever a sorted candidate exceeds the remaining target. In interviews, pruning logic differentiates a good solution from an excellent one.

Pattern 9: Binary Search Variants

Beyond the basic sorted-array search, binary search applies to any monotonic decision function: "can I achieve X with a budget of K?" Always ask yourself — can I binary search on the answer?

// Template — binary search on answer space
// LC 875: Koko Eating Bananas — O(n log W) time where W = max pile
public int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = Arrays.stream(piles).max().getAsInt();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(piles, mid, h)) {
            hi = mid; // try smaller speed
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

private boolean canFinish(int[] piles, int speed, int h) {
    int hours = 0;
    for (int pile : piles) hours += (pile + speed - 1) / speed; // ceiling division
    return hours <= h;
}

// LC 33: Search in Rotated Sorted Array — O(log n) time
public int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[lo] <= nums[mid]) { // left half is sorted
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else { // right half is sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

Pattern 10: Dynamic Programming

Break the problem into overlapping subproblems. Java tip: prefer bottom-up tabulation over top-down memoization for cache-friendly access and avoiding stack overflow on large inputs.

// LC 322: Coin Change — O(amount × coins) time, O(amount) space
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1); // sentinel "infinity"
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

// LC 1143: Longest Common Subsequence — O(m×n) time, O(m×n) space
public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(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];
}

The key to DP is identifying the recurrence relation before writing any code. For Coin Change, the recurrence is dp[i] = min(dp[i - coin] + 1) for each coin — build from 0 upward and every subproblem solution is already computed when needed. For the LCS 2D grid, the space can be optimized to O(min(m,n)) by keeping only two rows at a time, which is worth mentioning in interviews when the interviewer asks for space optimization. The sentinel value amount + 1 (instead of Integer.MAX_VALUE) avoids overflow when incrementing, a common Java bug in DP problems.

Pattern 11: Union Find

Group elements into disjoint sets. Supports near-O(1) find and union with path compression + union by rank. Used for connected components and Kruskal's MST.

// Reusable Union-Find — O(α(n)) per operation
class UnionFind {
    private final int[] parent, rank;

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // path compression
        return parent[x];
    }

    boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false; // already connected
        if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        return true;
    }
}

// LC 200: Number of Islands using Union Find
public int numIslandsUF(char[][] grid) {
    int m = grid.length, n = grid[0].length;
    UnionFind uf = new UnionFind(m * n);
    int islands = 0;
    int[][] dirs = {{1,0},{0,1}};

    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == '1') {
                islands++;
                for (int[] d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr < m && nc < n && grid[nr][nc] == '1') {
                        if (uf.union(r * n + c, nr * n + nc)) islands--;
                    }
                }
            }
        }
    }
    return islands;
}

Path compression (line: parent[x] = find(parent[x])) flattens the tree during each find call, making subsequent lookups near-O(1). Union by rank prevents tall trees from forming by attaching the shorter tree under the taller one. Together these optimizations achieve O(α(n)) amortized time — practically constant for any realistic input size, since the inverse Ackermann function α(n) never exceeds 4 for n < 2^65536. Keep a reusable UnionFind template in your interview repertoire; it solves Number of Connected Components (LC 323), Redundant Connection (LC 684), and Accounts Merge (LC 721) with minimal code changes.

Pattern 12: Monotonic Stack

Maintain a stack where elements are always increasing or always decreasing. Solves "next greater element", "largest rectangle in histogram", and "trapping rain water" in O(n).

// LC 84: Largest Rectangle in Histogram — O(n) time, O(n) space
public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>(); // monotonic increasing stack (indices)
    int maxArea = 0;
    int n = heights.length;

    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (!stack.isEmpty() && heights[stack.peek()] > h) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

// LC 496: Next Greater Element I — O(n) using monotonic stack
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<>(); // num -> next greater
    Deque<Integer> stack = new ArrayDeque<>(); // decreasing stack

    for (int num : nums2) {
        while (!stack.isEmpty() && stack.peek() < num) {
            map.put(stack.pop(), num);
        }
        stack.push(num);
    }
    int[] result = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        result[i] = map.getOrDefault(nums1[i], -1);
    }
    return result;
}

The monotonic stack achieves O(n) by ensuring each element is pushed and popped at most once, giving O(2n) total operations despite the inner while loop. The sentinel trick — appending a virtual bar of height 0 at the end — ensures all remaining bars in the stack are processed without a separate post-loop cleanup. For the "next greater element" variant, use a decreasing monotonic stack (pop when the incoming element is greater). The decision between increasing and decreasing monotonic stacks can be determined by the question: "what do I pop when?"— if you pop when the new element is smaller, you have a decreasing stack; if larger, an increasing one.

Java-Specific Tips That Cost People Interviews

Always Use ArrayDeque, Not LinkedList or Stack

// BAD — Stack is legacy (synchronized, slower)
Stack<Integer> stack = new Stack<>();

// BAD — LinkedList has worse cache locality
Queue<Integer> queue = new LinkedList<>();

// GOOD — ArrayDeque is backed by a resizable array; no synchronization overhead
Deque<Integer> stack = new ArrayDeque<>();
Deque<Integer> queue = new ArrayDeque<>();

This matters in interviews because interviewers notice when candidates reach for new LinkedList<>() as a queue — it signals unfamiliarity with Java's standard library evolution. Stack<> extends Vector which is synchronized, adding unneeded overhead in single-threaded algorithm code. ArrayDeque implements both Queue (FIFO via offer/poll) and Deque (LIFO via push/pop), so it's the correct choice for both stacks and queues.

PriorityQueue with Custom Comparators

// Min-heap (default)
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// Sort 2D array by second element descending
PriorityQueue<int[]> pqDesc = new PriorityQueue<>((a, b) -> b[1] - a[1]);

Integer Overflow in Comparators

// BAD — integer overflow when a[0] - b[0] overflows int
Arrays.sort(arr, (a, b) -> a[0] - b[0]); // risky if values near Integer.MIN/MAX_VALUE

// GOOD — use Integer.compare() to avoid overflow
Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));

LeetCode Study System for Busy Engineers

Quick Reference: Java Collections for Each Pattern

Conclusion

Mastering DSA as a Java backend engineer is not about memorizing solutions — it's about recognizing the shape of a problem and mapping it to the right pattern. A sliding-window sub-array question is always solved with two pointers and a HashMap. A "find connected components" question is always Union Find or DFS. A "minimum steps" question is always BFS.

Build your pattern library one at a time, validate it with 3–5 LeetCode problems per pattern, and run one timed mock per week. In 12 weeks you will be in the top 15% of Java interviewees — not because you are smarter, but because you have a system.

Md Sanwar Hossain

Software Engineer · Java · Spring Boot · Algorithms