Array Data Structure and Operations

// Array creation and initialization
const arr = [1, 2, 3, 4, 5];
const zeros = new Array(5).fill(0); // [0, 0, 0, 0, 0]

// Access - O(1)
const first = arr[0];        // 1
const last = arr[arr.length - 1]; // 5

// Search - O(n)
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

// Insert at end - O(1) amortized
arr.push(6); // [1, 2, 3, 4, 5, 6]

// Insert at position - O(n)
function insertAt(arr, index, value) {
    arr.splice(index, 0, value);
    return arr;
}
insertAt(arr, 2, 10); // [1, 2, 10, 3, 4, 5, 6]

// Delete at end - O(1)
arr.pop(); // [1, 2, 10, 3, 4, 5]

// Delete at position - O(n)
arr.splice(2, 1); // [1, 2, 3, 4, 5]

// Traverse - O(n)
arr.forEach((val, idx) => console.log(`arr[${idx}] = ${val}`));

// Row-major traversal
function rowMajor(matrix) {
    const result = [];
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            result.push(matrix[i][j]);
        }
    }
    return result;
}

// Column-major traversal
function columnMajor(matrix) {
    const result = [];
    for (let j = 0; j < matrix[0].length; j++) {
        for (let i = 0; i < matrix.length; i++) {
            result.push(matrix[i][j]);
        }
    }
    return result;
}

// Spiral traversal
function spiralOrder(matrix) {
    const result = [];
    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;
    
    while (top <= bottom && left <= right) {
        // Right
        for (let j = left; j <= right; j++) result.push(matrix[top][j]);
        top++;
        // Down
        for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
        right--;
        // Left
        if (top <= bottom) {
            for (let j = right; j >= left; j--) result.push(matrix[bottom][j]);
            bottom--;
        }
        // Up
        if (left <= right) {
            for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
            left++;
        }
    }
    return result;
}

// Diagonal traversal
function diagonalTraversal(matrix) {
    const result = [];
    const m = matrix.length, n = matrix[0].length;
    
    // Upper diagonals (starting from first row)
    for (let d = 0; d < n; d++) {
        let i = 0, j = d;
        while (i < m && j >= 0) {
            result.push(matrix[i][j]);
            i++;
            j--;
        }
    }
    
    // Lower diagonals (starting from first column)
    for (let d = 1; d < m; d++) {
        let i = d, j = n - 1;
        while (i < m && j >= 0) {
            result.push(matrix[i][j]);
            i++;
            j--;
        }
    }
    return result;
}

class DynamicArray {
    constructor(initialCapacity = 2) {
        this.data = new Array(initialCapacity);
        this.size = 0;
        this.capacity = initialCapacity;
    }
    
    // O(1) amortized
    push(value) {
        if (this.size === this.capacity) {
            this.resize(this.capacity * 2); // Double capacity
        }
        this.data[this.size++] = value;
    }
    
    // O(1)
    pop() {
        if (this.size === 0) return undefined;
        const value = this.data[--this.size];
        
        // Shrink if utilization < 25%
        if (this.size > 0 && this.size < this.capacity / 4) {
            this.resize(Math.floor(this.capacity / 2));
        }
        return value;
    }
    
    // O(n) for resize operation
    resize(newCapacity) {
        const newData = new Array(newCapacity);
        for (let i = 0; i < this.size; i++) {
            newData[i] = this.data[i];
        }
        this.data = newData;
        this.capacity = newCapacity;
    }
    
    // O(1)
    get(index) {
        if (index < 0 || index >= this.size) {
            throw new Error("Index out of bounds");
        }
        return this.data[index];
    }
    
    getSize() { return this.size; }
    getCapacity() { return this.capacity; }
}

// Usage
const arr = new DynamicArray();
for (let i = 0; i < 10; i++) {
    arr.push(i);
    console.log(`Size: ${arr.getSize()}, Capacity: ${arr.getCapacity()}`);
}
// Size: 1, Capacity: 2
// Size: 2, Capacity: 2
// Size: 3, Capacity: 4
// Size: 4, Capacity: 4
// Size: 5, Capacity: 8
// ...

