SvenStack

Algorithm-Day37-Binary-Tree-Inorder-Traversal-lc-94

Posted on 2025-08-02 In Algorithms , Binary Tree

🧩 Problem Description

Given the root of a binary tree, return its inorder traversal as a list of integers.

Inorder traversal order: left → root → right

💬 Example

1 2	Input: root = [1,null,2,3] Output: [1,3,2]

💡 Approach 1: Recursive DFS

The simplest way is to use recursion.
Visit:

Left subtree
Current node
Right subtree

🔢 Java Code (Recursive)

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }

    private void dfs(TreeNode node, List<Integer> res) {
        if (node == null) return;
        dfs(node.left, res);
        res.add(node.val);
        dfs(node.right, res);
    }
}

💡 Approach 2: Iterative with Stack

Use a stack to simulate the recursion.

🔢 Java Code (Iterative)

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        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();
            res.add(curr.val);
            curr = curr.right;
        }

        return res;
    }
}

⏱ Time and Space Complexity

Time Complexity: O(n) — each node is visited once
Space Complexity:
- Recursive: O(h) stack depth (h = height)
- Iterative: O(h) explicit stack

✍️ Summary

Learn both recursive and iterative versions
Foundation for tree problems like:
- lc-144: Preorder traversal
- lc-145: Postorder traversal
- lc-230: Kth Smallest in BST

Tree traversal mastery is essential for any tree-based problem.

Algorithm-Day36-LRU-Cache-lc-146

Posted on 2025-08-01 In Algorithms , Design

🧩 Problem Description

Design a data structure that follows the Least Recently Used (LRU) cache policy.

Implement the LRUCache class:

LRUCache(int capacity) initializes the cache with a positive size capacity.
int get(int key) returns the value of the key if it exists, otherwise returns -1.
void put(int key, int value) updates the value of the key. If the number of keys exceeds the capacity, evict the least recently used key.

💬 Example

Input:
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1,1], [2,2], [1], [3,3], [2], [4,4], [1], [3], [4]]
Output:
[null, null, null, 1, null, -1, null, -1, 3, 4]

💡 Intuition

To achieve O(1) time complexity for both get and put, use:

A HashMap to store key → node
A Doubly Linked List to track the usage order
- Most recently used at the front
- Least recently used at the end

When a key is accessed:

Move it to the front of the list
When inserting:
If at capacity, remove the tail (least recently used)

🔢 Java Code (Custom Doubly Linked List)

class LRUCache {

    class Node {
        int key, value;
        Node prev, next;
        Node(int k, int v) {
            key = k;
            value = v;
        }
    }

    private final int capacity;
    private Map<Integer, Node> cache;
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();

        // Dummy head and tail
        head = new Node(0, 0);
        tail = new Node(0, 0);

        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;

        Node node = cache.get(key);
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            if (cache.size() == capacity) {
                Node lru = tail.prev;
                remove(lru);
                cache.remove(lru.key);
            }

            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
        }
    }

    // Doubly Linked List helpers
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void moveToHead(Node node) {
        remove(node);
        addToHead(node);
    }
}

⏱ Time and Space Complexity

Time Complexity:
- get: O(1)
- put: O(1)
Space Complexity: O(capacity)

🧠 Summary

Combines a HashMap (for O(1) access) and a Doubly Linked List (for O(1) insert/delete).
A great example of system design + data structure synergy.
Common interview favorite!

Know this one cold — it’s the basis for many real-world cache systems (like Redis, in-memory caching, etc.)

Algorithm-Day35-Merge-K-Sorted-Lists-lc-23

Posted on 2025-07-31 In Algorithms , Linked List

🧩 Problem Description

You are given an array of k linked lists, each sorted in ascending order.

Merge all the linked lists into one sorted linked list and return it.

💬 Example

1 2	Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6]

💡 Approach 1: Min-Heap (Priority Queue)

Use a min-heap (priority queue) to always pull the smallest current node across all lists.

🔢 Java Code (PriorityQueue)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        PriorityQueue<ListNode> heap = new PriorityQueue<>(
            (a, b) -> a.val - b.val
        );

        for (ListNode node : lists) {
            if (node != null) heap.offer(node);
        }

        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

        while (!heap.isEmpty()) {
            ListNode min = heap.poll();
            curr.next = min;
            curr = curr.next;
            if (min.next != null) heap.offer(min.next);
        }

        return dummy.next;
    }
}

⏱ Complexity (Heap Version)

