Explanation of O(NLogN) solution
Very nice Java solution was provided here: https://leetcode.com/problems/rle-iterator/discuss/204726/Three-solutions-you-would-want-to-discuss-in-an-interview-(
Very nice Java solution was provided here: https://leetcode.com/problems/rle-iterator/discuss/204726/Three-solutions-you-would-want-to-discuss-in-an-interview-(O(n)-O(logn)-and-O(1)-lookup) in using BinarySearch (O(log N)) by storing cumulative count !!\nJust to unravel the solution:\n\nInput-> [3 8 0 9 2 5]\n\n1. Create two Arrays: One that stores the count and other that stores the number with that count\nCount Array : [3 0 2]\nNumber Array: [8 9 5]\n\n2. Now transform the "Count Array" by storing the cumulative count; this way we will be able to get the actual position or interval of the number\nCumulative Count Array: [3, 3+0, 3+0+2] -> [3 3 5]; Note: if the count is 0 in Count array, don\'t even store it to keep it cleaner -> [3 5]\nCumulative Count Array: [3 5]\nNumber Array : [8 5]\n\n3. With this cumulative count, we have actually been able to capture the positions or intervals of the numbers. Space complexity is still O(N/2) -> 0(N)\n[3 5] -> means positions 1 to 3 is the first number 8 and positions 4 to 5 is the second number 5\n\n4. Now, if they are asking us to find the number at position n ( this is a rolling position every time next() is called), we Binary Search the position in the Cumulative County Array\nand return the number in Number Array in that position or in that interval.\n\n5. First Time: n = (2); Binary Search 2 in Cumulative Count Array (CCA)\nLogic: Find n such that its less than or equal to a number in the CCA and greater than the previous number in CCA. Its position 1 -> So, return Number in\nposition 1.\n\n\tSecond Time: n = n + (1) = 3; Binary Search 3 in CCA -> Still its position 1.\n\n\tThird Time : n = n + (2) = 5; Binary Search 5 in CCA ->its position 2- > So, return Number in position 2.\n\n\tFourth Time : n = n + (1) = 6; Binary Search 6 in CCA -> Not available and so return -1.\n\nAs its a Binary Search, time complexity is O(log N).
[]