{"id":7666,"date":"2020-11-14T20:16:02","date_gmt":"2020-11-15T04:16:02","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7666"},"modified":"2020-11-14T20:19:24","modified_gmt":"2020-11-15T04:19:24","slug":"leetcode-1656-design-an-ordered-stream","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/data-structure\/leetcode-1656-design-an-ordered-stream\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1656. Design an Ordered Stream"},"content":{"rendered":"\n<p>There are&nbsp;<code>n<\/code>&nbsp;<code>(id, value)<\/code>&nbsp;pairs, where&nbsp;<code>id<\/code>&nbsp;is an integer between&nbsp;<code>1<\/code>&nbsp;and&nbsp;<code>n<\/code>&nbsp;and&nbsp;<code>value<\/code>&nbsp;is a string. No two pairs have the same&nbsp;<code>id<\/code>.<\/p>\n\n\n\n<p>Design a stream that takes the&nbsp;<code>n<\/code>&nbsp;pairs in an&nbsp;<strong>arbitrary<\/strong>&nbsp;order, and returns the values over several calls in&nbsp;<strong>increasing order of their ids<\/strong>.<\/p>\n\n\n\n<p>Implement the&nbsp;<code>OrderedStream<\/code>&nbsp;class:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>OrderedStream(int n)<\/code>&nbsp;Constructs the stream to take&nbsp;<code>n<\/code>&nbsp;values and sets a current&nbsp;<code>ptr<\/code>&nbsp;to&nbsp;<code>1<\/code>.<\/li><li><code>String[] insert(int id, String value)<\/code>&nbsp;Stores the new&nbsp;<code>(id, value)<\/code>&nbsp;pair in the stream. After storing the pair:<ul><li>If the stream has stored a pair with&nbsp;<code>id = ptr<\/code>, then find the&nbsp;<strong>longest contiguous incrementing sequence<\/strong>&nbsp;of ids starting with&nbsp;<code>id = ptr<\/code>&nbsp;and return a list of the values associated with those ids&nbsp;<strong>in order<\/strong>. Then, update&nbsp;<code>ptr<\/code>&nbsp;to the last&nbsp;<code>id + 1<\/code>.<\/li><li>Otherwise, return an empty list.<\/li><\/ul><\/li><\/ul>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/11\/10\/q1.gif\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted wp-block-preformatted;crayon:false\"><strong>Input<\/strong>\n[\"OrderedStream\", \"insert\", \"insert\", \"insert\", \"insert\", \"insert\"]\n[[5], [3, \"ccccc\"], [1, \"aaaaa\"], [2, \"bbbbb\"], [5, \"eeeee\"], [4, \"ddddd\"]]\n<strong>Output<\/strong>\n[null, [], [\"aaaaa\"], [\"bbbbb\", \"ccccc\"], [], [\"ddddd\", \"eeeee\"]]\n<strong>Explanation<\/strong>\nOrderedStream os= new OrderedStream(5);\nos.insert(3, \"ccccc\"); \/\/ Inserts (3, \"ccccc\"), returns [].\nos.insert(1, \"aaaaa\"); \/\/ Inserts (1, \"aaaaa\"), returns [\"aaaaa\"].\nos.insert(2, \"bbbbb\"); \/\/ Inserts (2, \"bbbbb\"), returns [\"bbbbb\", \"ccccc\"].\nos.insert(5, \"eeeee\"); \/\/ Inserts (5, \"eeeee\"), returns [].\nos.insert(4, \"ddddd\"); \/\/ Inserts (4, \"ddddd\"), returns [\"ddddd\", \"eeeee\"].\n<\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Straight Forward<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n) in total<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass OrderedStream {\npublic:\n  OrderedStream(int n): data_(n + 1) {}\n\n  vector<string> insert(int id, string value) {\n    data_[id] = value;\n    vector<string> ans;\n    if (ptr_ == id)\n      while (ptr_ < data_.size() &#038;&#038; !data_[ptr_].empty())\n        ans.push_back(data_[ptr_++]);\n    return ans;\n  }\nprivate:\n  int ptr_ = 1;\n  vector<string> data_;\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass OrderedStream:\n  def __init__(self, n: int):\n    self.data = [None] * (n + 1)\n    self.ptr = 1\n\n  def insert(self, id: int, value: str) -> List[str]:\n    self.data[id] = value\n    if id == self.ptr:\n      while self.ptr < len(self.data) and self.data[self.ptr]:\n        self.ptr += 1\n      return self.data[id:self.ptr]\n    return []\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There are&nbsp;n&nbsp;(id, value)&nbsp;pairs, where&nbsp;id&nbsp;is an integer between&nbsp;1&nbsp;and&nbsp;n&nbsp;and&nbsp;value&nbsp;is a string. No two pairs have the same&nbsp;id. Design a stream that takes the&nbsp;n&nbsp;pairs in an&nbsp;arbitrary&nbsp;order, and returns&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89],"tags":[20,291,251,222],"class_list":["post-7666","post","type-post","status-publish","format-standard","hentry","category-data-structure","tag-array","tag-data-structure","tag-design","tag-easy","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7666","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7666"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7666\/revisions"}],"predecessor-version":[{"id":7670,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7666\/revisions\/7670"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7666"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7666"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7666"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}