O(logN) search time, O(n) space solution with Cumulative Sum and Binary Search
Overall Time Complexity O(N),\n\t\n\tConstructor method: \n\tinitialize a cumulative sum variable. loop through the array, increment the cumulative sum value if
Overall Time Complexity O(N),\n\t\n\t**Constructor method:** \n\tinitialize a cumulative sum variable. loop through the array, increment the cumulative sum value if frequency is not zero, insert the sum variable and array value into index list and value list respectively\n\t\n\t**Next method:**\n\tUpdate the global cumulative sum variable, do a binary search from the index list, find the smallest index value which is just  greater than or equal to updated global variable. return the value from corresponding value list.  \n\t\n\tFollowing is the code:\n\t\n\t\tpublic long cumulative_ind = 0;\n\t\tpublic List<long> index_list = new List<long>();\n\t\tpublic List<int> value_list = new List<int>();\n\n\t\tpublic RLEIterator(int[] A) {\n\t\t\tint len = A.Length;\n\t\t\tlong current_cummutive = 0;\n\t\t\tfor (int i = 0; i < len; i+= 2) {\n\t\t\t\tif (A[i] != 0) {\n\t\t\t\t\tcurrent_cummutive += A[i];\n\t\t\t\t\tindex_list.Add(current_cummutive);\n\t\t\t\t\tvalue_list.Add(A[i+1]);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\n\t\tpublic int Next(int n) {\n\t\t\tcumulative_ind += n;        \n\t\t\t\n\t\t\tif (index_list[0] >= cumulative_ind) return value_list[0];\n\t\t\t// if cumulative sum is greater than the decoded array length, simply return -1;\n\t\t\tif (index_list[index_list.Count() - 1] < cumulative_ind) return -1;\n\t\t\t\n\t\t\tint st = 0; int end = index_list.Count() - 1;\n\t\t\twhile (st <= end) {\n\t\t\t\tint mid = (st + end)/2;\n\t\t\t\tif (index_list[mid] == cumulative_ind) return value_list[mid];\n\t\t\t\telse if (index_list[mid] <= cumulative_ind) {\n\t\t\t\t\tst += 1;\n\t\t\t\t} else {\n\t\t\t\t\tend -= 1;\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn value_list[st];\n\t\t}
[]