DSA Java Templates

Array Templates

1. Array Traversal

// Forward traversal
for (int i = 0; i < arr.length; i++) {
    // Process arr[i]
}

// Reverse traversal
for (int i = arr.length - 1; i >= 0; i--) {
    // Process arr[i]
}

// Enhanced for (no index needed)
for (int num : arr) {
    // Process num
}

Time: O(n) | Use when: Simple iteration, no index needed.

2. Two Pointers

// Two pointers from both ends (sorted array)
public int[] twoSumSorted(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[]{-1, -1};
}

Time: O(n) | Use when: Sorted array, find pair with sum.

3. Sliding Window

// Fixed window size
public int maxSumSubarray(int[] arr, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];
    int maxSum = windowSum;
    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

Time: O(n) | Use when: Contiguous subarray of fixed size.

4. Prefix Sum

int[] prefix = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
}
// Range sum [l, r] = prefix[r+1] - prefix[l]

Time: O(n) build, O(1) query | Use when: Multiple range sum queries.

String Templates

1. Character Counting

int[] count = new int[26];
for (char c : s.toCharArray()) {
    count[c - 'a']++;
}

Time: O(n) | Use when: Frequency analysis, anagram checks.

2. StringBuilder Patterns

StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
    sb.append(c);
}
String result = sb.toString();

// With capacity hint
StringBuilder sb = new StringBuilder(s.length());

Time: O(n) | Use when: String concatenation in loops.

3. Palindrome Check

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) return false;
        left++;
        right--;
    }
    return true;
}

Time: O(n) | Use when: Check if string reads same backwards.

4. Anagram Check

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int c : count) {
        if (c != 0) return false;
    }
    return true;
}

Time: O(n) | Use when: Check if two strings are anagrams.

HashMap Templates

1. Frequency Count

Map<String, Integer> freq = new HashMap<>();
for (String s : list) {
    freq.put(s, freq.getOrDefault(s, 0) + 1);
}
// Or with merge
for (String s : list) {
    freq.merge(s, 1, Integer::sum);
}

Time: O(n) | Use when: Count occurrences.

2. Two Sum Pattern

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[]{-1, -1};
}

Time: O(n) | Use when: Find pair with target sum.

3. Group By

Map<String, List<String>> groups = new HashMap<>();
for (String s : list) {
    String key = computeKey(s);  // grouping criterion
    groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
// Or with streams
Map<String, List<String>> groups2 = list.stream()
    .collect(Collectors.groupingBy(s -> computeKey(s)));

Time: O(n) | Use when: Group elements by criterion.

HashSet Templates

1. Contains Check

Set<Integer> set = new HashSet<>();
for (int num : arr) set.add(num);

// O(1) lookup
if (set.contains(target)) {
    // Found
}

Time: O(1) lookup | Use when: Fast membership test.

2. Intersection

Set<Integer> setA = new HashSet<>(listA);
Set<Integer> intersection = new HashSet<>();
for (int num : listB) {
    if (setA.contains(num)) intersection.add(num);
}
// Or with streams
Set<Integer> intersection2 = setA.stream()
    .filter(setB::contains)
    .collect(Collectors.toSet());

Time: O(n + m) | Use when: Find common elements.

3. Union

Set<Integer> union = new HashSet<>(setA);
union.addAll(setB);

Time: O(n + m) | Use when: Combine all unique elements.

4. Duplicate Detection

public boolean hasDuplicates(int[] arr) {
    Set<Integer> seen = new HashSet<>();
    for (int num : arr) {
        if (!seen.add(num)) return true;  // add() returns false if exists
    }
    return false;
}

Time: O(n) | Use when: Check for duplicates.

Sorting Templates

1. Arrays.sort()

int[] arr = {5, 2, 8, 1, 9};
Arrays.sort(arr);  // [1, 2, 5, 8, 9]

// With custom range
Arrays.sort(arr, 1, 4);  // Sort indices 1-3

Time: O(n log n) | Use when: Basic sorting.

2. Custom Comparator

// Sort strings by length
String[] arr = {"apple", "hi", "banana"};
Arrays.sort(arr, (a, b) -> a.length() - b.length());

// Sort by multiple criteria
Arrays.sort(arr, Comparator.comparing(String::length)
    .thenComparing(Comparator.naturalOrder()));

// Reverse order
Arrays.sort(arr, Comparator.reverseOrder());

Time: O(n log n) | Use when: Custom sort order.

3. Lambda Sorting

List<Person> people = new ArrayList<>();

// Sort by name
people.sort(Comparator.comparing(p -> p.name));

// Sort by age, then name
people.sort(Comparator.comparingInt((Person p) -> p.age)
    .thenComparing(p -> p.name));

// Nulls last
people.sort(Comparator.comparing(p -> p.name, Comparator.nullsLast(Comparator.naturalOrder())));

Time: O(n log n) | Use when: Sort complex objects.

Binary Search Templates

1. Standard Binary Search

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

Time: O(log n) | Use when: Find element in sorted array.

2. Leftmost Binary Search

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

Time: O(log n) | Use when: Find first occurrence.

3. Rightmost Binary Search

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

Time: O(log n) | Use when: Find last occurrence.

4. Binary Search on Answer

public int binarySearchOnAnswer(int[] arr) {
    int left = minPossible, right = maxPossible;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isFeasible(arr, mid)) {
            right = mid;  // Try smaller
        } else {
            left = mid + 1;  // Try larger
        }
    }
    return left;
}

