DEV Community: Giuseppe

LeetCode #238. Product of Array Except Self

Giuseppe — Sat, 07 Feb 2026 14:40:38 +0000

1.Solution with division

Time Complexity O(n)

First loop iterates through all n elements once to calculate the product and count zeros
Second loop iterates through all n elements once to populate the result array
Total: O(n) + O(n) = O(n)

Space Complexity

O(1) auxiliary space: Only uses a constant amount of extra variables (zeroCount, product, i).
The space complexity is typically considered O(1) since the output array doesn't count as extra space (it's required by the problem), and no additional space proportional to input size is used.

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

        int zeroCount = 0;
        int product = 1;

        for (int num : nums) {
            if (num == 0)
                zeroCount++;
            else 
                product *= num;
        }

        for (int i = 0; i < n; i++) {
            if (zeroCount > 1)
                result[i] = 0;
            if (zeroCount == 1)
                result[i] = (nums[i] == 0) ? product : 0;
            else 
                result[i] = product / nums[i];
        }

        return result;
    }
}

2.Solution without division

Time Complexity: O(n)

You do two linear passes over the array:

Prefix pass (left → right)
Suffix pass (right → left)

Each element is processed a constant number of times.
O(n) + O(n) = O(n)

Space Complexity: O(1)

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

        // prefix product
        result[0] = 1;
        for (int i = 1; i <nums.length; i++) {
            result[i] = result[i - 1] * nums[i - 1]; 
        }

        // suffix product
        int suffix = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            result[i] *= suffix;
            suffix *= nums[i];
        }
        return result;    
    }
}

LeetCode #271. Encode and Decode Strings

Giuseppe — Sat, 31 Jan 2026 16:56:28 +0000

Time Complexity: O(n)

for encoding:

Each character of each string is appended once
StringBuilder.append() is amortized O(1) per char
Total work = proportional to total characters

for decoding:

Pointer i only moves forward
Each character is visited a constant number of times
No backtracking or nested re-scanning

Space Complexity: O(n)

You must store:

encoded string (encode)
decoded list of strings (decode)

That’s O(n) by necessity

Extra (auxiliary) space

Only a few integers and pointers → O(1)

class Solution {

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();

        for (String s : strs) {
            sb.append(s.length())
              .append("#")
              .append(s);
        }
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        //create a list of String to return tthe result
        List<String> result = new ArrayList<>();
        // overall string pointer
        int i = 0;

        while (i < s.length()) {
            // pointer to find the delimiter '#'
            int j = i;
            while (s.charAt(j) != '#') {
                j++;
            }

            // parse length
            int length = Integer.parseInt(s.substring(i, j));

            // extract string
            String str = s.substring(j + 1, j + 1 + length);
            result.add(str);

            // move pointer
            i = j + 1 + length;
        }

        return result;
    }
}

LeetCode #347. Top K Frequent Element

Giuseppe — Sat, 31 Jan 2026 09:49:38 +0000

Time Complexity: O(n log n) dominated by sorting

Space Complexity: O(n) for the HashMap and List

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) +1);
        }

        List<Integer> list = new ArrayList<>(map.keySet());
        list.sort((a,b) -> Integer.compare(map.get(b), map.get(a)));

        int[] result = new int[k];
        for (int i = 0; i < k; i++){
            result[i] = list.get(i);
        }
        return result;
    }
}

LeetCode #647. Palindromic Substrings

Giuseppe — Tue, 02 Dec 2025 09:53:37 +0000

Brute force solution

Time Complexity: 0(n^3)

Space Complexity: O(1)

class Solution {
    public int countSubstrings(String s) {
        int count = 0;

        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++){
                if (isPalindrome(s, i, j)) {
                    count++;
                }
            }
        }
        return count;

    }

    public boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) return false;

            start++;
            end--;
        }
        return true;
    }
}

LeetCode #98.Validate Binary Search Tree

Giuseppe — Wed, 26 Nov 2025 11:54:53 +0000

Time Complexity: O(n)

We visit every node exactly once
At each node, we do constant work (a few comparisons)
So total work = O(n) where n = number of nodes

Space Complexity: O(h) → where h = height of the tree

This comes from the recursion stack (call stack).
Best case: O(log n)
→ Balanced tree (height ≈ log n)
→ Maximum stack depth = log n
Worst case: O(n)
→ Completely skewed tree (like a linked list)
→ Stack depth = n (all nodes on one side)

class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }

    private boolean helper(TreeNode node, Integer lower, Integer upper) {
        // Empty tree is valid
        if (node == null) {
            return true;
        }

        // Check bounds
        if (lower != null && node.val <= lower) return false;
        if (upper != null && node.val >= upper) return false;

        // Left subtree: all values must be < node.val  → tighten the upper bound
        // Right subtree: all values must be > node.val → tighten the lower bound
        if (!helper(node.left, lower, node.val)) return false;
        if (!helper(node.right, node.val, upper)) return false;

        return true;

    }
}

LeetCode #104. Maximum Depth of Binary Tree

Giuseppe — Wed, 19 Nov 2025 15:15:25 +0000

Time Complexity: O(n)

The function visits every node in the tree exactly once, where n is the total number of nodes. Each visit performs constant-time operations (comparison and addition), so the overall time complexity is linear.

Space Complexity: O(h)

h = height of the tree (maximum depth)
Best case (balanced tree): O(log n)

A perfectly balanced tree has height ≈ log₂(n).
So the deepest recursion chain is log(n) → stack size O(log n).

