How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Zipline.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Zipline during technical interviews.

Compute Maximum Area Under Adjacent Bars

Q: Compute Maximum Area Under Adjacent Bars

This question evaluates proficiency in array algorithms, range-based aggregation, and algorithmic optimization, including efficient data structure usage and complexity analysis for large inputs.

Company: Zipline

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given an array `heights` of `n` non-negative integers. Each value represents the height of a vertical bar of width `1`, and the bars are placed next to each other. Choose any contiguous range of bars. Within that range, you may form a rectangle whose height is at most the minimum bar height in the range and whose width is the number of bars in the range. Return the maximum possible rectangle area. Constraints: - `1 <= n <= 100000` - `0 <= heights[i] <= 1000000000` - The answer may require 64-bit integer arithmetic. Example: - Input: `heights = [2, 1, 5, 6, 2, 3]` - Output: `10` - Explanation: Choosing the bars with heights `5` and `6` gives height `5`, width `2`, and area `10`.

Quick Answer: This question evaluates proficiency in array algorithms, range-based aggregation, and algorithmic optimization, including efficient data structure usage and complexity analysis for large inputs.

You are given an array `heights` of `n` non-negative integers. Each value represents the height of a vertical bar of width `1`, and the bars are placed next to each other. Choose any contiguous range of bars. Within that range, you may form a rectangle whose height is at most the minimum bar height in the range and whose width is the number of bars in the range. Return the maximum possible rectangle area. This is the classic "Largest Rectangle in Histogram" problem. A monotonic stack of indices lets you find, for each bar, the maximal contiguous span over which that bar is the limiting (minimum) height, in O(n) total time. **Example:** - Input: `heights = [2, 1, 5, 6, 2, 3]` - Output: `10` - Explanation: Choosing the bars with heights `5` and `6` gives height `5`, width `2`, and area `10`.

Constraints

1 <= n <= 100000
0 <= heights[i] <= 1000000000
The answer may require 64-bit integer arithmetic (height up to 1e9 times width up to 1e5 ⇒ up to 1e14).

Examples

Input: ([2, 1, 5, 6, 2, 3],)

Expected Output: 10

Explanation: Bars 5 and 6 form height 5 over width 2 = 10.

Input: ([2, 4],)

Expected Output: 4

Explanation: Single bar of height 4 gives 4; pairing both gives height 2 over width 2 = 4.

Input: ([6, 2, 5, 4, 5, 1, 6],)

Expected Output: 12

Explanation: Bars at indices 2..4 (5,4,5) give height 4 over width 3 = 12.

Input: ([0],)

Expected Output: 0

Explanation: Single zero-height bar yields area 0.

Input: ([5],)

Expected Output: 5

Explanation: Single bar: height 5 over width 1 = 5.

Input: ([3, 3, 3, 3],)

Expected Output: 12

Explanation: All equal: height 3 over the full width 4 = 12.

Input: ([1, 2, 3, 4, 5],)

Expected Output: 9

Explanation: Strictly increasing: best is height 3 over width 3 (3,4,5) = 9.

Input: ([5, 4, 3, 2, 1],)

Expected Output: 9

Explanation: Strictly decreasing: best is height 3 over width 3 (5,4,3) = 9.

Input: ([1000000000, 1000000000, 1000000000],)

Expected Output: 3000000000

Explanation: Three max-height bars give 1e9 * 3 = 3e9, requiring 64-bit arithmetic.

Hints

For each bar, ask: what is the widest contiguous span in which this bar is the shortest? Its height times that width is a candidate area.
Use a stack that holds bar indices in non-decreasing height order. When the current bar is shorter than the bar on top of the stack, that top bar can no longer extend rightward — pop it and compute its area.
When popping index `top`, the rectangle height is `heights[top]`; its left boundary is the new stack top (after popping) and its right boundary is the current index `i`, so width = `i - stack[-1] - 1` (or `i` if the stack is empty).
Append a sentinel bar of height 0 at the end (iterate to index n) so every remaining bar in the stack gets flushed and measured.

Quick Overview

This question evaluates proficiency in array algorithms, range-based aggregation, and algorithmic optimization, including efficient data structure usage and complexity analysis for large inputs.