1656. Design an Ordered Stream

Description

There is a stream of n (idKey, value) pairs arriving in an arbitrary order, where idKey is an integer between 1 and n and value is a string. No two pairs have the same id.

Design a stream that returns the values in increasing order of their IDs by returning a chunk (list) of values after each insertion. The concatenation of all the chunks should result in a list of the sorted values.

Implement the OrderedStream class:

OrderedStream(int n) Constructs the stream to take n values.
String[] insert(int idKey, String value) Inserts the pair (idKey, value) into the stream, then returns the largest possible chunk of currently inserted values that appear next in the order.

Example:

Input
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
Output
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]

Explanation
// Note that the values ordered by ID is ["aaaaa", "bbbbb", "ccccc", "ddddd", "eeeee"].
OrderedStream os = new OrderedStream(5);
os.insert(3, "ccccc"); // Inserts (3, "ccccc"), returns [].
os.insert(1, "aaaaa"); // Inserts (1, "aaaaa"), returns ["aaaaa"].
os.insert(2, "bbbbb"); // Inserts (2, "bbbbb"), returns ["bbbbb", "ccccc"].
os.insert(5, "eeeee"); // Inserts (5, "eeeee"), returns [].
os.insert(4, "ddddd"); // Inserts (4, "ddddd"), returns ["ddddd", "eeeee"].
// Concatentating all the chunks returned:
// [] + ["aaaaa"] + ["bbbbb", "ccccc"] + [] + ["ddddd", "eeeee"] = ["aaaaa", "bbbbb", "ccccc", "ddddd", "eeeee"]
// The resulting order is the same as the order above.

Constraints:

1 <= n <= 1000
1 <= id <= n
value.length == 5
value consists only of lowercase letters.
Each call to insert will have a unique id.
Exactly n calls will be made to insert.

Solutions

Class `OrderedStream`

Attributes:
- self.data: A list initialized with None that is used to store the elements of the stream. Its length is n, the number of elements the stream will hold.
- self.ptr: An integer that acts as a pointer to the current position in the stream. It represents the next element in the sequence that should be released (if available).
__init__(self, n: int):
- Initializes the OrderedStream object with a size n. The data list is initialized with n None values, and ptr is set to 0, indicating the start of the stream.
insert(self, idKey: int, value: str) -> List[str]:
- Inserts an element into the stream at the specified idKey (1-indexed).
- The element is inserted at idKey - 1 in self.data (since Python lists are 0-indexed).
- After insertion, the method checks for a contiguous sequence of non-None elements starting from self.ptr.
- If contiguous non-None elements are found, they are added to the ans list, and self.ptr is updated accordingly.
- The method returns the list ans, which contains all the elements that were sequentially available starting from self.ptr.

How It Works

The class manages a stream of elements where elements can be inserted at any position, but the retrieval is always in order.
When a new element is inserted, it checks from the current ptr position to see if there are any contiguous elements available. This means that if ptr is at position 2, and elements at positions 2, 3, and 4 are available (non-None), they will be added to the answer list and returned.
The ptr is then updated to point to the next expected element in the sequence, which is the first None element after the last retrieved element.
The structure is particularly useful when data is received asynchronously or out of order but needs to be processed in a specific sequence.

Complexity

Time Complexity: O(n) in the worst case for insert method, where n is the number of elements in the stream. This is because in the worst case, it may iterate through the entire list of elements.
Space Complexity: O(n), where n is the number of elements in the stream, since a list of size n is used to store the elements.

class OrderedStream {
    private String[] data;
    private int ptr;

    public OrderedStream(int n) {
        data = new String[n];
        ptr = 0;
    }

    public List<String> insert(int idKey, String value) {
        data[idKey - 1] = value;
        List<String> ans = new ArrayList<>();
        while (ptr < data.length && data[ptr] != null) {
            ans.add(data[ptr++]);
        }
        return ans;
    }
}

/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream obj = new OrderedStream(n);
 * List<String> param_1 = obj.insert(idKey,value);
 */

class OrderedStream {
public:
    vector<string> data;
    int ptr = 0;

    OrderedStream(int n) {
        data.resize(n, "");
    }

    vector<string> insert(int idKey, string value) {
        data[idKey - 1] = value;
        vector<string> ans;
        while (ptr < data.size() && data[ptr] != "") ans.push_back(data[ptr++]);
        return ans;
    }
};

/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream* obj = new OrderedStream(n);
 * vector<string> param_1 = obj->insert(idKey,value);
 */

class OrderedStream:
    def __init__(self, n: int):
        self.data = [None] * n
        self.ptr = 0

    def insert(self, idKey: int, value: str) -> List[str]:
        self.data[idKey - 1] = value
        ans = []
        while self.ptr < len(self.data) and self.data[self.ptr]:
            ans.append(self.data[self.ptr])
            self.ptr += 1
        return ans


# Your OrderedStream object will be instantiated and called as such:
# obj = OrderedStream(n)
# param_1 = obj.insert(idKey,value)

type OrderedStream struct {
	data []string
	ptr  int
}

func Constructor(n int) OrderedStream {
	data := make([]string, n)
	return OrderedStream{data, 0}
}

func (this *OrderedStream) Insert(idKey int, value string) []string {
	this.data[idKey-1] = value
	var ans []string
	for this.ptr < len(this.data) && this.data[this.ptr] != "" {
		ans = append(ans, this.data[this.ptr])
		this.ptr++
	}
	return ans
}

/**
 * Your OrderedStream object will be instantiated and called as such:
 * obj := Constructor(n);
 * param_1 := obj.Insert(idKey,value);
 */

class OrderedStream {
    private ptr: number;
    private vals: string[];

    constructor(n: number) {
        this.ptr = 0;
        this.vals = new Array(n);
    }

    insert(idKey: number, value: string): string[] {
        this.vals[idKey - 1] = value;
        const res = [];
        while (this.vals[this.ptr] != null) {
            res.push(this.vals[this.ptr]);
            this.ptr++;
        }
        return res;
    }
}

/**
 * Your OrderedStream object will be instantiated and called as such:
 * var obj = new OrderedStream(n)
 * var param_1 = obj.insert(idKey,value)
 */

struct OrderedStream {
    ptr: usize,
    vals: Vec<Option<String>>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl OrderedStream {
    fn new(n: i32) -> Self {
        Self { ptr: 0, vals: vec![None; n as usize] }
    }

    fn insert(&mut self, id_key: i32, value: String) -> Vec<String> {
        self.vals[(id_key - 1) as usize] = Some(value);
        let mut res = Vec::new();
        while self.ptr < self.vals.len() {
            if let Some(s) = &self.vals[self.ptr] {
                res.push(s.clone());
                self.ptr += 1;
            } else {
                break;
            }
        }
        res
    }
}/**
 * Your OrderedStream object will be instantiated and called as such:
 * let obj = OrderedStream::new(n);
 * let ret_1: Vec<String> = obj.insert(idKey, value);
 */

1656 - Design an Ordered Stream

1656. Design an Ordered Stream

Description

Solutions

Class `OrderedStream`

How It Works

Complexity

All Problems

All Solutions

Welcome to Subscribe On Youtube

1656. Design an Ordered Stream

Description

Solutions

Class OrderedStream

How It Works

Complexity

All Problems

All Solutions

Class `OrderedStream`