SvenStack

🧩 Problem Description

Given the head of a singly linked list, reverse the list and return the new head.

Example:

1
2

Input: 1 → 2 → 3 → 4 → 5
Output: 5 → 4 → 3 → 2 → 1

💡 Brute Force (Not In-Place)

• Store values in an array or stack, then rebuild the list.
• ❌ Not optimal — uses extra space.

💡 Optimal Approach: Iterative In-Place Reversal

✨ Key Idea

• Use 3 pointers:
  • prev to track the previous node.
  • curr as the current node.
  • next to temporarily hold curr.next.

At each step:

• Reverse the link: curr.next = prev
• Move forward

🔢 Java Code (Iterative)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        return prev;
    }
}

🔁 Java Code (Recursive)

1
2
3
4
5
6
7
8
9
10
11

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

        ListNode reversed = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return reversed;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity:
  • Iterative: O(1)
  • Recursive: O(n) (due to recursion stack)

✍️ Summary

• This is a fundamental linked list pattern — useful in many real problems (e.g., palindrome check, list reordering).
• Understand both iterative and recursive versions.

Learn it well — this reversal logic appears often in interviews and linked list puzzles.

🧩 Problem Description

Given the heads of two singly linked lists headA and headB, return the node at which the two lists intersect.
If the two linked lists have no intersection at all, return null.

The linked lists must retain their original structure after the function returns.

Example:

1
2
3
4

Input:
A: 4 → 1 → 8 → 4 → 5
B: 5 → 6 → 1 → 8 → 4 → 5
Output: Reference to node with value 8

💡 Brute Force (Not Ideal)

• Compare every node from headA with every node from headB.
• Time: O(m × n)
• ❌ Inefficient

💡 Optimal Approach: Two Pointers

✨ Key Idea

• Use two pointers pA and pB.
• Traverse both lists:
  • If pA reaches end, redirect it to headB.
  • If pB reaches end, redirect it to headA.
• They will either meet at the intersection node or both become null (no intersection).

Why it works:

• Both pointers traverse exactly m + n steps.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode pA = headA;
        ListNode pB = headB;

        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }

        return pA;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(m + n)
• Space Complexity: O(1)

✍️ Summary

• This is a textbook two-pointer technique for linked lists.
• Avoids using extra space like hash sets.
• Useful for related problems such as:
  • lc-142: Linked List Cycle II
  • lc-21: Merge Two Sorted Lists

Pointer redirection is a simple yet powerful technique when dealing with linked lists of unequal lengths.

🧩 Problem Description

Write an efficient algorithm that searches for a value in an m x n matrix.

This matrix has the following properties:

• Integers in each row are sorted in ascending order.
• Integers in each column are sorted in ascending order.

Example:

1
2
3
4
5
6
7
8
9

Input: matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
], target = 5

Output: true

💡 Naive Approach (Not Ideal)

• Scan the whole matrix: O(m × n) time.
• ❌ Not efficient considering the sorted properties.

💡 Optimal Approach: Search from Top-Right Corner

✨ Key Idea

• Start from the top-right cell.
• At each step:
  • If the value is equal to target, return true.
  • If the value is greater than target, move left.
  • If the value is less than target, move down.
• Why it works:
  • Rows increase left → right.
  • Columns increase top → bottom.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int m = matrix.length;
        int n = matrix[0].length;

        int row = 0;
        int col = n - 1;

        while (row < m && col >= 0) {
            int val = matrix[row][col];
            if (val == target) {
                return true;
            } else if (val > target) {
                col--;
            } else {
                row++;
            }
        }

        return false;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(m + n)
  Worst case: we move from top-right to bottom-left.
• Space Complexity: O(1)
  No extra space used.

✍️ Summary

• The staircase search pattern is a must-know technique for sorted 2D matrices.
• It’s more efficient than binary search on each row or column separately.
• Similar sorted matrix problems:
  • lc-74 (Search a 2D Matrix)
  • lc-378 (Kth Smallest Element in a Sorted Matrix)

When rows and columns are sorted, think about combining row and column movement strategies instead of brute force search.

🧩 Problem Description

You are given an n x n 2D matrix representing an image. Rotate the image 90 degrees clockwise.

