Ordered_Set_Tutorial.txt

Ordered Set
===========

- Introduction:
===============

    An Ordered Set is a data structure that combines the features of both sets and lists. Here are the key characteristics:

    1. Unique Elements: Like a traditional set, an ordered set ensures that all elements are unique. There are no duplicate elements.

    2. Order Preservation: Unlike a traditional set, which does not maintain any order of elements, an ordered set maintains
        the order of elements as they are inserted. This means that elements can be iterated over in the order they were added.

    * Implementation:
    -----------------

     Ordered sets can be implemented in various ways, including:

    - Linked Hash Sets: Use a hash table for fast membership checking and a linked list to maintain the order of elements.
    - Balanced Binary Search Trees: Use a tree structure to keep elements sorted. Examples include AVL trees, Red-Black trees, and B-trees.

    * Operations:
    --------------

        An ordered set typically supports the following operations:

        - Insertion: Adding an element while preserving order.
        - Deletion: Removing an element and maintaining order.
        - Membership Testing: Checking if an element is in the set.
        - Iteration: Iterating over elements in the order they were added.
        - Accessing Ordered Elements: Accessing the first or last element, or any other element based on their order.

    * Examples in Programming:
    --------------------------

    Different programming languages and libraries provide implementations of ordered sets. Some examples include:

    - Python: The `collections` module provides `OrderedDict`, which can be used to implement an ordered set. Python's
        `sortedcontainers` library also provides an `OrderedSet` implementation.
    - C++: The Standard Library includes `std::set` and `std::map`, but for an ordered set specifically, a combination
        of data structures or third-party libraries like `boost` may be used.
    - Java: The `LinkedHashSet` class in the Java Collections Framework is an implementation of an ordered set.

    * Use Cases:
    ------------

    Ordered sets are useful in scenarios where you need both uniqueness and order. Some examples include:

    - Caching: Where you need to keep track of the order of items for eviction policies.
    - Database Indexing: To maintain a set of unique keys in a specific order.
    - Event Handling: Where events need to be processed in the order they occurred, but duplicates are not allowed.

- Operations of Ordered Set data structure:
===========================================

    In Java, the LinkedHashSet class is commonly used to implement an ordered set. LinkedHashSet maintains a linked list
    of the entries in the set, in the order in which they were inserted, allowing iteration, deletion, membership testing
    in the insertion order. Here are the main operations of an Ordered Set using LinkedHashSet in Java:

    Let's go over the operations of an Ordered Set data structure in Java using `LinkedHashSet` and discuss the time and
    space complexity for each operation.

    1. Insertion:
    -------------
    Adding an element to a `LinkedHashSet`:

    orderedSet.add(element);

    - Time Complexity: O(1) on average. The underlying hash table allows for average constant-time performance for insertions.
    - Space Complexity: O(1) for each element added, considering the hash table and linked list overhead.

    2. Deletion:
    ------------
    Removing an element from a `LinkedHashSet`:

    orderedSet.remove(element);

    - Time Complexity: O(1) on average. The hash table allows for average constant-time performance for deletions.
    - Space Complexity: O(1) for each element removed.

    3. Membership Testing:
    ----------------------
    Checking if an element is in the `LinkedHashSet`:

    orderedSet.contains(element);

    - Time Complexity: O(1) on average. The hash table allows for average constant-time performance for lookups.
    - Space Complexity: O(1) per query.

    4. Iteration:
    --------------
    Iterating over the elements in the order they were added:

        for (Integer element : orderedSet) {
            System.out.println(element);
        }

    - Time Complexity: O(n), where n is the number of elements. Each element is visited once.
    - Space Complexity: O(1) for the iterator.

    5. Accessing Ordered Elements:
    ------------------------------
    Since `LinkedHashSet` does not provide direct access by index, you can convert it to a list to access elements by their insertion order:

        List<Integer> orderedList = new ArrayList<>(orderedSet);
        Integer firstElement = orderedList.get(0);
        Integer lastElement = orderedList.get(orderedList.size() - 1);

        - Time Complexity:
          - Conversion: O(n), where n is the number of elements.
          - Access by index: O(1).
        - Space Complexity: O(n) for storing the list of elements.

    6. Example Code:
    ----------------

    Here is a complete example demonstrating these operations along with their complexity considerations:

            import java.util.LinkedHashSet;
            import java.util.ArrayList;
            import java.util.List;

            public class OrderedSetExample {
                public static void main(String[] args) {
                    LinkedHashSet<Integer> orderedSet = new LinkedHashSet<>();

                    // Insertion
                    orderedSet.add(1); // O(1)
                    orderedSet.add(2); // O(1)
                    orderedSet.add(3); // O(1)
                    orderedSet.add(1); // Duplicate, O(1)

                    // Iteration
                    System.out.println("Ordered Set Elements:");
                    for (Integer element : orderedSet) { // O(n)
                        System.out.println(element);
                    }

                    // Membership Testing
                    boolean contains = orderedSet.contains(2); // O(1)
                    System.out.println("Set contains 2: " + contains);

                    // Size
                    int size = orderedSet.size(); // O(1)
                    System.out.println("Set size: " + size);

                    // Deletion
                    orderedSet.remove(2); // O(1)

                    // Iteration after Deletion
                    System.out.println("Ordered Set Elements after removal of 2:");
                    for (Integer element : orderedSet) { // O(n)
                        System.out.println(element);
                    }

                    // Accessing Ordered Elements
                    List<Integer> orderedList = new ArrayList<>(orderedSet); // O(n)
                    if (!orderedList.isEmpty()) {
                        Integer firstElement = orderedList.get(0); // O(1)
                        Integer lastElement = orderedList.get(orderedList.size() - 1); // O(1)
                        System.out.println("First element: " + firstElement);
                        System.out.println("Last element: " + lastElement);
                    }

                    // isEmpty
                    boolean isEmpty = orderedSet.isEmpty(); // O(1)
                    System.out.println("Set is empty: " + isEmpty);

                    // Clear
                    orderedSet.clear(); // O(n)
                    System.out.println("Set size after clear: " + orderedSet.size()); // O(1)
                }
            }

    6. Summary of Complexities:
    ---------------------------

        - Insertion: O(1) time, O(1) space per element.
        - Deletion: O(1) time, O(1) space per element.
        - Membership Testing: O(1) time, O(1) space per query.

    Iteration: O(n) time, O(1) space for the iterator.

        *Accessing Ordered Elements:
          - Conversion to list: O(n) time, O(n) space.
          - Access by index: O(1) time.

    This example and analysis provide a comprehensive understanding of using `LinkedHashSet` in Java to implement an
    ordered set, covering insertion, deletion, membership testing, iteration, and accessing ordered elements, along with
    their respective time and space complexities.

