🔥Beats 93.56%🔥✅Easy (C++/Java/Python) Solution With Detailed Explanation✅
Intuition\nThe intuition of OrderedStream class in C++ is designed to model an ordered stream of strings where the strings are inserted at specific positions, a
# Intuition\nThe intuition of `OrderedStream` class in C++ is designed to model an ordered stream of strings where the strings are inserted at specific positions, and contiguous blocks of strings are returned from the point of insertion if they form a sequence without gaps. Let\'s analyze the approach and complexity of this implementation.\n\n\n![Screenshot 2024-02-20 084736.png](https://assets.leetcode.com/users/images/572e1e5d-36c1-46bc-80a3-9a1de5ae0b3e_1708399271.8232589.png)\n# Approach\n\n1. **Initialization (`OrderedStream` constructor):** The vector `res` is resized to `n` and filled with empty strings (or spaces, as in the provided code), indicating uninitialized positions. The pointer `ptr` is set to 0.\n\n2. **Insertion (`insert` method):**\n   - The method places the input string `value` at the correct index (`idKey - 1`) in the vector `res`.\n   - Starting from `ptr`, it checks for and collects all contiguous, non-empty strings in a temporary vector `s`.\n   - The pointer `ptr` is updated to point to the next empty or uninitialized position in the vector `res`.\n\n\n# Complexity\n\n- **Time Complexity:**\n  - The time complexity of the `insert` method is O(n) in the worst-case scenario, where `n` is the total number of elements in the stream. This worst-case scenario occurs when the last insert operation triggers the collection and return of all remaining elements in the stream.\n  - However, for each individual insert operation, the time complexity can be considered amortized O(1), assuming that the distribution of insert operations and the lengths of contiguous blocks are relatively uniform over time.\n\n- **Space Complexity:**\n  - The space complexity is O(n), where `n` is the size of the stream. This is due to the storage requirements of the vector `res`, which holds up to `n` strings. The temporary vector `s` returned by the `insert` method does not contribute to the overall space complexity in terms of additional data structures because its lifetime is limited to the scope of the `insert` method call.\n\n# Code\n```C++ []\nclass OrderedStream {\npublic:\n\n    vector<string> res;\n    int ptr = 0;\n    OrderedStream(int n) {\n        res.resize(n, " ");\n    }\n    \n    vector<string> insert(int idKey, string value) {\n        res[idKey-1] = value;\n        vector<string> s = {};\n\n        while (ptr < res.size() && res[ptr] != " ")\n            s.push_back(res[ptr++]);\n\n        return s;\n    }\n};\n```\n```Java []\nimport java.util.ArrayList;\nimport java.util.List;\n\npublic class OrderedStream {\n    private String[] stream;\n    private int ptr;\n\n    public OrderedStream(int n) {\n        stream = new String[n];\n        ptr = 0; // Pointer starts at 0, which will be incremented to point to the next index after the first insertion\n    }\n\n    public List<String> insert(int idKey, String value) {\n        List<String> result = new ArrayList<>();\n        // Adjust the idKey to 0-based index\n        stream[idKey - 1] = value;\n        \n        // Check if the current pointer is at an element that is not null and add to result list\n        while (ptr < stream.length && stream[ptr] != null) {\n            result.add(stream[ptr]);\n            ptr++;\n        }\n\n        return result;\n    }\n}\n\n```\n```Python []\nfrom typing import List\n\nclass OrderedStream:\n\n    def __init__(self, n: int):\n        self.stream = [""] * n  # Initialize the stream with empty strings\n        self.ptr = 0  # Pointer to track the next element to output\n\n    def insert(self, idKey: int, value: str) -> List[str]:\n        # Adjust for 0-based indexing\n        self.stream[idKey - 1] = value\n        result = []\n\n        # Output all contiguous, non-empty strings starting from ptr\n        while self.ptr < len(self.stream) and self.stream[self.ptr]:\n            result.append(self.stream[self.ptr])\n            self.ptr += 1\n\n        return result\n\n```\n\n\n```
['C++']