algoadvance

Leetcode 1656. Design an Ordered Stream

Problem Statement

You are given an OrderedStream class that consists of:

• An integer n (the size of the stream)
• A constructor (OrderedStream(int n)) that creates a stream of size n and initializes all elements to null.
• A function insert(int idKey, string value) that inserts the pair (idKey, value) into the stream (where idKey is a 1-based index) and then returns the largest possible chunk of consecutive non-null values that start from the position pointed to by a pointer in the stream.

Initially, the pointer is set to 1. When you insert a pair, it should return an array containing the largest chunk of consecutive non-null values, starting from the current position of the pointer. Then move the pointer past these inserted values.

Example

• OrderedStream os = new OrderedStream(5);
• assert(os.insert(3, "ccccc") == []);
• assert(os.insert(1, "aaaaa") == ["aaaaa"]);
• assert(os.insert(2, "bbbbb") == ["bbbbb", "ccccc"]);
• assert(os.insert(5, "eeeee") == []);
• assert(os.insert(4, "ddddd") == ["ddddd", "eeeee"]);

Clarifying Questions

1. Is the idKey guaranteed to be within the range 1 to n?
2. Can we assume that the insertions will be valid, i.e., no duplicate keys or out-of-order issues needing special handling?
3. Should the stream always maintain the order of inserted elements, or do we need to sort them before returning?

Strategy

1. Initialize an array to store strings with a size of n and set a pointer to the first position.
2. During insertion, place the value in its corresponding position in the array (account for 1-based index by subtracting 1).
3. After insertion, check from the current pointer position for the longest consecutive non-null chunk.
4. Accumulate this chunk, update the pointer, and return the accumulated values.

Code

Here is a C++ implementation of the OrderedStream class:

#include <vector>
#include <string>

class OrderedStream {
public:
    OrderedStream(int n) : stream(n), ptr(0) {}

    std::vector<std::string> insert(int idKey, const std::string& value) {
        stream[idKey - 1] = value;  // Insert the value at the 1-based index adjusted for 0-based array
        std::vector<std::string> result;

        // Collect all consecutive non-null values starting from the pointer
        while (ptr < stream.size() && !stream[ptr].empty()) {
            result.push_back(stream[ptr]);
            ++ptr;
        }

        return result;
    }

private:
    std::vector<std::string> stream;
    int ptr;
};

Time Complexity

• The constructor OrderedStream(int n) runs in O(n) as it initializes a vector of size n.
• The insert function runs in O(k), where k is the length of the chunk of consecutive non-null elements starting from the current pointer. In the worst case, this can be O(n) when all elements up to the current position are in sequence.

This approach ensures efficient management of the stream while maintaining a clear and straightforward implementation.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?