1656. Design an Ordered Stream LeetCode Solution

In this guide, you will get 1656. Design an Ordered Stream LeetCode Solution with the best time and space complexity. The solution to Design an Ordered Stream problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Design an Ordered Stream solution in C++
Design an Ordered Stream solution in Java
Design an Ordered Stream solution in Python
Additional Resources

1656. Design an Ordered Stream LeetCode Solution image

Problem Statement of Design an Ordered Stream

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.

Example not found

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.

Complexity Analysis

Time Complexity: amortized O(1)
Space Complexity: O(n)

1656. Design an Ordered Stream LeetCode Solution in C++

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)
};
/* code provided by PROGIEZ */

1656. Design an Ordered Stream LeetCode Solution in Java

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)
}
// code provided by PROGIEZ

1656. Design an Ordered Stream LeetCode Solution in Python

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]
 # code by PROGIEZ