Three solutions you would want to discuss in an interview (O(n), O(logn) and O(1) lookup)
First is straight forward. O(n) space O(1) for init and O(n) next (O(1) amortized).\n\n\n\tclass RLEIterator {\n\n\t\tint[] A;\n\t\tint curA = 0;\n\t\tpublic RL
First is straight forward. `O(n)` space `O(1)` for init and `O(n)` next (`O(1)` amortized).\n\n\n\tclass RLEIterator {\n\n\t\tint[] A;\n\t\tint curA = 0;\n\t\tpublic RLEIterator(int[] A) {\n\t\t\tthis.A = A;\n\t\t}\n\n\t\tpublic int next(int n) {\n\t\t\tint num=0;\n\t\t\twhile(n > 0) {\n\t\t\t\tif (curA >= A.length) return -1;\n\t\t\t\tn = n - A[curA];\n\t\t\t\tif (n <= 0) {\n\t\t\t\t\tnum = A[curA+1];\n\t\t\t\t\tA[curA] = -n;\n\t\t\t\t} else {\n\t\t\t\t\tcurA += 2;\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn num;\n\t\t}\n\t}\n\nSecond is a binary search. `O(n)` space `O(n)` init and `O(log n)` next.\n\n\tclass RLEIterator {\n\n\t\tlong[] count;\n\t\tint[] num;\n\n\t\tlong cur = 0;    \n\t\tint low = 0;\n\t\tpublic RLEIterator(int[] A) {\n\t\t\tcount = new long[A.length/2];\n\t\t\tnum = new int[A.length/2];\n\t\t\tfor (int i=0; i<A.length; i+=2) {\n\t\t\t\tcount[i/2] = A[i] + (i>1? count[i/2 - 1] : 0);\n\t\t\t\tnum[i/2] = A[i+1];\n\t\t\t}\n\t\t}\n\n\t\tpublic int next(int n) {\n\t\t\tif (count.length==0) return -1;\n\t\t\tcur += n;\n\t\t\tif (cur > count[count.length-1]) return -1;\n\t\t\tint l=low, h=count.length-1;\n\n\t\t\twhile(l < h) {\n\t\t\t\tint mid = l + (h-l)/2;\n\t\t\t\tif (count[mid] >= cur) {\n\t\t\t\t\th = mid;\n\t\t\t\t} else {\n\t\t\t\t\tl = mid+1;\n\t\t\t\t}\n\t\t\t}\n\t\t\tlow = l;\n\t\t\treturn num[l];\n\t\t}\n\t}\n\nThe third option is to write out the actual array. And then use a pointer to directly index the array to see which number is in the specific field. Init runs in `O(k)` space and time, where `k` is the size of the unwrapped array. As `k` is very big in Leetcodes test cases this solution is not accepted! However, next then runs in `O(1)` which might be great for specific use cases!\n\nAll in all the binary search solution should be preferable in many cases.
[]