Company: Amazon_31_jan
Difficulty: medium
Optimize Data Packet Segmentation Problem Description Amazon developers are designing an algorithm to optimize segmentation of streaming data packets. You are given an array of integers data_packets of size n . The algorithm repeatedly performs the following until data_packets becomes empty: Choose an integer k such that 1 ≤ k ≤ length(data_packets) . Compute the MEX (Minimum Excludant) of the first k elements. The MEX of a set of non-negative integers is the smallest non-negative integer not present in the set. Example: MEX({1,2,3}) = 0 , MEX({0,1,2,4}) = 3 . Append this MEX to an array result . Remove the first k elements from data_packets . Your task is to find the lexicographically maximum array result that can be obtained. Note: An array x is lexicographically greater than an array y if at the first index where they differ, x[i] > y[i] , or if y is a prefix of x . Example: [3,2,1] > [3,1,5] (since 2 > 1 at index 1). Example: [1,2,3,4] > [1,2,3] (since the latter is a prefix)