The Weekly Challenge 075

Coins Sum and Largest Rectangle Histogram

Solutions on GitHub

Task 1: Coins Sum

You are given a set of coins @C (assuming an infinite amount of each coin) and a target sum $S. Write a script to find how many ways you can make the sum $S using the coins from the set.

Example Output

Input: @C = (1, 2, 4), $S = 6 Output: 6 Possible ways: a) (1, 1, 1, 1, 1, 1) b) (1, 1, 1, 1, 2) c) (1, 1, 2, 2) d) (1, 1, 4) e) (2, 2, 2) f) (2, 4)

Logic

This is the classic unbounded knapsack / coin change change-counting problem solvable with dynamic programming in O(|C| * S) time and O(S) space. We initialize an array ways of size S + 1 with zeros and set ways[0] = 1. For each coin denomination, we iterate from coin to S and add ways[j - coin] to ways[j].

Perl Solution

ch-1.pl

sub count_coin_ways ( $coins, $target_sum ) { return 1 if $target_sum == 0; return 0 if $target_sum < 0 || !@$coins; my @ways = (0) x ( $target_sum + 1 ); $ways[0] = 1; for my $coin (@$coins) { next if $coin <= 0; for my $j ( $coin .. $target_sum ) { $ways[$j] += $ways[ $j - $coin ]; } } return $ways[$target_sum]; }

Python Solution

ch-1.py

def count_coin_ways(coins: list[int], target_sum: int) -> int: """Calculate the number of combinations of coins that sum to target_sum.""" if target_sum == 0: return 1 if target_sum < 0 or not coins: return 0 ways = [0] * (target_sum + 1) ways[0] = 1 for coin in coins: if coin <= 0: continue for j in range(coin, target_sum + 1): ways[j] += ways[j - coin] return ways[target_sum]

Task 2: Largest Rectangle Histogram

You are given an array of positive numbers @A representing heights of histogram bars. Write a script to find the largest rectangular area formed by the histogram bars.

Example Output

Input: @A = (2, 1, 4, 5, 3, 7) Output: 12 (formed by columns 4, 5, 3, and 7 with min height 3, width 4 => 4 x 3 = 12) Input: @A = (3, 2, 3, 5, 7, 5) Output: 15 (formed by columns 5, 7, and 5 with min height 5, width 3 => 3 x 5 = 15)

Logic

We use a monotonic stack of indices to achieve optimal O(N) time complexity. We iterate over all bars plus a terminating sentinel bar of height 0. As long as the current bar is shorter than the bar at the top of the stack, we pop the stack and calculate the area with the popped height as the minimum bar, with width spanning from the current index back to the new top of the stack. We keep track of the maximum area encountered.

Perl Solution

ch-2.pl

sub largest_rectangle ($histogram) { return 0 if !@$histogram; my @stack; my $max_area = 0; my $n = scalar @$histogram; for my $i ( 0 .. $n ) { my $curr_height = ( $i == $n ) ? 0 : $histogram->[$i]; while ( @stack && $histogram->[ $stack[-1] ] > $curr_height ) { my $top_idx = pop @stack; my $h = $histogram->[$top_idx]; my $w = @stack ? ( $i - $stack[-1] - 1 ) : $i; my $area = $h * $w; $max_area = $area if $area > $max_area; } push @stack, $i; } return $max_area; }

Python Solution

ch-2.py

def largest_rectangle(histogram: list[int]) -> int: """Compute the maximum area of a rectangle formed within the histogram in O(N).""" if not histogram: return 0 stack: list[int] = [] max_area = 0 n = len(histogram) for i in range(n + 1): curr_height = 0 if i == n else histogram[i] while stack and histogram[stack[-1]] > curr_height: top_idx = stack.pop() h = histogram[top_idx] w = (i - stack[-1] - 1) if stack else i max_area = max(max_area, h * w) stack.append(i) return max_area