Worst case (skewed tree): O(n)

If each node only has one child (linked-list shape):
height = n
→ recursion stack size = n
→ O(n).

Average case: O(log n)

Random/typical trees tend to be reasonably balanced, so expected height ≈ log n.

Classic recursive problem because the depth of a tree is naturally defined in terms of the depths of its subtrees.

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        return Math.max(leftDepth, rightDepth) + 1;
    }
}

We recursively calculate the maximum depth of the left subtree and the right subtree:

int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);

As long as a node has children, the recursive calls continue deeper into the tree, and the current function cannot execute its return statement yet because it is waiting for the recursive results.

Once we reach a leaf node, its .left and .right are null, so the recursive calls hit the base case:

if (root == null) return 0;

At this point, the recursion starts returning upward (unwinding the call stack), and each node can finally execute:

return Math.max(leftDepth, rightDepth) + 1;

So:
Recursion goes down until null, then the return statements execute while coming back up.

LeetCode #19. Remove nth Node from End of List

Giuseppe — Wed, 19 Nov 2025 10:46:36 +0000

Space Complexity: O(1)

Time Complexity: O(n)

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode dummy = new ListNode();
        dummy.next = head;

        ListNode slow = dummy;
        ListNode fast = dummy;

        // advance fast node till the nth node
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // advance both nodes till fast != null
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // slow now is at the node before the node that has to be deleted
        // bypass the nth node that be to be deleted
        // so we just do not reference that node anymore
        slow.next = slow.next.next;

        return dummy.next;
    }
}

LeetCode #141. Linked List Cycle

Giuseppe — Mon, 10 Nov 2025 11:39:54 +0000

Time Complexity: O(n)

Space Complexity: O(1)

public class Solution {
    public boolean hasCycle(ListNode head) {

         if (head == null || head.next == null) {
            return false;
        }

        // Initialize two pointers
        ListNode slow = head;
        ListNode fast = head;

        // Move pointers until they meet or fast reaches end
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            // If pointers meet, there's a cycle
            if (slow == fast) {
                return true;
            }
        }

        // Fast pointer reached end, no cycle
        return false;

    }
}

LeetCode #234. Palindrome Linked List

Giuseppe — Fri, 07 Nov 2025 11:39:06 +0000

Time Complexity: O(n)

Space Complexity: O(1)

class Solution {
    public boolean isPalindrome(ListNode head) {
        // trivially palindrome
        if (head == null || head.next == null) return true;

        // Find middle
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // If odd length, skip the middle node
        // because in the odd case the middle node is not relevant for nowing if a list is palindrome
        if (fast != null) slow = slow.next;

        // Reverse second half
        ListNode second = reverse(slow);

        // Compare halves
        ListNode p1 = head;
        ListNode p2 = second;
        boolean ok = true;
        while (p2 != null) {
            if (p1.val != p2.val) { 
                ok = false; 
                break; 
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        return ok;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

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

LeetCode #2. Add Two Numbers

Giuseppe — Thu, 30 Oct 2025 08:19:49 +0000

Time Complexity: O(n)

Space Complexity: O(1)

Total space (including result list): O(n)

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 

        ListNode dummy = new ListNode();
        ListNode current = dummy;
        int carry = 0;

        // Continue looping as long as there’s at least one more digit to process or a carry to handle.
        while (l1 != null || l2 != null || carry != 0) {
            // extract the values (if node exists, else 0)
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;

            // compute total sum with carry
            int sum = val1 + val2 + carry;

            // determine next carry and current digit
            carry = sum / 10;
            int digit = sum % 10;

            // create new node with the digit and attach
            current.next = new ListNode(digit);
            current = current.next;

            // move input pointers forward
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;

        }  

        return dummy.next;   
    }
}

LeetCode #206. Reverse Linked List

Giuseppe — Wed, 29 Oct 2025 11:25:49 +0000

Time Complexity: O(n)

Space Complexity: O(1)

class Solution {
    public ListNode reverseList(ListNode head) {

        // these variables are references, not copies of the node itself
        // so we are not using them as copies of the nodes, but as references (pointers)
        ListNode previous = null;
        ListNode current = head;
        ListNode next = null;

        while (current != null) {

            next = current.next; // save next
            current.next = previous; // reverse

            // advance previous & current
            previous = current; // previous points to the old current
            current = next; // current points to the old next
        }

        return previous; // new head at the end

    }
}

LeetCode #237. Delete node in a LinkedList.

Giuseppe — Mon, 27 Oct 2025 11:54:39 +0000

Time Complexity: O(1)

Copy the value from the next node: node.val = node.next.val
Update the pointer to skip the next node: node.next = node.next.next

No loops, no recursion, no operations that depend on the size of the linked list. It always takes the same amount of time.

We're not actually deleting the node we were given. Instead, we're:

Overwriting its value with the next node's value
Bypassing the next node by updating the pointer to skip over it

So if we have: 1 -> [2] -> 3 -> 4 (delete node with value 2)
After the operation: 1 -> [3] -> 4
The node object at the second position still exists in memory at the same location, but now it:

Contains the value 3 (copied from the next node)
Points directly to the node with value 4

The original "node 3" is now orphaned (no references to it), so it becomes eligible for garbage collection.

Space Complexity: O(1)

class Solution {
    public void deleteNode(ListNode node) {

        node.val = node.next.val;
        node.next = node.next.next;

    }
}