You must rotate the image in place.

Example:

1
2

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

💡 Brute Force Approach (Not Allowed)

• Create a new matrix and write rotated values into it.
• ❌ Uses O(n²) extra space, violates “in-place” requirement.

💡 Optimal Approach: Transpose + Reverse

✨ Key Idea

1. Transpose the matrix:
   • Swap matrix[i][j] with matrix[j][i] for all i < j.
2. Reverse each row.

This combination achieves a 90-degree clockwise rotation in place.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // Step 1: Transpose
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // Step 2: Reverse each row
        for (int i = 0; i < n; i++) {
            reverseRow(matrix[i]);
        }
    }

    private void reverseRow(int[] row) {
        int left = 0, right = row.length - 1;
        while (left < right) {
            int temp = row[left];
            row[left] = row[right];
            row[right] = temp;
            left++;
            right--;
        }
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n²)
  Each element is processed twice (transpose + reverse).
• Space Complexity: O(1)
  Fully in-place.

✍️ Summary

• The transpose + reverse method is an elegant solution for in-place rotation problems.
• Remember:
  • Clockwise → transpose + reverse rows
  • Counterclockwise → transpose + reverse columns
• This is a core pattern in matrix transformation problems.

Mastering in-place matrix tricks helps with both interviews and real-world image manipulation tasks.

🧩 Problem Description

Given an m x n matrix, return all elements of the matrix in spiral order.

Example:

1
2

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

💡 Approach: Layer-by-Layer Traversal

✨ Key Idea

We maintain four boundaries:

• top, bottom, left, right

At each step:

1. Traverse from left to right along top.
2. Traverse from top + 1 to bottom along right.
3. Traverse from right - 1 to left along bottom (only if top < bottom).
4. Traverse from bottom - 1 to top + 1 along left (only if left < right).

After each step, we shrink the boundaries inward.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

import java.util.*;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();

        if (matrix == null || matrix.length == 0) return result;

        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;

        while (top <= bottom && left <= right) {
            // Traverse from left to right
            for (int j = left; j <= right; j++) {
                result.add(matrix[top][j]);
            }
            top++;

            // Traverse from top to bottom
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--;

            if (top <= bottom) {
                // Traverse from right to left
                for (int j = right; j >= left; j--) {
                    result.add(matrix[bottom][j]);
                }
                bottom--;
            }

            if (left <= right) {
                // Traverse from bottom to top
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }

        return result;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(m × n)
  Each cell is visited exactly once.
• Space Complexity: O(1) extra space
  (excluding output list)

✍️ Summary

• Boundary shrinking is a classic matrix traversal technique.
• Spiral order appears in related problems like Spiral Matrix II (filling numbers), lc-59.
• Make sure to check conditions carefully when shrinking boundaries to avoid duplicates.

Matrix traversal patterns (row-wise, column-wise, spiral, zigzag) are common interview topics — good to master!

🧩 Problem Description

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0.
You must do it in place.

Example:

1
2

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

💡 Brute Force (Not Ideal)

• Mark all rows and columns with zeros using extra sets.
• Time: O(m × n)
• Space: O(m + n) → uses extra memory, not fully in-place.

💡 Optimal Approach: Constant Space Using First Row and Column

✨ Key Idea

• Use the first row and first column as markers for rows and columns that need to be zeroed.
• Two passes:
  1. Mark rows/columns.
  2. Set cells to zero based on markers.
• Special care is needed for handling the first row and column separately.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean firstRowZero = false;
        boolean firstColZero = false;

        // Check if first row needs to be zeroed
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }

        // Check if first column needs to be zeroed
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }

        // Use first row and column as markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // Zero cells based on markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Zero first row if needed
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }

        // Zero first column if needed
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(m × n)
  Two passes over the matrix.
• Space Complexity: O(1)
  No extra space beyond the matrix itself.

✍️ Summary

• Smart use of the matrix itself as storage avoids extra space usage.
• Watch out for the first row and first column edge cases.
• Similar in-place patterns appear in other matrix transformation problems.

Learning how to reuse input space for flags is a useful technique in constrained-space algorithm design.

🧩 Problem Description

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example:

1
2

Input: nums = [3,4,-1,1]
Output: 2