Time Complexity: O(N log k)
- N = total number of nodes
- k = number of lists
Space Complexity: O(k) for the heap

💡 Approach 2: Divide and Conquer

Merge lists in pairs, just like how merge sort works.

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;

        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);

        return mergeTwoLists(l1, l2);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), 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;
    }
}

⏱ Complexity (Divide & Conquer)

Time Complexity: O(N log k)
Space Complexity: O(log k) due to recursion

✍️ Summary

PriorityQueue approach is clean and uses a heap to track minimums.
Divide & conquer approach is elegant and more space-efficient.
Mastering this helps with:
- lc-148 (Sort List)
- lc-21 (Merge 2 Sorted Lists)
- lc-218 (The Skyline Problem — heap merge concept)

Efficient merging is a key skill when working with linked lists and sorted data.

Algorithm-Day34-Sort-List-lc-148

Posted on 2025-07-30 In Algorithms , Linked List

🧩 Problem Description

Given the head of a linked list, return the list sorted in ascending order.

You must sort in O(n log n) time and use constant space complexity (no array conversion).

💬 Example

1 2	Input: head = [4,2,1,3] Output: [1,2,3,4]

💡 Intuition

We cannot use extra space like arrays. So we apply merge sort on the linked list itself:

Split the list into halves using the slow/fast pointer technique
Recursively sort each half
Merge the two sorted halves (like in lc-21)

This gives us O(n log n) time and uses O(1) extra space for list nodes.

🔢 Java Code (Top-Down Merge Sort)

class Solution {
    public ListNode sortList(ListNode head) {
        // Base case
        if (head == null || head.next == null) return head;

        // Step 1: Split list into halves
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next;
        slow.next = null;

        // Step 2: Recursively sort each half
        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        // Step 3: Merge sorted halves
        return merge(left, right);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), 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 and Space Complexity

Time Complexity: O(n log n)
Space Complexity: O(log n) due to recursion stack (not extra list memory)

✍️ Summary

Use top-down merge sort directly on the list.
Core techniques:
- Fast/slow pointer to find middle
- Recursive divide-and-conquer
- Merging two sorted linked lists
Efficient, in-place sorting without using arrays

Make sure you’ve mastered lc-21 (merge two sorted lists) before this one — it’s the foundation of merging steps here.

Algorithm-Day33-Copy-List-with-Random-Pointer-lc-138

Posted on 2025-07-29 In Algorithms , Linked List

🧩 Problem Description

A linked list is given where each node has two pointers:

next: points to the next node
random: can point to any node in the list or be null

Return a deep copy of the list.

Each node in the new list must have the same value and the same random structure — but must be a new node, not shared.

💬 Example

Input:
Node1: val = 7, next = Node2, random = null
Node2: val = 13, next = Node3, random = Node1
...

Output:
Deep copy of the above structure

💡 Approach 1: HashMap Mapping (Straightforward)

✨ Idea

Traverse original list, and use a HashMap<OldNode, NewNode> to:
- Store the mapping between original nodes and copied ones
- After building the copy, set the next and random pointers

🔢 Java Code (Using HashMap)

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        Map<Node, Node> map = new HashMap<>();

        // Step 1: Create all nodes and store mapping
        Node curr = head;
        while (curr != null) {
            map.put(curr, new Node(curr.val));
            curr = curr.next;
        }

        // Step 2: Assign next and random pointers
        curr = head;
        while (curr != null) {
            Node copy = map.get(curr);
            copy.next = map.get(curr.next);
            copy.random = map.get(curr.random);
            curr = curr.next;
        }

        return map.get(head);
    }
}

Time Complexity: O(n)
Space Complexity: O(n) — due to the map

💡 Approach 2: Interleaving Nodes (O(1) Extra Space)

✨ Key Idea

Clone each node and insert it right after the original:
- A → A' → B → B' → ...
Assign random pointers:
A'.random = A.random.next
Detach the new list from the original

🔢 Java Code (No Extra Space)

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        // Step 1: Clone and insert nodes
        Node curr = head;
        while (curr != null) {
            Node clone = new Node(curr.val);
            clone.next = curr.next;
            curr.next = clone;
            curr = clone.next;
        }

        // Step 2: Assign random pointers
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }

        // Step 3: Detach the clone list
        Node dummy = new Node(0);
        Node copyCurr = dummy;
        curr = head;

        while (curr != null) {
            Node clone = curr.next;
            copyCurr.next = clone;
            copyCurr = clone;

            curr.next = clone.next;  // Restore original list
            curr = curr.next;
        }

        return dummy.next;
    }
}

