Optimize Data Packet Segmentation

Problem Statement

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)