💡 Brute Force (Not Acceptable)

• Sort the array → O(n log n)
• Check for the first missing positive
• ❌ Not allowed by problem constraints

💡 Optimal Approach: Index Placement (Cyclic Sort Pattern)

✨ Key Idea

• If nums[i] is in range [1, n], ideally it should be placed at nums[nums[i] - 1].
• Swap elements until every number is placed correctly.
• Then scan once to find the first index i where nums[i] != i + 1.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                // Swap nums[i] with nums[nums[i] - 1]
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
  Each number is swapped at most once.
• Space Complexity: O(1)
  In-place swaps only.

✍️ Summary

• This is a textbook application of the cyclic sort pattern.
• Focus on the fact that only numbers within [1, n] matter.
• Understand why O(n) solutions are possible by leveraging in-place swaps.

Problems like this appear often in data structure interviews where array indexing and in-place manipulation are tested.

🧩 Problem Description

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The algorithm must run in O(n) time and without using division.

Example:

1
2

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

💡 Brute Force (Not Acceptable)

For each index, multiply all other elements:

• Time: O(n²)
• ❌ Not efficient for large inputs

💡 Optimal Approach: Prefix Product + Suffix Product

✨ Key Idea

We calculate:

• prefix[i]: product of all elements before index i
• suffix[i]: product of all elements after index i

Then:
answer[i] = prefix[i] * suffix[i]

But we can optimize to use only one output array.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];

        // Step 1: Left products
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }

        // Step 2: Right products (suffix) and multiply on the fly
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] = answer[i] * right;
            right *= nums[i];
        }

        return answer;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
  Two passes over the array.
• Space Complexity: O(1) extra space (output array does not count as extra space in the problem statement)

✍️ Summary

• This is a classic prefix + suffix product pattern.
• No division is used.
• Space-optimized by combining both steps into a single result array.

Learning this approach helps with problems involving “all elements except…” patterns, such as sum, XOR, or custom aggregates.

🧩 Problem Description

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example:

1
2

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]

💡 Naive Approach (Extra Array)

• Copy elements into a new array

• Place each element at (i + k) % n index

• Copy back to nums

• ✅ Works

• ❌ Uses O(n) extra space

💡 Optimal Approach: Reverse Method

🧠 Key Idea

1. Reverse the whole array
2. Reverse the first k elements
3. Reverse the remaining n - k elements

✅ Why It Works

Reversing segments restores them into rotated order.

🔢 Java Code

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;  // Handle k >= n

        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)
  In-place rotation using reversals

✍️ Summary

• This problem demonstrates an important array manipulation pattern.
• The reverse trick is efficient and widely applicable in other rotation-related problems.
• Avoid extra space when possible by reusing in-place algorithms.

Understand both the logic and implementation of reverse-in-place operations — this comes up in multiple array and string questions!

🧩 Problem Description

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example:

1
2

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

💡 Brute Force? Not Ideal

You could check every pair and try to merge, but:

• You would need to compare all combinations
• ❌ Time complexity is too high (O(n²) or worse)

💡 Optimal Approach: Sort + Merge

✨ Key Idea

1. Sort the intervals by start time
2. Iterate through intervals:
   • If the current interval overlaps with the previous one, merge them
   • Otherwise, add the previous interval to result

This approach ensures that we process all intervals in a linear scan after sorting.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;

        // Step 1: Sort intervals by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> result = new ArrayList<>();

        int[] current = intervals[0];

        for (int i = 1; i < intervals.length; i++) {
            int[] next = intervals[i];

            if (current[1] >= next[0]) {
                // Merge overlapping intervals
                current[1] = Math.max(current[1], next[1]);
            } else {
                result.add(current);
                current = next;
            }
        }

        result.add(current); // Add the last interval

        return result.toArray(new int[result.size()][]);
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n log n)
  For sorting the intervals
• Space Complexity: O(n)
  For the result list (output), auxiliary space is constant

✍️ Summary

• This is a classic sort-then-scan problem
• Make sure to handle edge cases like fully nested intervals (e.g., [1,10], [2,5])
• Very common pattern in scheduling, calendar, and timeline problems

Sorting followed by greedy merging is a powerful approach for interval problems.