Time Complexity: O(n)
Space Complexity: O(1)

✍️ Summary

Understand how to maintain relationships with .random using either:
- Hash map mapping (O(n) space)
- Interleaved list strategy (O(1) space)
This is a deep copy problem with pointer manipulation — commonly tested in interviews

Practice building clones of linked structures while preserving complex references. This is a great test of both logic and implementation skill.

Algorithm-Day32-Reverse-Nodes-in-Group-lc-25

Posted on 2025-07-28 In Algorithms , Linked List

🧩 Problem Description

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

Nodes that remain fewer than k at the end should remain in order.
You may not alter the values in the list’s nodes — only node pointers may be changed.

💬 Example

1 2	Input: head = [1,2,3,4,5], k = 3 Output: [3,2,1,4,5]

💡 Intuition

This is an extension of basic linked list reversal.

Reversing k nodes at a time → similar to lc-206, but in segments.
Key steps:
1. Check if at least k nodes remain.
2. Reverse k nodes.
3. Recurse or loop to the next k-group.

✅ Use a helper function to reverse a portion of the list.

🔢 Java Code (Recursive)

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode curr = head;
        int count = 0;

        // Step 1: Check if we have at least k nodes
        while (curr != null && count < k) {
            curr = curr.next;
            count++;
        }

        if (count < k) return head;

        // Step 2: Reverse k nodes
        ListNode prev = null;
        curr = head;
        for (int i = 0; i < k; i++) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // Step 3: Recursively reverse next k group
        head.next = reverseKGroup(curr, k);

        return prev;
    }
}

🔁 Java Code (Iterative with Dummy Node)

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode prevGroupEnd = dummy;

        while (true) {
            ListNode kth = getKthNode(prevGroupEnd, k);
            if (kth == null) break;

            ListNode groupStart = prevGroupEnd.next;
            ListNode nextGroupStart = kth.next;

            // Reverse current k-group
            ListNode prev = kth.next, curr = groupStart;
            while (curr != nextGroupStart) {
                ListNode tmp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = tmp;
            }

            // Connect with previous part
            prevGroupEnd.next = kth;
            prevGroupEnd = groupStart;
        }

        return dummy.next;
    }

    private ListNode getKthNode(ListNode curr, int k) {
        while (curr != null && k > 0) {
            curr = curr.next;
            k--;
        }
        return curr;
    }
}

⏱ Time and Space Complexity

Time Complexity: O(n), each node is visited once
Space Complexity:
- Recursive: O(n/k) recursion stack
- Iterative: O(1)

✍️ Summary

Advanced linked list problem — combines segment reversal, pointer manipulation, and recursion/looping.
You must understand lc-206 (reverse linked list) first.
Mastering this problem improves your skill with pointer operations.

Start from simpler problems like lc-24, then build up to this level. Great interview question!

Algorithm-Day31-Swap-Nodes-in-Pairs-lc-24

Posted on 2025-07-27 In Algorithms , Linked List

🧩 Problem Description

Given the head of a linked list, swap every two adjacent nodes and return its head.

You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

💬 Example

1 2	Input: head = [1,2,3,4] Output: [2,1,4,3]

💡 Intuition

This is a classic linked list node manipulation problem.

Use a dummy node to simplify edge cases.
Iterate through the list in pairs.
For each pair:
- Update pointers to swap the two nodes.
- Move to the next pair.

🔢 Java Code (Iterative)

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode curr = dummy;

        while (curr.next != null && curr.next.next != null) {
            ListNode first = curr.next;
            ListNode second = curr.next.next;

            // Swapping nodes
            first.next = second.next;
            second.next = first;
            curr.next = second;

            // Move to next pair
            curr = first;
        }

        return dummy.next;
    }
}

🔁 Java Code (Recursive)

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode first = head;
        ListNode second = head.next;

        first.next = swapPairs(second.next);
        second.next = first;

        return second;
    }
}

⏱ Time and Space Complexity

Time Complexity: O(n), where n is the number of nodes
Space Complexity:
- Iterative: O(1)
- Recursive: O(n) due to recursion stack

✍️ Summary

Good test of pointer manipulation in linked lists.
Practice both iterative and recursive approaches.
Understanding node-level swaps is essential for problems like:
- lc-25: Reverse Nodes in k-Group
- lc-92: Reverse Linked List II

