sounio-benchmarks/063_largest_rectangle.sio at main · Sounio-lang/sounio-benchmarks · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//@ run-pass
// HumanEval 063: Largest Rectangle in Histogram
//
// Given an array of bar heights, find the area of the largest rectangle
// that can be formed in the histogram. Uses a stack-based approach:
// maintain a stack of indices with increasing heights. When a shorter
// bar is encountered, pop and compute areas.

fn largest_rectangle(heights: [i64; 256], n: i64) -> i64 with Mut, Panic {
    var stack: [i64; 256] = [0; 256]
    var top: i64 = 0
    var best: i64 = 0
    var i: i64 = 0

    while i <= n {
        // Use height 0 as sentinel at position n
        var cur_h: i64 = 0
        if i < n {
            cur_h = heights[i]
        }

        while top > 0 {
            let peek_idx = stack[top - 1]
            if heights[peek_idx] <= cur_h { break }

            // Pop
            top = top - 1
            let h = heights[peek_idx]
            var width: i64 = i
            if top > 0 {
                width = i - stack[top - 1] - 1
            }
            let area = h * width
            if area > best {
                best = area
            }
        }

        stack[top] = i
        top = top + 1
        i = i + 1
    }

    best
}

fn main() -> i64 with IO, Mut, Panic, Div {
    // Test 1: [2,1,5,6,2,3] -> 10 (bars at index 2,3: min(5,6)*2=10)
    var h1: [i64; 256] = [0; 256]
    h1[0] = 2
    h1[1] = 1
    h1[2] = 5
    h1[3] = 6
    h1[4] = 2
    h1[5] = 3
    assert(largest_rectangle(h1, 6) == 10)

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

    // Test 3: all same [3,3,3,3] -> 12
    var h3: [i64; 256] = [0; 256]
    h3[0] = 3
    h3[1] = 3
    h3[2] = 3
    h3[3] = 3
    assert(largest_rectangle(h3, 4) == 12)

    // Test 4: ascending [1,2,3,4,5] -> 9 (bars 2-4: 3*3)
    var h4: [i64; 256] = [0; 256]
    h4[0] = 1
    h4[1] = 2
    h4[2] = 3
    h4[3] = 4
    h4[4] = 5
    assert(largest_rectangle(h4, 5) == 9)

    // Test 5: single bar [7] -> 7
    var h5: [i64; 256] = [0; 256]
    h5[0] = 7
    assert(largest_rectangle(h5, 1) == 7)

    // Test 6: descending [5,4,3,2,1] -> 9
    var h6: [i64; 256] = [0; 256]
    h6[0] = 5
    h6[1] = 4
    h6[2] = 3
    h6[3] = 2
    h6[4] = 1
    assert(largest_rectangle(h6, 5) == 9)

    // Test 7: empty -> 0
    var h7: [i64; 256] = [0; 256]
    assert(largest_rectangle(h7, 0) == 0)

    println("063_largest_rectangle: ALL TESTS PASSED")
    0
}