036_container_water.sio

//@ run-pass
// HumanEval 036: Container With Most Water
//
// Given n heights, find two lines that together with the x-axis form
// a container that holds the most water. Uses the two-pointer approach.
// Area = min(height[lo], height[hi]) * (hi - lo)

fn max_water(height: [i64; 256], n: i64) -> i64 with Mut, Panic, Div {
    var lo: i64 = 0
    var hi: i64 = n - 1
    var best: i64 = 0

    while lo < hi {
        // min of two heights
        var h: i64 = height[lo]
        if height[hi] < h {
            h = height[hi]
        }
        let area = h * (hi - lo)
        if area > best {
            best = area
        }
        // move the shorter side inward
        if height[lo] < height[hi] {
            lo = lo + 1
        } else {
            hi = hi - 1
        }
    }
    best
}

fn main() -> i64 with IO, Mut, Panic, Div {
    // Test 1: [1,8,6,2,5,4,8,3,7] -> 49 (between indices 1 and 8)
    var h1: [i64; 256] = [0; 256]
    h1[0] = 1
    h1[1] = 8
    h1[2] = 6
    h1[3] = 2
    h1[4] = 5
    h1[5] = 4
    h1[6] = 8
    h1[7] = 3
    h1[8] = 7
    assert(max_water(h1, 9) == 49)

    // Test 2: [1, 1] -> 1
    var h2: [i64; 256] = [0; 256]
    h2[0] = 1
    h2[1] = 1
    assert(max_water(h2, 2) == 1)

    // Test 3: [4, 3, 2, 1, 4] -> 16 (indices 0 and 4: min(4,4)*4)
    var h3: [i64; 256] = [0; 256]
    h3[0] = 4
    h3[1] = 3
    h3[2] = 2
    h3[3] = 1
    h3[4] = 4
    assert(max_water(h3, 5) == 16)

    // Test 4: [1, 2, 1] -> 2 (indices 0 and 2: min(1,1)*2)
    var h4: [i64; 256] = [0; 256]
    h4[0] = 1
    h4[1] = 2
    h4[2] = 1
    assert(max_water(h4, 3) == 2)

    // Test 5: [3, 9, 3, 4, 7, 2, 12, 6] -> 45 (indices 1 and 6: min(9,12)*5)
    var h5: [i64; 256] = [0; 256]
    h5[0] = 3
    h5[1] = 9
    h5[2] = 3
    h5[3] = 4
    h5[4] = 7
    h5[5] = 2
    h5[6] = 12
    h5[7] = 6
    assert(max_water(h5, 8) == 45)

    println("036_container_water: ALL TESTS PASSED")
    0
}