Skip to content

1656. Design an Ordered Stream 👎

  • Time:
    • Constructor: $O(n)$
    • insert(idKey: int, value: int): amortized $O(1)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class OrderedStream {
 public:
  OrderedStream(int n) : values(n) {}

  vector<string> insert(int idKey, string value) {
    --idKey;  // Converts to 0-indexed.
    values[idKey] = value;
    if (idKey > i)
      return {};
    while (i < values.size() && !values[i].empty())
      ++i;
    return vector<string>{values.begin() + idKey, values.begin() + i};
  }

 private:
  vector<string> values;
  int i = 0;  // values' index (0-indexed)
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class OrderedStream {
  public OrderedStream(int n) {
    this.values = new String[n];
  }

  public List<String> insert(int idKey, String value) {
    --idKey; // Converts to 0-indexed
    values[idKey] = value;
    if (idKey > i)
      return new ArrayList<>();
    while (i < values.length && values[i] != null && !values[i].isEmpty())
      i++;
    List<String> res = new ArrayList<>();
    for (int j = idKey; j < i; ++j)
      res.add(values[j]);
    return res;
  }

  private String[] values;
  private int i = 0; // values' index (0-indexed)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class OrderedStream:
  def __init__(self, n: int):
    self.values = [''] * n
    self.i = 0  # self.values' index (0-indexed)

  def insert(self, idKey: int, value: str) -> list[str]:
    idKey -= 1  # Converts to 0-indexed.
    self.values[idKey] = value
    if idKey > self.i:
      return []
    while self.i < len(self.values) and self.values[self.i]:
      self.i += 1
    return self.values[idKey:self.i]