- Implement Ordered Set as AVL tree:
====================================

    Implementing an ordered set using an AVL tree in Java involves ensuring that the tree remains balanced after every
    insertion and deletion, which allows for efficient lookups, insertions, deletions, and ordered traversal.

    Here is a detailed implementation of an ordered set using an AVL tree along with the time and space complexities for the operations:

    * AVL Tree Implementation:
    --------------------------
            1. AVL Tree Node
            First, define the node class for the AVL tree:

            class AVLNode<E> {
                E key;
                int height;
                AVLNode<E> left, right;

                AVLNode(E key) {
                    this.key = key;
                    this.height = 1;
                }
            }

            2. AVL Tree Class
            Next, implement the AVL tree class with methods for insertion, deletion, membership testing, and accessing ordered elements:

            import java.util.NoSuchElementException;

            public class AVLTreeSet<E extends Comparable<E>> {
                private AVLNode<E> root;

                // Utility methods
                private int height(AVLNode<E> node) {
                    return node == null ? 0 : node.height;
                }

                private int getBalance(AVLNode<E> node) {
                    return node == null ? 0 : height(node.left) - height(node.right);
                }

                private AVLNode<E> rightRotate(AVLNode<E> y) {
                    AVLNode<E> x = y.left;
                    AVLNode<E> T2 = x.right;
                    x.right = y;
                    y.left = T2;
                    y.height = Math.max(height(y.left), height(y.right)) + 1;
                    x.height = Math.max(height(x.left), height(x.right)) + 1;
                    return x;
                }

                private AVLNode<E> leftRotate(AVLNode<E> x) {
                    AVLNode<E> y = x.right;
                    AVLNode<E> T2 = y.left;
                    y.left = x;
                    x.right = T2;
                    x.height = Math.max(height(x.left), height(x.right)) + 1;
                    y.height = Math.max(height(y.left), height(y.right)) + 1;
                    return y;
                }

                // Insertion
                public void add(E key) {
                    root = add(root, key);
                }

                private AVLNode<E> add(AVLNode<E> node, E key) {
                    if (node == null)
                        return new AVLNode<>(key);
                    if (key.compareTo(node.key) < 0)
                        node.left = add(node.left, key);
                    else if (key.compareTo(node.key) > 0)
                        node.right = add(node.right, key);
                    else
                        return node; // Duplicates are not allowed

                    node.height = 1 + Math.max(height(node.left), height(node.right));
                    int balance = getBalance(node);

                    // Left Left Case
                    if (balance > 1 && key.compareTo(node.left.key) < 0)
                        return rightRotate(node);

                    // Right Right Case
                    if (balance < -1 && key.compareTo(node.right.key) > 0)
                        return leftRotate(node);

                    // Left Right Case
                    if (balance > 1 && key.compareTo(node.left.key) > 0) {
                        node.left = leftRotate(node.left);
                        return rightRotate(node);
                    }

                    // Right Left Case
                    if (balance < -1 && key.compareTo(node.right.key) < 0) {
                        node.right = rightRotate(node.right);
                        return leftRotate(node);
                    }

                    return node;
                }

                // Deletion
                public void remove(E key) {
                    root = remove(root, key);
                }

                private AVLNode<E> remove(AVLNode<E> node, E key) {
                    if (node == null)
                        return node;

                    if (key.compareTo(node.key) < 0)
                        node.left = remove(node.left, key);
                    else if (key.compareTo(node.key) > 0)
                        node.right = remove(node.right, key);
                    else {
                        if ((node.left == null) || (node.right == null)) {
                            AVLNode<E> temp = node.left != null ? node.left : node.right;
                            if (temp == null) {
                                temp = node;
                                node = null;
                            } else
                                node = temp;
                            temp = null;
                        } else {
                            AVLNode<E> temp = minValueNode(node.right);
                            node.key = temp.key;
                            node.right = remove(node.right, temp.key);
                        }
                    }

                    if (node == null)
                        return node;

                    node.height = Math.max(height(node.left), height(node.right)) + 1;
                    int balance = getBalance(node);

                    if (balance > 1 && getBalance(node.left) >= 0)
                        return rightRotate(node);

                    if (balance > 1 && getBalance(node.left) < 0) {
                        node.left = leftRotate(node.left);
                        return rightRotate(node);
                    }

                    if (balance < -1 && getBalance(node.right) <= 0)
                        return leftRotate(node);

                    if (balance < -1 && getBalance(node.right) > 0) {
                        node.right = rightRotate(node.right);
                        return leftRotate(node);
                    }

                    return node;
                }

                private AVLNode<E> minValueNode(AVLNode<E> node) {
                    AVLNode<E> current = node;
                    while (current.left != null)
                        current = current.left;
                    return current;
                }

                // Membership Testing
                public boolean contains(E key) {
                    return contains(root, key);
                }

                private boolean contains(AVLNode<E> node, E key) {
                    if (node == null)
                        return false;
                    if (key.compareTo(node.key) < 0)
                        return contains(node.left, key);
                    else if (key.compareTo(node.key) > 0)
                        return contains(node.right, key);
                    else
                        return true;
                }

                // Iteration
                public void inOrder() {
                    inOrder(root);
                }

                private void inOrder(AVLNode<E> node) {
                    if (node != null) {
                        inOrder(node.left);
                        System.out.print(node.key + " ");
                        inOrder(node.right);
                    }
                }

                // Accessing Ordered Elements
                public E getFirst() {
                    if (root == null) throw new NoSuchElementException();
                    AVLNode<E> node = root;
                    while (node.left != null) {
                        node = node.left;
                    }
                    return node.key;
                }

                public E getLast() {
                    if (root == null) throw new NoSuchElementException();
                    AVLNode<E> node = root;
                    while (node.right != null) {
                        node = node.right;
                    }
                    return node.key;
                }
            }

    3. Time and Space Complexity

        1. Insertion
        - Time Complexity: O(log n) - The tree remains balanced, ensuring that the height is O(log n), and each insertion
            takes logarithmic time.
        - Space Complexity: O(1) additional space for each insertion, but O(n) total space for storing all elements.

        2. Deletion
        - Time Complexity: O(log n) - Similar to insertion, the tree remains balanced, and deletions take logarithmic time.
        - Space Complexity: O(1) additional space for each deletion, but O(n) total space for storing all elements.

        3. Membership Testing
        - Time Complexity: O(log n) - The balanced nature of the AVL tree ensures logarithmic time for lookups.
        - Space Complexity: O(1) per query.

        4. Iteration
        - Time Complexity: O(n) - In-order traversal visits each node once.
        - Space Complexity: O(h) = O(log n) for the recursion stack during traversal.

        5. Accessing Ordered Elements
        - Time Complexity: O(log n) - Finding the minimum or maximum element takes logarithmic time due to the height of the tree.
        - Space Complexity: O(1) per query.

    4. Example Usage

    Here is a complete example demonstrating these operations:

            public class Main {
                public static void main(String[] args) {
                    AVLTreeSet<Integer> orderedSet = new AVLTreeSet<>();

                    // Insertion
                    orderedSet.add(10);
                    orderedSet.add(20);
                    orderedSet.add(30);
                    orderedSet.add(40);
                    orderedSet.add(50);
                    orderedSet.add(25);

                    // In-order traversal
                    System.out.println("In-order traversal:");
                    orderedSet.inOrder(); // Output: 10 20 25 30 40 50
                    System.out.println();

                    // Membership Testing
                    System.out.println("Contains 20: " + orderedSet.contains(20)); // Output: true
                    System.out.println("Contains 60: " + orderedSet.contains(60)); // Output: false

                    // Accessing Ordered Elements
                    System.out.println("First element: " + orderedSet.getFirst()); // Output: 10
                    System.out.println("Last element: " + orderedSet.getLast()); // Output: 50

                    // Deletion
                    orderedSet.remove(30);
                    System.out.println("In-order traversal after deleting 30:");
                    orderedSet.inOrder(); // Output: 10 20 25 40 50
                }
            }

    This implementation demonstrates how to use an AVL tree to maintain an ordered set with efficient operations and
    includes a detailed analysis of the time and space complexities for each operation.

