1656. Design an Ordered Stream #

Problem #

There is a stream of n (id, value) pairs arriving in an arbitrary order, where id 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 id, String value) Inserts the pair (id, 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.

Problem Summary #

There are n (id, value) pairs, where id is an integer between 1 and n, and value is a string. No two (id, value) pairs have the same id.

Design a stream that obtains n (id, value) pairs in an arbitrary order and returns some values in increasing order of id over multiple calls.

Implement the OrderedStream class:

OrderedStream(int n) constructs a stream that can receive n values and sets the current pointer ptr to 1.
String[] insert(int id, String value) stores a new (id, value) pair in the stream. After storing: If the stream has an (id, value) pair with id = ptr, find the longest continuously increasing sequence of ids starting from id = ptr, and return the list of values associated with these ids in order. Then, update ptr to the last id + 1. Otherwise, return an empty list.

Solution Approach #

Design an Ordered Stream with an insert operation. The insert operation first inserts value at the specified position, then returns the longest continuous increasing string sequence from the current pointer ptr to the nearest empty position. If the string is not empty, ptr moves to the index position after the non-empty value.
Easy problem. Just simulate according to the problem description. Be careful to control the position of ptr.

Code #

package leetcode

type OrderedStream struct {
	ptr    int
	stream []string
}

func Constructor(n int) OrderedStream {
	ptr, stream := 1, make([]string, n+1)
	return OrderedStream{ptr: ptr, stream: stream}
}

func (this *OrderedStream) Insert(id int, value string) []string {
	this.stream[id] = value
	res := []string{}
	if this.ptr == id || this.stream[this.ptr] != "" {
		res = append(res, this.stream[this.ptr])
		for i := id + 1; i < len(this.stream); i++ {
			if this.stream[i] != "" {
				res = append(res, this.stream[i])
			} else {
				this.ptr = i
				return res
			}
		}
	}
	if len(res) > 0 {
		return res
	}
	return []string{}
}

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