Dummy nodes make linked list problems so much easier — use them!

Algorithm-Day30-Remove-Nth-Node-From-End-of-List-lc-19

Posted on 2025-07-26 In Algorithms , Linked List

🧩 Problem Description

Given the head of a linked list, remove the n-th node from the end of the list and return its head.

💬 Example

1 2	Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

💡 Intuition

Use the two-pointer technique:

Move first pointer n steps ahead.
Then move both first and second together until first reaches the end.
Now second is just before the node to delete.

✅ Trick: use a dummy node before head to simplify edge cases like deleting the head.

🔢 Java Code

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = dummy;
        ListNode second = dummy;

        // Move first n+1 steps to maintain gap
        for (int i = 0; i <= n; i++) {
            first = first.next;
        }

        // Move both pointers
        while (first != null) {
            first = first.next;
            second = second.next;
        }

        // Skip the target node
        second.next = second.next.next;

        return dummy.next;
    }
}

⏱ Time and Space Complexity

Time Complexity: O(L), where L is the length of the list
Space Complexity: O(1)

✍️ Summary

Two-pointer pattern is super useful for problems involving relative positions.
Using a dummy node helps avoid corner-case bugs when deleting the head.
This technique appears frequently — make sure you’re confident with it.

Similar problems include:

lc-876: Middle of the Linked List

lc-160: Intersection of Two Linked Lists

lc-234: Palindrome Linked List

Algorithm-Day29-Divide-Two-Integers-lc-29

Posted on 2025-07-25 Edited on 2025-07-24 In Algorithms , Bit Manipulation

🧩 Problem Description

Given two integers dividend and divisor, divide them without using multiplication, division, or mod operator.

Return the quotient after dividing dividend by divisor.

The result should be truncated toward zero (i.e., 8.9 → 8, -8.9 → -8).

💬 Example

Input: dividend = 10, divisor = 3
Output: 3

Input: dividend = 7, divisor = -3
Output: -2

⚠️ Constraints

You must not use *, /, or %.
Range of inputs: -2³¹ ≤ dividend, divisor ≤ 2³¹ - 1
If result overflows (> 2³¹ - 1), return 2³¹ - 1

💡 Intuition

To simulate division:

Keep subtracting the divisor from dividend until the dividend is smaller than divisor.
To speed up, use bit shifting (double the divisor each time).

This is like long division: find the largest multiple of divisor that fits in dividend.

🔢 Java Code (Bit Manipulation)

class Solution {
    public int divide(int dividend, int divisor) {
        // Edge case: overflow
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;

        // Use long to prevent overflow during shifting
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);
        int result = 0;

        while (a >= b) {
            long temp = b;
            int multiple = 1;
            while (a >= (temp << 1)) {
                temp <<= 1;
                multiple <<= 1;
            }
            a -= temp;
            result += multiple;
        }

        // Determine sign
        return (dividend > 0) == (divisor > 0) ? result : -result;
    }
}

⏱ Time and Space Complexity

Time Complexity: O(log N) — where N is |dividend|
Space Complexity: O(1)

✍️ Summary

No multiplication, division, or modulus — use bit shifts and subtraction.
Carefully handle:
- Negative numbers
- Edge cases like Integer.MIN_VALUE / -1
This is a good exercise in low-level arithmetic logic.

Learn this if you want to understand how division could be implemented in systems without direct hardware division support.

Algorithm-Day28-Add-Two-Numbers-lc-2

Posted on 2025-07-24 In Algorithms , Linked List

🧩 Problem Description

You are given two non-empty linked lists representing two non-negative integers.
The digits are stored in reverse order, and each node contains a single digit.

Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

💬 Example

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]

Explanation:
342 + 465 = 807

💡 Intuition

Since the numbers are stored in reverse, we can simulate digit-by-digit addition like grade school.
Maintain a carry variable for overflow.
Traverse both lists and construct the result list.

🔢 Java Code

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);  // Dummy head
        ListNode curr = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry > 0) {
            int sum = carry;

            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }

            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
        }

        return dummy.next;
    }
}

⏱ Time and Space Complexity

Time Complexity: O(max(n, m)) — traverses both lists once
Space Complexity: O(max(n, m)) — result list size

✍️ Summary

This is a classic linked list and math simulation problem.
Be comfortable managing carry and dummy nodes.
Appears frequently in interviews and serves as a great test of logic + list handling.

For follow-ups, consider:

BigInteger usage (if languages allow)

Lists in forward order (lc-445)