Time: O(n log M) | Use when: Minimize/maximize answer.

Stack Templates

1. Next Greater Element

public int[] nextGreater(int[] arr) {
    int[] result = new int[arr.length];
    Stack<Integer> stack = new Stack<>();
    
    for (int i = arr.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && stack.peek() <= arr[i]) {
            stack.pop();
        }
        result[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(arr[i]);
    }
    return result;
}

Time: O(n) | Use when: Find next greater element for each.

2. Monotonic Stack

// Monotonically decreasing stack
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < arr.length; i++) {
    while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
        int idx = stack.pop();
        // Process arr[idx] with arr[i] as next greater
    }
    stack.push(i);
}

Time: O(n) | Use when: Next greater/smaller element.

3. Balanced Parentheses

public boolean isBalanced(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return stack.isEmpty();
}

Time: O(n) | Use when: Validate nested brackets.

Queue Templates

1. BFS Template

public void bfs(Node start) {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();
    
    queue.offer(start);
    visited.add(start);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            for (Node neighbor : node.neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }
}

Time: O(V + E) | Use when: Level-order traversal, shortest path.

2. Sliding Window Maximum

public int[] maxSlidingWindow(int[] arr, int k) {
    Deque<Integer> deque = new ArrayDeque<>();
    int[] result = new int[arr.length - k + 1];
    
    for (int i = 0; i < arr.length; i++) {
        // Remove elements outside window
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        // Remove smaller elements
        while (!deque.isEmpty() && arr[deque.peekLast()] < arr[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
        if (i >= k - 1) {
            result[i - k + 1] = arr[deque.peekFirst()];
        }
    }
    return result;
}

Time: O(n) | Use when: Max/min in each sliding window.

Deque Templates

1. Palindrome Check

public boolean isPalindrome(String s) {
    Deque<Character> deque = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        deque.offerLast(c);
    }
    while (deque.size() > 1) {
        if (deque.pollFirst() != deque.pollLast()) return false;
    }
    return true;
}

Time: O(n) | Use when: Check palindrome.

2. Sliding Window with Deque

public void slidingWindow(int[] arr, int k) {
    Deque<Integer> deque = new ArrayDeque<>();
    
    for (int i = 0; i < arr.length; i++) {
        // Remove out-of-window elements
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        // Maintain monotonic property
        while (!deque.isEmpty() && arr[deque.peekLast()] > arr[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
        
        if (i >= k - 1) {
            // Window ready, deque.peekFirst() is min/max
        }
    }
}

Time: O(n) | Use when: Min/max in sliding window.

Linked List Templates

1. Reversal

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

Time: O(n) | Use when: Reverse linked list.

2. Cycle Detection (Floyd's)

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;
}

// Find cycle start
public ListNode detectCycleStart(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}

Time: O(n) | Use when: Detect cycle in linked list.

3. Merge Two Sorted Lists

public ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

Time: O(n + m) | Use when: Merge two sorted lists.

Tree Templates

1. DFS - Inorder

public void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.println(root.val);
    inorder(root.right);
}
// Iterative
public void inorderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        System.out.println(curr.val);
        curr = curr.right;
    }
}

Time: O(n) | Use when: Sorted order, validate BST.

2. DFS - Preorder

public void preorder(TreeNode root) {
    if (root == null) return;
    System.out.println(root.val);
    preorder(root.left);
    preorder(root.right);
}

Time: O(n) | Use when: Copy/serialize tree.

3. DFS - Postorder

public void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.println(root.val);
}

Time: O(n) | Use when: Delete tree, calculate height.

4. BFS - Level Order

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; 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;
}

Time: O(n) | Use when: Process level by level.

DFS Templates

1. Graph DFS