// HashMap-based sparse array
class SparseArray {
    constructor() {
        this.data = new Map();
        this.defaultValue = 0;
    }
    
    set(index, value) {
        if (value !== this.defaultValue) {
            this.data.set(index, value);
        } else {
            this.data.delete(index); // Don't store default values
        }
    }
    
    get(index) {
        return this.data.has(index) ? this.data.get(index) : this.defaultValue;
    }
    
    getSize() {
        return this.data.size; // Number of non-default values
    }
}

// Coordinate List (COO) format - for sparse matrix
class COOMatrix {
    constructor() {
        this.rows = [];
        this.cols = [];
        this.values = [];
    }
    
    add(row, col, value) {
        if (value !== 0) {
            this.rows.push(row);
            this.cols.push(col);
            this.values.push(value);
        }
    }
    
    get(row, col) {
        for (let i = 0; i < this.rows.length; i++) {
            if (this.rows[i] === row && this.cols[i] === col) {
                return this.values[i];
            }
        }
        return 0;
    }
}

// Run-Length Encoding
class RLEArray {
    constructor() {
        this.runs = []; // [{value, count}, ...]
    }
    
    encode(arr) {
        if (arr.length === 0) return;
        
        let currentValue = arr[0];
        let count = 1;
        
        for (let i = 1; i < arr.length; i++) {
            if (arr[i] === currentValue) {
                count++;
            } else {
                this.runs.push({value: currentValue, count});
                currentValue = arr[i];
                count = 1;
            }
        }
        this.runs.push({value: currentValue, count});
    }
    
    decode() {
        const result = [];
        for (const run of this.runs) {
            for (let i = 0; i < run.count; i++) {
                result.push(run.value);
            }
        }
        return result;
    }
}

// Example usage
const sparse = new SparseArray();
sparse.set(1000, 42);
sparse.set(5000, 99);
console.log(sparse.get(1000)); // 42
console.log(sparse.get(2000)); // 0 (default)
console.log(sparse.getSize()); // 2 (only stores non-zero values)

// Sort array of 0s, 1s, and 2s in-place
function dutchFlagPartition(arr) {
    let low = 0;           // Boundary for 0s
    let mid = 0;           // Current element
    let high = arr.length - 1; // Boundary for 2s
    
    while (mid <= high) {
        if (arr[mid] === 0) {
            [arr[low], arr[mid]] = [arr[mid], arr[low]];
            low++;
            mid++;
        } else if (arr[mid] === 1) {
            mid++;
        } else { // arr[mid] === 2
            [arr[mid], arr[high]] = [arr[high], arr[mid]];
            high--;
        }
    }
    return arr;
}

// Example
const colors = [2, 0, 1, 2, 1, 0, 1, 2, 0];
dutchFlagPartition(colors); // [0, 0, 0, 1, 1, 1, 2, 2, 2]

// Time: O(n), Space: O(1), Single pass!

// Find maximum sum of contiguous subarray
function maxSubarraySum(arr) {
    let maxSoFar = arr[0];      // Global maximum
    let maxEndingHere = arr[0];  // Maximum ending at current position
    
    for (let i = 1; i < arr.length; i++) {
        // Either extend existing subarray or start new one
        maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}

// With indices tracking
function maxSubarrayWithIndices(arr) {
    let maxSoFar = arr[0];
    let maxEndingHere = arr[0];
    let start = 0, end = 0, tempStart = 0;
    
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > maxEndingHere + arr[i]) {
            maxEndingHere = arr[i];
            tempStart = i; // New subarray starts here
        } else {
            maxEndingHere = maxEndingHere + arr[i];
        }
        
        if (maxEndingHere > maxSoFar) {
            maxSoFar = maxEndingHere;
            start = tempStart;
            end = i;
        }
    }
    
    return {sum: maxSoFar, start, end};
}

// Example
const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubarraySum(arr)); // 6 (subarray [4,-1,2,1])
console.log(maxSubarrayWithIndices(arr)); // {sum: 6, start: 3, end: 6}