Learning Journal

2/1/2024

RLEIterator -- 3rd attempt

Tags: algorithms leetcode divide_and_conquer

class RLEIterator {
    private _arr = [];

    constructor(encoding: number[]) {
        for(let i = 0; i < encoding.length; i+=2) {
            if(encoding[i] === 0) {
                continue;
            }
            else {
                this._arr.push({
                    num: encoding[i + 1],
                    count: encoding[i]
                })
            }
        }
    }

    next(n:number):number {
        let result = -1;

        for(let i = 0; i < this._arr.length; i++) {
            const item = this._arr.shift();
            i--;

            n = n - item.count;

            if(n <= 0) {
                item.count = -1 * n;
                result = item.num;

                if(item.count > 0) {
                    this._arr.unshift(item);
                    i++;
                }

                break;
            }
        }

        return result;
    }   
}class RLEIterator {
    private _arr = [];

    constructor(encoding: number[]) {
        for(let i = 0; i < encoding.length; i+=2) {
            if(encoding[i] === 0) {
                continue;
            }
            else {
                this._arr.push({
                    num: encoding[i + 1],
                    count: encoding[i]
                })
            }
        }
    }

    next(n:number):number {
        let result = -1;

        for(let i = 0; i < this._arr.length; i++) {
            const item = this._arr.shift();
            i--;

            n = n - item.count;

            if(n <= 0) {
                item.count = -1 * n;
                result = item.num;

                if(item.count > 0) {
                    this._arr.unshift(item);
                    i++;
                }

                break;
            }
        }

        return result;
    }   
}

**This is my third attempt at solving the RLEIterator problem.

Let me try to explain it again.

In the constructor, we convert the encoding array to a private array of objects that has two properties: num and count.

In the next function, we iterate through the private array. In each iteration, we get the current item/block. See whether or not n consumes the block. If it is and there is some n left, we update n and move to the next block and do the same thing. If n cannot consume the whole block, we update the block's count and get the value of the block to return. If the block's count is still greater than 0 which means there is something left on the block, we add the block back to the array and adjust the i pointer accordingly.

Revised by ChatGPT

In the constructor, we transform the input encoding array into a private array, _arr, which consists of objects. Each object possesses two properties: num, representing the actual number, and count, indicating the frequency of that number. We only include numbers with a non-zero frequency in _arr.

In the next function, we process requests for the next n elements sequentially. The function iterates through _arr, examining one block (or item) at a time. For each block, we determine if n is sufficient to consume the entire block. If n exceeds or equals the block's count, we reduce n by the count of that block and proceed to the next block. In cases where n is less than the block's count, we've located the block containing the nth element. At this point, we:

Update the block's count to reflect the number of elements consumed.
Assign the block's number to result as it represents the value of the nth element.
If the block still contains elements (its count is positive), we adjust the block's count and reinsert it into _arr for future next calls.

The current implementation uses shift() and unshift() operations for array manipulation, which, although functional, is not optimal for performance, especially with larger arrays. These operations have a time complexity of O(n) and complicate the index management within the array.