- Ordered Set Example LeetCode Question: 456. 132 Pattern
==========================================================

    To solve the problem of detecting a 132 pattern in an array of integers, we can use a stack-based approach to efficiently
    find the required pattern. This approach ensures an optimal time and space complexity. Here's the detailed implementation
    along with the complexity analysis (ChatGPT coded the solution 🤖):

    1. Approach:
    ------------
        1. Use a Stack: The idea is to use a stack to keep track of possible candidates for `nums[k]` in the 132 pattern.
        2. Track the Minimum Element: Maintain a variable to keep track of the minimum element (`nums[i]`) up to the current point
            in the iteration.
        3. Iterate from Right to Left: This helps in efficiently determining the `nums[k]` and `nums[j]` by utilizing the stack and
            the tracked minimum element.

    2. Steps:
    ---------
        1. Initialize a stack to keep track of potential `nums[k]` values.
        2. Initialize a variable `third` to represent `nums[k]`, set it initially to the smallest possible value.
        3. Traverse the array from right to left.
        4. For each element, check if it can be `nums[i]` in the 132 pattern (i.e., it should be less than `third`).
        5. While the stack is not empty and the top of the stack is less than the current element, pop from the stack and update
            `third` (indicating that this popped value is a candidate for `nums[k]`).
        6. If the current element is less than `third`, then a 132 pattern is found.
        7. If not, push the current element onto the stack.
        8. If the loop completes without finding a pattern, return false.

    3. Implementation in Java:
    --------------------------
            import java.util.Stack;

            public class Pattern132 {
                public boolean find132pattern(int[] nums) {
                    if (nums == null || nums.length < 3) {
                        return false;
                    }

                    int third = Integer.MIN_VALUE;
                    Stack<Integer> stack = new Stack<>();

                    for (int i = nums.length - 1; i >= 0; i--) {
                        if (nums[i] < third) {
                            return true;
                        }
                        while (!stack.isEmpty() && stack.peek() < nums[i]) {
                            third = stack.pop();
                        }
                        stack.push(nums[i]);
                    }

                    return false;
                }

                public static void main(String[] args) {
                    Pattern132 solution = new Pattern132();
                    int[] nums = {3, 1, 4, 2};
                    System.out.println(solution.find132pattern(nums)); // Output: true

                    int[] nums2 = {1, 2, 3, 4};
                    System.out.println(solution.find132pattern(nums2)); // Output: false

                    int[] nums3 = {-1, 3, 2, 0};
                    System.out.println(solution.find132pattern(nums3)); // Output: true
                }
            }

    4. Complexity Analysis

        - Time Complexity: O(n)
          - We traverse the array once, and each element is pushed and popped from the stack at most once. Therefore, the
            operations on the stack are O(1) on average, resulting in a linear time complexity.

        - Space Complexity: O(n)
          - In the worst case, all elements could be pushed onto the stack, which requires O(n) space.

    This implementation efficiently checks for the 132 pattern in an array using a stack and achieves optimal time and
        space complexity.