public void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {
    visited.add(node);
    System.out.println(node);
    
    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        if (!visited.contains(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }
}

// Iterative
public void dfsIterative(Map<Integer, List<Integer>> graph, int start) {
    Stack<Integer> stack = new Stack<>();
    Set<Integer> visited = new HashSet<>();
    stack.push(start);
    
    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (!visited.contains(node)) {
            visited.add(node);
            for (int neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
}

Time: O(V + E) | Use when: Explore all paths, connected components.

2. Backtracking Template

public void backtrack(List<Integer> state, List<List<Integer>> result, int[] choices) {
    if (isSolution(state)) {
        result.add(new ArrayList<>(state));  // Copy!
        return;
    }
    
    for (int choice : choices) {
        if (isValid(state, choice)) {
            state.add(choice);      // Choose
            backtrack(state, result, choices);  // Explore
            state.remove(state.size() - 1);    // Un-choose
        }
    }
}

Time: O(2^n) | Use when: Generate all combinations/permutations.

BFS Templates

1. Graph BFS

public void bfs(Map<Integer, List<Integer>> graph, int start) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    
    queue.offer(start);
    visited.add(start);
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.println(node);
        
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}

Time: O(V + E) | Use when: Shortest path (unweighted).

2. Shortest Path

public int shortestPath(Map<Integer, List<Integer>> graph, int start, int end) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    Map<Integer, Integer> dist = new HashMap<>();
    
    queue.offer(start);
    visited.add(start);
    dist.put(start, 0);
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        if (node == end) return dist.get(node);
        
        for (int neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                dist.put(neighbor, dist.get(node) + 1);
                queue.offer(neighbor);
            }
        }
    }
    return -1;  // Not reachable
}

Time: O(V + E) | Use when: Shortest path in unweighted graph.

Heap Templates

1. Top K Elements

public int[] topK(int[] arr, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for (int num : arr) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();  // Remove smallest
        }
    }
    
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = minHeap.poll();
    }
    return result;
}

Time: O(n log k) | Use when: Find K largest/smallest.

2. Median Finding

public double findMedian(int[] arr) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for (int num : arr) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());
        
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
    
    if (maxHeap.size() > minHeap.size()) return maxHeap.peek();
    return (maxHeap.peek() + minHeap.peek()) / 2.0;
}

Time: O(n log n) | Use when: Running median.

3. Merge K Sorted Lists

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

Time: O(N log k) | Use when: Merge k sorted sequences.

Graph Templates

1. Adjacency List

// Build graph
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
    graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
    graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);  // Undirected
}

2. Topological Sort

public List<Integer> topologicalSort(int n, int[][] edges) {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    int[] inDegree = new int[n];
    
    for (int[] edge : edges) {
        graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
        inDegree[edge[1]]++;
    }
    
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) queue.offer(i);
    }
    
    List<Integer> result = new ArrayList<>();
    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (--inDegree[neighbor] == 0) queue.offer(neighbor);
        }
    }
    return result.size() == n ? result : new ArrayList<>();  // Cycle if size < n
}

Time: O(V + E) | Use when: Task ordering, course schedule.

3. Union-Find

public class UnionFind {
    int[] parent, rank;
    
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);  // Path compression
        return parent[x];
    }
    
    public boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) { parent[px] = py; }
        else if (rank[px] > rank[py]) { parent[py] = px; }
        else { parent[py] = px; rank[px]++; }
        return true;
    }
}

Time: O(α(n)) amortized | Use when: Connected components, cycle detection.

DP Templates

1. Memoization Template

public int memoized(int[] arr, int n, Integer[] dp) {
    if (n == 0) return baseCase;
    if (dp[n] != null) return dp[n];
    
    int result = 0;
    // Recursive relationship
    for (int i = 0; i < n; i++) {
        result = Math.max(result, memoized(arr, i, dp) + arr[i]);
    }
    return dp[n] = result;
}
// Usage: Integer[] dp = new Integer[n + 1];

2. Tabulation Template

public int tabulated(int[] arr) {
    int n = arr.length;
    int[] dp = new int[n + 1];
    
    dp[0] = baseCase;
    for (int i = 1; i <= n; i++) {
        // Build from smaller subproblems
        for (int j = 0; j < i; j++) {
            dp[i] = Math.max(dp[i], dp[j] + arr[i]);
        }
    }
    return dp[n];
}

3. 1D DP

// Climbing stairs
public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

4. 2D DP

// 0/1 Knapsack
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];
}

Bit Manipulation Templates

Common Bit Tricks:

// Check if number is power of 2
boolean isPowerOf2(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

// Get ith bit
int getBit(int n, int i) {
    return (n >> i) & 1;
}

// Set ith bit
int setBit(int n, int i) {
    return n | (1 << i);
}

// Clear ith bit
int clearBit(int n, int i) {
    return n & ~(1 << i);
}

// Toggle ith bit
int toggleBit(int n, int i) {
    return n ^ (1 << i);
}

// Count set bits (Brian Kernighan)
int countBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);  // Clear lowest set bit
        count++;
    }
    return count;
}

// Find single number (XOR all)
int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) result ^= num;
    return result;
}

Time: O(1) for bit ops, O(log n) for bit counting | Use when: Fast math, unique element, subset generation.

Interval Templates

1. Merge 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[0][]);
}

Time: O(n log n) | Use when: Merge overlapping intervals.

2. Insert Interval

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0;
    
    // Add all intervals before newInterval
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i++]);
    }
    
    // Merge overlapping intervals
    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.add(newInterval);
    
    // Add remaining intervals
    while (i < intervals.length) {
        result.add(intervals[i++]);
    }
    
    return result.toArray(new int[0][]);
}

Time: O(n) | Use when: Insert and merge interval.