thread category Thread - DSA Grind

#dsa #java #old-post
Last updated: 03/11/2024
Written by: Yuk 
Thread info: Last updated: 03-11-2024
    - 03-11-2024:   LeetCode - 796. Rotate String
                    LeetCode - 141. Linked List Cycle
                    LeetCode - 206. Reverse Linked List
                    LeetCode - 20. Valid Parentheses

LeetCode

LeetCode - 796. Rotate String

class Solution {
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) {
            return false;
        }
        return (s + s).contains(goal);
    }
}
  • Base case: length mismatch -> False
  • Examples:
    • “abc” and “cab” -> “abcabc” contains “cab” -> True
    • “abc” and “acb” -> “abcabc” -> False
  • Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)
    • Best-case: Length mismatch -> False -> \(\Omega(1)\)
    • contains of java String is \(O(n)\)
  • Space complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)
    • Concatenation (s + s) takes \(O(n)\) space

LeetCode - 141. Linked List Cycle

class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

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

            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
}
  • Reference: G4G - Floyd’s Cycle Finding Algorithm
  • Essentially a fancy way to check all nodes and all distances
  • Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)
    • No cycle -> \(O(n)\)
    • Best case for edge cases like only 1 node or null -> \(\Omega(1)\)
  • Space complexity: \(O(1) \mid \Omega(1) \mid \Theta(1)\)

LeetCode - 206. Reverse Linked List

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

        while (head != null) {
            ListNode temp = head.next;
            head.next = node;
            node = head;
            head = temp;
        }
        return node;
    }
}
  • Example:
head ↴
   ( 1 ) -> ( 2 ) -> ( 3 ) -> null

  head → temp ↴
   ( 1 )    ( 2 ) -> ( 3 ) -> null
     ↑
   node

   ( 1 ) <- ( 2 )    ( 3 ) -> null
     ↑        ↑
   node     head

           head → temp ↴
   ( 1 ) <- ( 2 )    ( 3 ) -> null
              ↑
            node

                   head → temp ↴
   ( 1 ) <- ( 2 ) <- ( 3 )    null
                       ↑
                     node
  • Basically just jolt it down on paper, nice that it doesn’t have any edge cases.
  • Time complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)
  • Space complexity: \(O(1) \mid \Omega(1) \mid \Theta(1)\)

LeetCode - 20. Valid Parentheses

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> mapping = new HashMap<>();
        mapping.put(')', '(');
        mapping.put('}', '{');
        mapping.put(']', '[');

        for (char c : s.toCharArray()) {
            if (mapping.containsValue(c)) {
                stack.push(c);
            } else if (mapping.containsKey(c)) {
                if (stack.isEmpty() || mapping.get(c) != stack.pop()) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}
  • There are a lot of edge cases with this problem, just make sure you go through them all if you want to justify the solution above.
  • Time complexity: \(O(n) \mid \Omega(n) \mid \Theta(n)\)
  • Space complexity: \(O(n) \mid \Omega(1) \mid \Theta(n)\)
    • You may use explicit string matching but the HashMap here is relatively irrelevant compared to the core Stack usage of the algorithm itself.